Recursive form of general limited memory variable metric methods. (English) Zbl 1266.49060

Lukšan, Ladislav; Vlček, Jan

Kybernetika 49, No. 2, 224-235 (2013).

Summary: In this report we propose a new recursive matrix formulation of limited memory variable metric methods. This approach can be used for an arbitrary update from the Broyden class (and some other updates) and also for the approximation of both the Hessian matrix and its inverse. The new recursive formulation requires approximately \(4mn\) multiplications and additions per iteration, so it is comparable with other efficient limited memory variable metric methods. Numerical experiments concerning Algorithm 1, proposed in this report, confirm its practical efficiency.

MSC:

49M30	Other numerical methods in calculus of variations (MSC2010)
49K35	Optimality conditions for minimax problems
90C06	Large-scale problems in mathematical programming
90C47	Minimax problems in mathematical programming
90C51	Interior-point methods

Keywords:

unconstrained optimization; large scale optimization; limited memory methods; variable metric updates; recursive matrix formulation; algorithms

Software:

CUTE; CUTEr; L-BFGS

References:

[1]	Bongartz, I., Conn, A. R., Gould, N., Toint, P. L.: CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Software 21 (1995), 123-160. · Zbl 0886.65058
[2]	Byrd, R. H., Nocedal, J., Schnabel, R. B.: Representation of quasi-Newton matrices and their use in limited memory methods. Math. Programming 63 (1994), 129-156. · Zbl 0809.90116
[3]	Davidon, W. C.: Optimally conditioned optimization algorithms without line searches. Math. Programming 9 (1975), 1-30. · Zbl 0328.90055
[4]	Dolan, E. D., Moré, J. J.: Benchmarking optimization software with performance profiles. Math. Programming 91 (2002), 201-213. · Zbl 1049.90004
[5]	Hoshino, S.: A formulation of variable metric methods. J. Institute of Mathematics and its Applications 10 (1972), 394-403. · Zbl 0258.65065
[6]	Lukšan, L.: Quasi-Newton methods without projections for unconstrained minimization. Kybernetika 18 (1982), 290-306. · Zbl 0514.65047
[7]	Lukšan, L., Matonoha, C., Vlček, J.: Sparse Test Problems for Unconstrained Optimization. Report V-1064, Institute of Computer Science AS CR, Prague 2010.
[8]	Lukšan, L., Matonoha, C., Vlček, J.: Modified CUTE Problems for Sparse Unconstrained Optimization. Report V-1081, Institute of Computer Science AS CR, Prague 2010.
[9]	Spedicato, L. Lukšan amd E.: Variable metric methods for unconstrained optimization and nonlinear least squares. J. Comput. Appl. Math. 124 (2000), 61-95. · Zbl 0985.65066
[10]	Matthies, H., Strang, G.: The solution of nonlinear finite element equations. Internat. J. Numer. Methods Engrg. 14 (1979), 1613-1623. · Zbl 0419.65070
[11]	Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comput. 35 (1980), 773-782. · Zbl 0464.65037
[12]	Vlček, J., Lukšan, L.: Generalizations of the Limited-memory BFGS Method Based on Quasi-product Form of Update. Report V-1060, Institute of Computer Science AS CR, Prague 2009. · Zbl 1279.65080