Advanced Search
Article Contents
Article Contents

Global convergence of a modified Broyden family method for nonconvex functions

This work is supported by the National Natural Science Foundation of China (Grant No. 11661009), the High Level Innovation Teams and Excellent Scholars Program in Guangxi institutions of higher education (Grant No.[2019]52), the Guangxi Natural Science Key Fund (No. 2017GXNSFDA198046), the Special Funds for Local Science and Technology Development Guided by the Central Government (No. ZY20198003), and the special foundation for Guangxi Ba Gui Scholars

Abstract Full Text(HTML) Figure(4) / Table(1) Related Papers Cited by
  • The Broyden family method is one of the most effective methods for solving unconstrained optimization problems. However, the study of the global convergence of the Broyden family method is not sufficient. In this paper, a new Broyden family method is proposed based on the BFGS formula of Yuan and Wei (Comput. Optim. Appl. 47: 237-255, 2010). The following approaches are used in the designed algorithm: (1) a modified Broyden family formula is given, (2) every matrix sequence $ \{B_k\} $ generated by the new algorithm possesses positive-definiteness, and (3) the global convergence of the new presented Broyden family algorithm with the Y-W-L inexact line search is obtained for general functions. Numerical performance shows that the modified Broyden family method is competitive with the classical Broyden family method.

    Mathematics Subject Classification: Primary: 90C53.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Performance profiles of the algorithm MBroyden with different $ \phi $

    Figure 2.  Performance profiles of these methods(CPU)

    Figure 3.  Performance profiles of these methods(NI)

    Figure 4.  Performance profiles of these methods(NFG)

    Table 1.  Test problems

    No. Test problems No. Test problems
    1 Extended Freudenstein and Roth Function 38 ARWHEAD Function (CUTE)
    2 Extended Trigonometric Function 39 ARWHEAD Function (CUTE)
    3 Extended Rosenbrock Function 40 NONDQUAR Function (CUTE)
    4 Extended White and Holst Function 41 DQDRTIC Function (CUTE)
    5 Extended Beale Function 42 EG2 Function (CUTE)
    6 Extended Penalty Function 43 DIXMAANA Function (CUTE)
    7 Perturbed Quadratic Function 44 DIXMAANB Function (CUTE)
    8 Raydan 1 Function 45 DIXMAANC Function (CUTE)
    9 Raydan 2 Function 46 DIXMAANE Function (CUTE)
    10 Diagonal 1 Function 47 Partial Perturbed Quadratic Function
    11 Diagonal 2 Function 48 Broyden Tridiagonal Function
    12 Diagonal 3 Function 49 Almost Perturbed Quadratic Function
    13 Hager Function 50 Tridiagonal Perturbed Quadratic Function
    14 Generalized Tridiagonal 1 Function 51 EDENSCH Function (CUTE)
    15 Extended Tridiagonal 1 Function 52 VARDIM Function (CUTE)
    16 Extended Three Exponential Terms Function 53 STAIRCASE S1 Function
    17 Generalized Tridiagonal 2 Function 54 LIARWHD Function (CUTE)
    18 Diagonal 4 Function 55 DIAGONAL 6 Function
    19 Diagonal 5 Function 56 DIXON3DQ Function (CUTE)
    20 Extended Himmelblau Function 57 DIXMAANF Function (CUTE)
    21 Generalized PSC1 Function 58 DIXMAANG Function (CUTE)
    22 Extended PSC1 Function 59 DIXMAANH Function (CUTE)
    23 Extended Powell Function 60 DIXMAANI Function (CUTE)
    24 Extended Block Diagonal BD1 Function 61 DIXMAANJ Function (CUTE)
    25 Extended Maratos Function 62 DIXMAANK Function (CUTE)
    26 Extended Cliff Function 63 DIXMAANL Function (CUTE)
    27 Quadratic Diagonal Perturbed Function 64 DIXMAAND Function (CUTE)
    28 Extended Wood Function 65 ENGVAL1 Function (CUTE)
    29 Extended Hiebert Function 66 FLETCHCR Function (CUTE)
    30 Quadratic Function QF1 Function 67 COSINE Function (CUTE)
    31 Extended Quadratic Penalty QP1 Function 68 Extended DENSCHNB Function (CUTE)
    32 Extended Quadratic Penalty QP2 Function 69 DENSCHNF Function (CUTE)
    33 A Quadratic Function QF2 Function 70 SINQUAD Function (CUTE)
    34 Extended EP1 Function 71 BIGGSB1 Function (CUTE)
    35 Extended Tridiagonal-2 Function 72 Partial Perturbed Quadratic PPQ2 Function
    36 BDQRTIC Function (CUTE) 73 Scaled Quadratic SQ1 Function
    37 TRIDIA Function (CUTE)
     | Show Table
    DownLoad: CSV
  • [1] M. Al-Baali and H. Khalfan, A combined class of self-scaling and modified quasi-Newton methods, Comput. Optim. Appl., 52 (2012), 393-408.  doi: 10.1007/s10589-011-9415-1.
    [2] C. G. BroydenJ. E. Dennis and J. J. Mor$\acute{e}$, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl., 12 (1973), 223-245.  doi: 10.1093/imamat/12.3.223.
    [3] R. ByrdJ. Nocedal and Y. Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM J. Numer. Anal., 24 (1987), 1171-1189.  doi: 10.1137/0724077.
    [4] R. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer. Anal., 26 (1989), 727-739.  doi: 10.1137/0726042.
    [5] E. D. Dolan and J. J. Mor$\acute{e}$, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213.  doi: 10.1007/s101070100263.
    [6] L. C. W. Dixon, Variable metric algorithms: Nessary and sufficient conditions for identical behavior on nonquadratic functions, J. Optimiz. Theory. App., 10 (1972), 34-40.  doi: 10.1007/BF00934961.
    [7] J. E. Dennis Jr and J. J. Mor$\acute{e}$, Quasi-Newton methods, motivation and theory, SIAM Rev., 19 (1977), 46-89.  doi: 10.1137/1019005.
    [8] J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983.
    [9] Y. Dai, Convergence properties of the BFGS algoritm, SIAM J. Optim., 13 (2003), 693-701.  doi: 10.1137/S1052623401383455.
    [10] R. Fletcher, Practical Methods of Optimization, 2$^nd$ edition, A Wiley-Interscience Publication. John Wiley & Sons, Ltd., Chichester, 1987.
    [11] A. Griewank, The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients, Math. Program., 50 (1991), 141-175.  doi: 10.1007/BF01594933.
    [12] A. Griewank, The "global" convergence of Broyden-like methods with suitable line search, J. Austral. Math. Soc. Ser., 28 (1986), 75-92.  doi: 10.1017/S0334270000005208.
    [13] Z. W. Geem, Parameter estimation for the nonlinear Muskingum model using the BFGS technique, J. Irrig. Drain. Eng., 132 (2006), 474-478.  doi: 10.1061/(ASCE)0733-9437(2006)132:5(474).
    [14] D. Li and M. Fukushima, A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129 (2001), 15-35.  doi: 10.1016/S0377-0427(00)00540-9.
    [15] D. Li and M. Fukushima, On the global convergence of the BFGS method for nonconvex unconstrained optimization problems, SIAM J. Optim., 11 (2001), 1054-1064.  doi: 10.1137/S1052623499354242.
    [16] A. OuyangL. LiuZ. Sheng and F. Wu, A class of parameter estimation methods for nonlinear Muskingum model using hybrid invasive weed optimization algorithm, Math. Probl. Eng., 2015 (2015), 1-15.  doi: 10.1155/2015/573894.
    [17] A. OuyangZ. TangK. LiA. Sallam and E. Sha, Estimating parameters of Muskingum model using an adaptive hybrid PSO algorithm, Int. J. Pattern. Recogn., 28 (2014), 1-29.  doi: 10.1142/S0218001414590034.
    [18] M. J. D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl., 7 (1971), 21-36.  doi: 10.1093/imamat/7.1.21.
    [19] M. J. D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches, Nonlinear Programming, SIAM-AMS Proc., Amer. Math. Soc., Providence, R. I., 9 (1976), 53–72.
    [20] J. D. Pearson, Variable metric methods of minimization, Comput. J., 12 (1969/70), 171-178.  doi: 10.1093/comjnl/12.2.171.
    [21] J. Schropp, A note on minimization problems and multistep methods, Numer. Math., 78 (1997), 87-101.  doi: 10.1007/s002110050305.
    [22] J. Schropp, One-step and multistep procedures for constrained minimization problems, IMA J. Numer. Anal., 20 (2000), 135-152.  doi: 10.1093/imanum/20.1.135.
    [23] P. L. Toint, Global convergence of the partitioned BFGS algorithm for convex partially separable optimization, Math. Program., 36 (1986), 290-306.  doi: 10.1007/BF02592063.
    [24] D. J. Van Wyk, Differential optimization techniques, Appl. Math. Model., 8 (1984), 419-424.  doi: 10.1016/0307-904X(84)90048-9.
    [25] M. N. VrahatisG. S. Androulakis and J. N. Lambrinos, et al., A class of gradient unconstrained minimization algorithms with adaptive stepsize, J. Comput. Appl. Math., 114 (2000), 367-386.  doi: 10.1016/S0377-0427(99)00276-9.
    [26] Z. WeiG. Li and L. Qi, New quasi-Newton methods for unconstrained optimization problems, Appl. Math. Comput., 175 (2006), 1156-1188.  doi: 10.1016/j.amc.2005.08.027.
    [27] Z. WeiG. YuG. Yuan and Z. Lian, The superlinear convergence of a modified BFGS-type method for unconstrained optimization, Comput. Optim. Appl., 29 (2004), 315-332.  doi: 10.1023/B:COAP.0000044184.25410.39.
    [28] H. YabeH. Ogasawara and M. Yoshino, Local and superlinear convergence of quasi-Newton methods based on modified secant conditions, J. Comput. Appl. Math., 205 (2007), 617-632.  doi: 10.1016/j.cam.2006.05.018.
    [29] G. Yuan and X. Lu, A new line search method with trust region for unconstrained optimization, Comm. Appl. Nonlinear Anal., 15 (2008), 35-49. 
    [30] G. YuanZ. ShengB. WangW. Hu and C. Li, The global convergence of a modified BFGS method for nonconvex functions, J. Comput. Appl. Math., 327 (2018), 274-294.  doi: 10.1016/j.cam.2017.05.030.
    [31] G. Yuan, Z. Wang and P. Li, A modifed Broyden family algorithm with global convergence under a weak Wolfe-Powell line search for unconstrained nonconvex problems, Calcolo., 57 (2020), 21pp. doi: 10.1007/s10092-020-00383-5.
    [32] G. YuanZ. Wei and X. Lu, Global convergence of BFGS and PRP methods under a modified weak Wolfe-Powell line search, Appl. Math. Model., 47 (2017), 811-825.  doi: 10.1016/j.apm.2017.02.008.
    [33] G. Yuan and Z. Wei, Convergence analysis of a modified BFGS method on convex minimizations, Comput. Optim. Appl., 47 (2010), 237-255.  doi: 10.1007/s10589-008-9219-0.
    [34] G. Yuan and Z. Wei, New line search methods for unconstrained optimization, J. Korean Statist. Soc., 38 (2009), 29-39.  doi: 10.1016/j.jkss.2008.05.004.
    [35] G. Yuan, Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems, Optim. Lett., 3 (2009), 11-21.  doi: 10.1007/s11590-008-0086-5.
    [36] Y. Yuan and W. Sun, Theory and Methods of Optimization, Science Press of China, Beijing, 1999.
  • 加载中




Article Metrics

HTML views(800) PDF downloads(506) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint