Global convergence of the partitioned BFGS algorithm for convex partially separable optimization.(English)Zbl 0626.90076
To overcome the difficulty of the Broyden-Fletcher-Goldfarb-Shanno method with large scale problems, Griewank and Toint have earlier proposed “partitioned updating” algorithms which exploit the fact that in many such problems the objective function has the form \(f(x)=\sum^{m}_{i=1}f_ i(x)\), where each function \(f_ i\) only depends on a few components of x. In the reviewed paper the author presents a proof of the global convergence for a partitioned updating algorithm when each \(f_ i\) is convex (and some additional conditions are fulfilled). Inexact solution of the linear system defining the search direction and variants of the steplength rule are also shown to be acceptable without affecting the global convergence properties.
Reviewer: H.Tuy
MSC:
| 90C30 | Nonlinear programming |
| 90C25 | Convex programming |
| 65K05 | Numerical mathematical programming methods |
| 49M37 | Numerical methods based on nonlinear programming |
Keywords:
unconstrained optimization;large scale problems;global convergence;partitioned updating algorithmSoftware:
ve08Cite
Full Text:DOI
References:
| [1] | M. Abramowitz and I.A. Stegun,Handbook of Mathematical Functions (Dover Publications, New-York, 1968). ·Zbl 0171.38503 |
| [2] | R.S. Dembo, S.C. Eisenstat and T. Steihaug, ”Inexact Newton methods”,SIAM Journal of Numerical Anal. 19 (1982) 400–408. ·Zbl 0478.65030 ·doi:10.1137/0719025 |
| [3] | R. Fletcher, ”A new approach to variable metric algorithms”,Computer Journal 13 (1970) 317–322. ·Zbl 0207.17402 ·doi:10.1093/comjnl/13.3.317 |
| [4] | A. Griewank and Ph.L. Toint, ”On the unconstrained optimization of partially separable functions”, in: M.J.D. Powell, ed.,Nonlinear Optimization (Academic Press, New-York, 1981). ·Zbl 0563.90085 |
| [5] | A. Griewank and Ph.L. Toin, ”Partitioned variable metric updates for large structured optimization problems”,Numerische Mathematik 39 (1982) 119–137. ·Zbl 0482.65035 ·doi:10.1007/BF01399316 |
| [6] | A. Griewank and Ph.L. Toint, ”Local convergence analysis for partitioned quasi-Newton updates”,Numerische Mathematik 39 (1982) 429–448. ·Zbl 0505.65018 ·doi:10.1007/BF01407874 |
| [7] | A. Griewank and Ph.L. Toint, ”Numerical experiments with partially separable optimization problems”, in: D.F. Griffiths, ed.Numerical Analysis, Proceedings Dundee 1983 (Lecture Notes in Mathematics 1066, Springer-Verlag, Berlin, 1984). ·Zbl 0531.65033 |
| [8] | J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New-York, 1970). ·Zbl 0241.65046 |
| [9] | M.J.D. Powell, ”Some global convergence properties of a variable metric algorithm for minimization without exact line searches”,SIAM-AMS Proceedings 9 (1976) 53–72. ·Zbl 0338.65038 |
| [10] | W. Warth and J. Werner, ”Effiziente Schrittweitenfunktionen bei unrestringierten Optimierungs-aufgaben,”Computing 19 (1) (1977) 59–72. ·Zbl 0367.90101 ·doi:10.1007/BF02260741 |
| [11] | J. Werner, ”Über die globale Konvergenz von Variable-Metric Verfahren mit nichtexakter Schritt-weitenbestimmung”,Numerische Mathematik 31 (1978) 321–334. ·Zbl 0427.65047 ·doi:10.1007/BF01397884 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
