Previous |  Up |  Next


unconstrained optimization; large scale optimization; limited memory methods; variable metric updates; recursive matrix formulation; algorithms
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 $4 m n$ 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.
[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. DOI 10.1145/200979.201043 | 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. DOI 10.1007/BF01582063 | MR 1268604
[3] Davidon, W. C.: Optimally conditioned optimization algorithms without line searches. Math. Programming 9 (1975), 1-30. DOI 10.1007/BF01681328 | MR 0383741 | Zbl 0328.90055
[4] Dolan, E. D., Moré, J. J.: Benchmarking optimization software with performance profiles. Math. Programming 91 (2002), 201-213. DOI 10.1007/s101070100263 | MR 1875515 | Zbl 1049.90004
[5] Hoshino, S.: A formulation of variable metric methods. J. Institute of Mathematics and its Applications 10 (1972), 394-403. DOI 10.1093/imamat/10.3.394 | MR 0336997 | Zbl 0258.65065
[6] Lukšan, L.: Quasi-Newton methods without projections for unconstrained minimization. Kybernetika 18 (1982), 290-306. MR 0688368 | 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. DOI 10.1016/S0377-0427(00)00420-9 | MR 1803294
[10] Matthies, H., Strang, G.: The solution of nonlinear finite element equations. Internat. J. Numer. Methods Engrg. 14 (1979), 1613-1623. DOI 10.1002/nme.1620141104 | MR 0551801 | Zbl 0419.65070
[11] Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comput. 35 (1980), 773-782. DOI 10.1090/S0025-5718-1980-0572855-7 | MR 0572855 | 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.
Partner of
EuDML logo