×

Compact representations of structured BFGS matrices. (English) Zbl 1473.90086

Summary: For general large-scale optimization problems compact representations exist in which recursive quasi-Newton update formulas are represented as compact matrix factorizations. For problems in which the objective function contains additional structure, recent structured quasi-Newton methods exploit available second-derivative information and approximate unavailable second derivatives. This article develops the compact representations of two structured Broyden-Fletcher-Goldfarb-Shanno update formulas. The compact representations enable efficient limited memory and initialization strategies. Two limited memory line search algorithms are described for which extensive numerical results demonstrate the efficacy of the algorithms, including comparisons to IPOPT on large machine learning problems, and to L-BFGS on a real world large scale ptychographic imaging application.

MSC:

90C06 Large-scale problems in mathematical programming
90C53 Methods of quasi-Newton type
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Barzilai, J.; Borwein, J., Two-point step size gradient methods, IMA J. Numer. Anal., 8, 1, 141-148 (1988) · Zbl 0638.65055
[2] Boggs, P.; Byrd, R., Adaptive, limited-memory bfgs algorithms for unconstrained optimization, SIAM J. Optim., 29, 2, 1282-1299 (2019) · Zbl 1431.65082
[3] Brandwood, DH, A complex gradient operator and its application in adaptive array theory, IEEE Proc. F Commun. Radar Signal Process., 130, 1, 11-16 (1983)
[4] Broyden, CG, The convergence of a class of double-rank minimization algorithms 1. General considerations, IMA J. Appl. Math., 6, 1, 76-90 (1970) · Zbl 0223.65023
[5] Brust, JJ; Burdakov, O.; Erway, JB; Marcia, RF, A dense initialization for limited-memory quasi-newton methods, Comput. Optim. Appl., 74, 1, 121-142 (2019) · Zbl 1427.90292
[6] Byrd, RH; Chin, GM; Neveitt, W.; Nocedal, J., On the use of stochastic hessian information in optimization methods for machine learning, SIAM J. Optim., 21, 977-995 (2011) · Zbl 1245.65062
[7] Byrd, RH; Nocedal, J.; Schnabel, RB, Representations of quasi-Newton matrices and their use in limited-memory methods, Math. Program., 63, 129-156 (1994) · Zbl 0809.90116
[8] Chang, CC; Lin, CJ, Libsvm: a library for support vector machines, ACM Trans. Intell. Syst. Technol., 2, 3, 27:1-27:27 (2011)
[9] Dennis, J.; Moré, J., Quasi-newton methods, motivation and theory, SIAM Rev., 19, 46-89 (1977) · Zbl 0356.65041
[10] Dennis, JE Jr; Gay, DM; Walsh, RE, An adaptive nonlinear least-squares algorithm, ACM Trans. Math. Softw., 7, 3, 348-368 (1981) · Zbl 0464.65040
[11] Dennis, JE Jr; Martinez, HJ; Tapia, RA, Convergence theory for the structured bfgs secant method with an application to nonlinear least squares, J. Optim. Theory Appl., 61, 2, 161-178 (1989) · Zbl 0645.65026
[12] Dolan, E.; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
[13] Fletcher, R., A new approach to variable metric algorithms, Comput. J., 13, 3, 317-322 (1970) · Zbl 0207.17402
[14] Fung, SW; Di Wendy, Z., Multigrid optimization for large-scale ptychographic phase retrieval, SIAM J. Imaging Sci., 13, 1, 214-233 (2020) · Zbl 07196102
[15] Gill, PE; Murray, W., Algorithms for the solution of the nonlinear least-squares problem, SIAM J. Numer. Anal., 11, 311-365 (2010)
[16] Goldfarb, D., A family of variable-metric methods derived by variational means, Math. Comp., 24, 23-26 (1970) · Zbl 0196.18002
[17] Gould, NIM; Orban, D.; Toint, PL, CUTEr and SifDec: a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Softw., 29, 4, 373-394 (2003) · Zbl 1068.90526
[18] Mahajan, A., Leyffer, S., Kirches, C.: Solving mixed-integer nonlinear programs by qp diving. Technical Report ANL/MCS-P2071-0312, Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL (2012)
[19] Moré, JJ; Thuente, DJ, Line search algorithms with guaranteed sufficient decrease, ACM Trans. Math. Softw., 20, 3, 286-307 (1994) · Zbl 0888.65072
[20] Nocedal, J., Updating quasi-Newton matrices with limited storage, Math. Comput., 35, 773-782 (1980) · Zbl 0464.65037
[21] Nocedal, J.; Wright, SJ, Numerical Optimization (1999), New York: Springer-Verlag, New York · Zbl 0930.65067
[22] Petra, C.; Chiang, N.; Anitescu, M., A structured quasi-newton algorithm for optimizing with incomplete hessian information, SIAM J. Optim., 29, 2, 1048-1075 (2019) · Zbl 1411.90358
[23] Remmert, R., Theory of Complex Functions (1991), New York: Springer-Verlag, New York · Zbl 0732.32002
[24] Shanno, DF, Conditioning of quasi-Newton methods for function minimization, Math. Comput., 24, 647-656 (1970) · Zbl 0225.65073
[25] Sorber, L.; Barel, MV; Lathauwer, LD, Unconstrained optimization of real functions in complex variables, SIAM J. Optim., 22, 3, 879-898 (2012) · Zbl 1260.90150
[26] Sra, S.; Nowozin, S.; Wright, SJ, Optimization for Machine Learning (2011), New York: The MIT Press, New York
[27] Teo, CH; Vishwanthan, S.; Smola, AJ; Le, QV, Bundle methods for regularized risk minimization, J. Mach. Learn. Res., 11, 311-365 (2010) · Zbl 1242.68253
[28] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57 (2006) · Zbl 1134.90542
[29] Yabe, H.; Takahashi, T., Factorized quasi-newton methods for nonlinear least squares problems, Math. Program. (1991) · Zbl 0737.90064
[30] Zhu, C.; Byrd, R.; Nocedal, J., Algorithm 778: L-BFGS-B: fortran subroutines for large-scale bound-constrained optimization, ACM Trans. Math. Softw., 23, 550-560 (1997) · Zbl 0912.65057
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.