×

zbMATH — the first resource for mathematics

Convergence analysis of a modified BFGS method on convex minimizations. (English) Zbl 1228.90077
Summary: A modified BFGS method is proposed for unconstrained optimization. The global convergence and the superlinear convergence of the convex functions are established under suitable assumptions. Numerical results show that this method is interesting.

MSC:
90C25 Convex programming
Software:
SifDec; CUTEr; ve08; minpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Broyden, C.G., Dennis, J.E., Moré, J.J.: On the local and superlinear convergence of quasi-Newton methods. J. Inst. Math. Appl. 12, 223–246 (1973) · Zbl 0282.65041
[2] Byrd, R., Nocedal, J.: A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J. Numer. Anal. 26, 727–739 (1989) · Zbl 0676.65061
[3] Byrd, R., Nocedal, J., Yuan, Y.: Global convergence of a class of quasi-Newton methods on convex problems. SIAM J. Numer. Analysis 24, 1171–1189 (1987) · Zbl 0657.65083
[4] Dai, Y.: Convergence properties of the BFGS algorithm. SIAM J. Optim. 13, 693–701 (2003) · Zbl 1036.65052
[5] Davidon, W.C.: Variable metric methods for minimization. Argonne National Labs Report, Argonne, IL (1959)
[6] Dennis, J.E. Jr., Moré, J.J.: Quasi-Newton methods, motivation and theory. SIAM Rev. 19, 46–89 (1977) · Zbl 0356.65041
[7] Dennis, J.E., Moré, J.J.: A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comp. 28, 549–560 (1974) · Zbl 0282.65042
[8] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs (1983) · Zbl 0579.65058
[9] Dixon, L.C.W.: Variable metric algorithms: Nessary and sufficient conditions for identical behavior on nonquadratic functions. J. Optim. Theory Appl. 10, 34–40 (1972) · Zbl 0226.49014
[10] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004
[11] Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, Chichester (1987) · Zbl 0905.65002
[12] Gould, N.I.M.: Dominique Orban and Philippe L. Toint, CUTEr(and SifDec): A Constrained and Unconstrained Testing Environment, revisited. ACM Trans. Math. Softw. 29, 373–394 (2003) · Zbl 1068.90526
[13] Griewank, A.: The global convergence of partioned BFGS on problems with convex decompositons and Lipschitzian gradients. Math. Program. 50, 141–175 (1991) · Zbl 0736.90068
[14] Griewank, A.: The ’global’ convergence of Broyden-like methods with a suitable line search. J. Austral. Math. Soc. Ser. B 28, 75–92 (1986) · Zbl 0596.65034
[15] Griewank, A., Toint, Ph.L.: Local convergence analysis for partitioned quasi-Newton updates. Numer. Math. 39, 429–448 (1982) · Zbl 0505.65018
[16] Han, J.Y., Liu, G.H.: Global convergence analysis of a new nonmonotone BFGS algorithm on convex objective functions. Comput. Optim. Appl. 7, 277–289 (1997) · Zbl 0876.90072
[17] Han, J.Y., Liu, G.H.: Notes on the general form of stepsize selection. OR Decis. Mak. 1, 619–624 (1992)
[18] Li, D., Fukushima, M.: A modified BFGS method and its global convergence in nonconvex minimization. J. Comput. Appl. Math. 129, 15–35 (2001) · Zbl 0984.65055
[19] Li, D., Fukushima, M.: On the global convergence of the BFGS method for nonconvex unconstrained optimization problems. SIAM J. Optim. 11, 1054–1064 (2001) · Zbl 1010.90079
[20] Li, G., Tang, C., Wei, Z.: New conjugacy condition and related new conjugate gradient methods for unconstrained optimization problems. J. Comput. Appl. Math. 202, 532–539 (2007) · Zbl 1116.65069
[21] Liu, G.H., Han, J.Y., Xu, Z.L.: Global convergence of the variable metric algorithms with a generalized Wolfe linesearch. J. Math. Res. Exp. 4, 499–508 (1995) · Zbl 0866.90113
[22] Liu, G.H., Han, J.Y., Sun, D.F.: Global convergence analysis of the BFGS algorithm with nonmonotone linesearch. Optimization 34, 147–159 (1995) · Zbl 0858.90122
[23] Liu, G.H., Peng, J.M.: The convergence properties of a nonmonotonic algorithm. J. Comput. Math. 1, 65–71 (1992) · Zbl 0900.65189
[24] Mascarenhas, W.F.: The BFGS method with exact line searches fails for non-convex objective functions. Math. Program. 99, 49–61 (2004) · Zbl 1082.90108
[25] Moré, J.J., Garbow, B.S., Hillstrome, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17–41 (1981) · Zbl 0454.65049
[26] Pearson, J.D.: Variable metric methods of minimization. Comput. J. 12, 171–178 (1969) · Zbl 0207.17301
[27] Powell, M.J.D.: On the convergence of the variable metric algorithm. J. Inst. Math. Appl. 7, 21–36 (1971) · Zbl 0217.52804
[28] Powell, M.J.D.: Some properties of the variable metric algorithm. In: Lootsma, F.A. (ed.) Numerical Methods for Nonlinear Optimization. Academic Press, London (1972) · Zbl 0288.65036
[29] Powell, M.J.D.: Some global convergence properties of a variable metric algorithm for minimization without exact line searches. In: Cottle, R.W., Lemke, C.E. (eds.) Nonlinear Programming, SIAM-AMS Proceedings, vol. IX. SIAM, Philadelphia (1976) · Zbl 0338.65038
[30] Powell, M.J.D.: A new algorithm for unconstrained optimization. In: Rosen, J.B., Mangasarian, O.L., Ritter, K. (eds.) Nonlinear Programming, pp. 31–65. Academic Press, New York (1970) · Zbl 0228.90043
[31] Schropp, J.: A note on minimization problems and multistep methods. Numer. Math. 78, 87–101 (1997) · Zbl 0884.34021
[32] Schropp, J.: One-step and multistep procedures for constrained minimization problems. IMA J. Numer. Anal. 20, 135–152 (2000) · Zbl 0945.65065
[33] Toint, Ph.L.: Global convergence of the partioned BFGS algorithm for convex partially separable opertimization. Math. Program. 36, 290–306 (1986) · Zbl 0626.90076
[34] Van Wyk, D.J.: Differential optimization techniques. Appl. Math. Model. 8, 419–424 (1984) · Zbl 0555.90092
[35] Vrahatis, M.N., Androulakis, G.S., Lambrinos, J.N., Magolas, G.D.: A class of gradient unconstrained minimization algorithms with adaptive stepsize. J. Comput. Appl. Math. 114, 367–386 (2000) · Zbl 0958.65072
[36] Wei, Z., Li, G., Qi, L.: New Quasi-Newton Methods for unconstrained optimization problems. preprint · Zbl 1100.65054
[37] Wei, Z., Qi, L., Chen, X.: An SQP-type method and its application in stochastic programming. J. Optim. Theory Appl. 116, 205–228 (2003) · Zbl 1030.90142
[38] Wei, Z., Yu, G., Yuan, G., Lian, Z.: The superlinear convergence of a modified BFGS-type method for unconstrained optimization. Comput. Optim. Appl. 29, 315–332 (2004) · Zbl 1070.90089
[39] Yuan, G.L.: Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems. Optim. Lett. (2008). doi: 10.1007/s11590-008-0086-5
[40] Yuan, G.L., Lu, X.W.: A new line search method with trust region for unconstrained optimization. Commun. Appl. Nonlinear Analysis 15(1), 35–49 (2008) · Zbl 1146.49031
[41] Yuan, Y., Sun, W.: Theory and Methods of Optimization. Science Press of China, Beijing (1999)
[42] Yuan, G.L., Wei, Z.X.: New Line Search Methods for Unconstrained Optimization. J. Korean Stat. Soc. (2008). doi: 10.1016/j.jkss.2008.05.004 · Zbl 1293.65098
[43] Yuan, G., Wei, Z.: The superlinear convergence analysis of a nonmonotone BFGS algorithm on convex objective functions. Acta Math. Sinica, Eng. Ser. 24(1), 35–42 (2008) · Zbl 1152.65072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.