A structured quasi-Newton algorithm for optimizing with incomplete Hessian information. (English) Zbl 1411.90358
Summary: We present a structured quasi-Newton algorithm for unconstrained optimization problems that have unavailable second-order derivatives or Hessian terms. We provide a formal derivation of the well-known Broyden-Fletcher-Goldfarb-Shanno (BFGS) secant update formula that approximates only the missing Hessian terms, and we propose a linesearch quasi-Newton algorithm based on a modification of Wolfe conditions that converges to first-order optimality conditions. We also analyze the local convergence properties of the structured BFGS algorithm and show that it achieves superlinear convergence under the standard assumptions used by quasi-Newton methods using secant updates. We provide a thorough study of the practical performance of the algorithm on the CUTEr suite of test problems and show that our structured BFGS-based quasi-Newton algorithm outperforms the unstructured counterpart(s).
MSC:
| 90C53 | Methods of quasi-Newton type |
| 90C30 | Nonlinear programming |
| 90C06 | Large-scale problems in mathematical programming |
References:
| [1] | S. Abhyankar, V. Rao, and M. Anitescu, Dynamic security constrained optimal power flow using finite difference sensitivities, in 2014 IEEE Power and Energy Society General Meeting–Conference & Exposition, IEEE, 2014, pp. 1-5. |
| [2] | K. Amini and A. Ghorbani Rizi, A new structured quasi-Newton algorithm using partial information on Hessian, J. Comput. Appl. Math., 234 (2010), pp. 805-811. · Zbl 1190.65094 |
| [3] | C. G. Broyden, J. E. Dennis, Jr., and J. J. Moré, On the local and superlinear convergence of quasi-Newton methods, IMA J. Appl. Math., 12 (1973), pp. 223-245. · Zbl 0282.65041 |
| [4] | R. H. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer. Anal., 26 (1989), pp. 727-739, . · Zbl 0676.65061 |
| [5] | R. H. Byrd, J. Nocedal, and R. B. Schnabel, Representations of quasi-Newton matrices and their use in limited memory methods, Math. Programming, 63 (1994), pp. 129-156. · Zbl 0809.90116 |
| [6] | J. E. Dennis, Jr., H. J. Martinez, and R. A. Tapia, Convergence theory for the structured BFGS secant method with an application to nonlinear least squares, J. Optim. Theory Appl., 61 (1989), pp. 161-178. · Zbl 0645.65026 |
| [7] | J. E. Dennis, Jr., and J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28 (1974), pp. 549-560. · Zbl 0282.65042 |
| [8] | J. E. Dennis, Jr., and J. J. Moré, Quasi-Newton methods, motivation and theory, SIAM Rev., 19 (1977), pp. 46-89, . · Zbl 0356.65041 |
| [9] | J. E. Dennis, Jr., and H. F. Walker, Convergence theorems for least-change secant update methods, SIAM J. Numer. Anal., 18 (1981), pp. 949-987, . · Zbl 0527.65032 |
| [10] | E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201-213. · Zbl 1049.90004 |
| [11] | R. Fletcher, An optimal positive definite update for sparse Hessian matrices, SIAM J. Optim., 5 (1995), pp. 192-218, . · Zbl 0824.65038 |
| [12] | R. Fourer, D. M. Gay, and B. W. Kernighan, AMPL: A mathematical programming language, in Algorithms and Model Formulations in Mathematical Programming, Springer, Berlin, Heidelberg, 1989, pp. 150-151. |
| [13] | N. I. M. Gould, D. Orban, and P. L. Toint, CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM Trans. Math. Software, 29 (2003), pp. 373-394. · Zbl 1068.90526 |
| [14] | A. Griewank and P. L. Toint, Local convergence analysis for partitioned quasi-Newton updates, Numer. Math., 39 (1982), pp. 429-448. · Zbl 0505.65018 |
| [15] | O. Güler, F. Gürtuna, and O. Shevchenko, Duality in quasi-Newton methods and new variational characterizations of the DFP and BFGS updates, Optim. Methods Softw., 24 (2009), pp. 45-62. · Zbl 1154.90624 |
| [16] | J. Huschens, Exploiting additional structure in equality constrained optimization by structured SQP secant algorithms, J. Optim. Theory Appl., 77 (1993), pp. 343-358. · Zbl 0792.90069 |
| [17] | L. Lukšan and E. Spedicato, Variable metric methods for unconstrained optimization and nonlinear least squares, J. Comput. Appl. Math., 124 (2000), pp. 61-95. · Zbl 0985.65066 |
| [18] | J. J. Moré and D. J. Thuente, Line search algorithms with guaranteed sufficient decrease, ACM Trans. Math. Software, 20 (1994), pp. 286-307. · Zbl 0888.65072 |
| [19] | T. B. Nguyen and M. Pai, Dynamic security-constrained rescheduling of power systems using trajectory sensitivities, IEEE Trans. Power Syst., 18 (2003), pp. 848-854. |
| [20] | J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer, New York, 2006. · Zbl 1104.65059 |
| [21] | D. P. O’Leary, A Matlab implementation of a MINPACK line search algorithm by Jorge J. Moré and David J. Thuente, , 1991. |
| [22] | R. Tapia, On secant updates for use in general constrained optimization, Math. Comp., 51 (1988), pp. 181-202. · Zbl 0657.90088 |
| [23] | A. Wächter and L. T. Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), pp. 25-57. · Zbl 1134.90542 |
| [24] | P. Wolfe, Convergence conditions for ascent methods, SIAM Rev., 11 (1969), pp. 226-235, . · Zbl 0177.20603 |
| [25] | P. Wolfe, Convergence conditions for ascent methods. II: Some corrections, SIAM Rev., 13 (1971), pp. 185-188, . · Zbl 0216.26901 |
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.
