Local convergence analysis for partitioned quasi-Newton updates

Springer Science and Business Media LLC - Tập 39 - Trang 429-448 - 1982
A. Griewank1,2, Ph. L. Toint1,2
1Department of Southern Mathematics Methodist University, Dallas, USA
2Department of Mathematics, Facultes Universitaires de Namur, Namur, Belgium

Tóm tắt

This paper considers local convergence properties of inexact partitioned quasi-Newton algorithms for the solution of certain non-linear equations and, in particular, the optimization of partially separable objective functions. Using the bounded deterioration principle, one obtains local and linear convergence, which impliesQ-superlinear convergence under the usual conditions on the quasi-Newton updates. For the optimization case, these conditions are shown to be satisfied by any sequence of updates within the convex Broyden class, even if some Hessians are singular at the minimizer. Finally, local andQ-superlinear convergence is established for an inexact partitioned variable metric method under mild assumptions on the initial Hessian approximations.

Tài liệu tham khảo

Dennis, J.E., Moré, J.J.: Quasi-Newton Methods, Motivation and Theory. SIAM Rev.19, 46–89 (1977)

Dennis, J.E., Moré, J.J.: A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods. Math. Comput.28 (126), 549–560 (1974)

Dembo, R.S., Eisenstat, S.C., Steilhaug, T.: Inexact-Newton Methods. SIAM J. Numer. Anal.19, 400–408 (1982)

Dennis, J.E., Walker, H.F.: Convergence Theorems for Least Change Secant Update Methods. SIAM J. Numer. Anal.18, 949–987 (1981)

Fletcher, R.: A New Approach to Variable Metric Algorithms. Comput. J.13, 317–322 (1970)

Griewank, A., Toint, Ph.L.: Partitioned Variable Metric Updates for Large Structured Optimization Problems. Numer. Math.39, 119–137 (1982)

Griewank, A., Toint, Ph.L.: On the Unconstrained Optimization of Partially separable Functions. In M.J.D. Powell (ed.), Nonlinear Optimization. New York: Academic Press, 1981

Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. New York: Academic Press, 1970

Powell, M.J.D.: Some Global Convergence Properties of a Variable Metric Algorithm for Minimization Without Exact Line Searches. SIAM-AMS Proc.9.

Powell, M.J.D.: The convergence of variable metric methods for nonlinearly constrained optimization calculations In O.L. Mangasarin, R.R. Meyer, S.M. Robinson (ed.), Nonlinear Programming 3. New York: Academic Press, 1978

Ritter, K.: Local and Superlinear Convergence of a Class of Variable Metric Methods. Computing23, 287–297 (1979)

Stachurski, A.: Superlinear Convergence of Broyden's Bounded theta-Class of Methods. Math. Progr.20, 196–212 (1981)

Steihaug, T.: Quasi-Newton Methods for Large Scale Nonlinear Problems. PhD Thesis, Yale University, 1980

Stoer, J.: On the Convergence Rate of Imperfect Minimization Algorithms in Broyden's beta-Class. Math. Progr.9 (3), 313–335 (1975)

Warth, W., Werner, J.: Effizente Schrittweitenfunktionen bei unrestringierten Optimierungsaufgaben. Computing19 (1), 59–72 (1977)

Werner, J.: Über die globale Konvergenz von Variable-Metrik Verfahren mit nichtexakter Schrittweitenbestimmung. Numer. Math.31, 321–334 (1978)

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 39

429-448

Thông tin tác giả