×

A regularized factorization-free method for equality-constrained optimization. (English) Zbl 1390.90389

Summary: We propose a method for equality-constrained optimization based on a problem in which all constraints are systematically regularized. The regularization is equivalent to applying an augmented Lagrangian method but the linear system used to compute a search direction is reminiscent of regularized sequential quadratic programming. A limited-memory BFGS approximation to second derivatives allows us to employ iterative methods for linear least squares to compute steps, resulting in a factorization-free implementation. We establish global and fast local convergence under weak assumptions. In particular, we do not require the LICQ and our method is suitable for degenerate problems. Preliminary numerical experiments show that a factorization-based implementation of our method exhibits significant robustness while a factorization-free implementation, though not as robust, is promising. We briefly discuss generalizing our framework to other classes of methods and to problems with inequality constraints.

MSC:

90C06 Large-scale problems in mathematical programming
90C20 Quadratic programming
90C30 Nonlinear programming
90C51 Interior-point methods
90C53 Methods of quasi-Newton type
90C55 Methods of successive quadratic programming type
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Al-Baali, {\it Damped techniques for enforcing convergence of quasi-Newton methods}, Optim. Methods Softw., 29 (2014), pp. 919-936, . · Zbl 1308.90201
[2] P. Armand, J. Benoist, R. Omheni, and V. Pateloup, {\it Study of a primal-dual algorithm for equality constrained minimization}, Comput. Optim. Appl., 59 (2014), pp. 405-433, . · Zbl 1304.49050
[3] P. Armand, J. Benoist, and D. Orban, {\it From global to local convergence of interior methods for nonlinear optimization}, Optim. Methods Softw., 28 (2012), pp. 1051-1080, . · Zbl 1278.90254
[4] P. Armand and R. Omheni, {\it A globally and quadratically convergent primal-dual augmented Lagrangian algorithm for equality constrained optimization}, Optim. Methods Softw., 32 (2015), . · Zbl 1365.90209
[5] S. Arreckx, D. Orban, and N. van Omme, {\it NLP.py–A Large-Scale Optimization Toolkit in Python}, Cahier du GERAD G-2016-42, GERAD, Montréal, QC, Canada, 2016.
[6] D. P. Bertsekas, {\it Constrained Optimization and Lagrange Multiplier Methods}, Academic Press, New York, 1996, . · Zbl 0572.90067
[7] E. G. Birgin and J. M. Martínez, {\it Practical Augmented Lagrangian Methods for Constrained Optimization}, Fundam. Algorithms, SIAM, Philadelphia, 2014, . · Zbl 1339.90312
[8] P. T. Boggs and J. W. Tolle, {\it Sequential quadratic programming}, Acta Numer., 4 (1995), pp. 1-51, . · Zbl 0828.65060
[9] R. H. Byrd, F. E. Curtis, and J. Nocedal, {\it An inexact Newton method for nonconvex equality constrained optimization}, Math. Program., 122 (2009), pp. 273-299, . · Zbl 1184.90127
[10] R. H. Byrd, J. Nocedal, and R. B. Schnabel, {\it Representations of quasi-Newton matrices and their use in limited memory methods}, Math. Program., 63 (1994), pp. 129-156, . · Zbl 0809.90116
[11] R. H. Byrd, R. A. Tapia, and Y. Zhang, {\it An SQP augmented lagrangian BFGS algorithm for constrained optimization}, SIAM J. Optim., 2 (1992), pp. 210-241. · Zbl 0773.90065
[12] J. E. Dennis and J. J. Moré, {\it Quasi-Newton methods, motivation and theory}, SIAM Rev., 19 (1977), pp. 46-89, . · Zbl 0356.65041
[13] J. E. J. Dennis and R. B. Schnabel, {\it Numerical Methods for Unconstrained Optimization and Nonlinear Equations}, Classics in Appl. Math. 16, SIAM, Philadelphia, 1996, . · Zbl 0847.65038
[14] I. S. Duff, {\it MA57–a code for the solution of sparse symmetric definite and indefinite systems}, ACM Trans. Math. Software, 30 (2004), pp. 118-144, . · Zbl 1070.65525
[15] D. Fernández, E. A. Pilotta, and G. A. Torres, {\it An inexact restoration strategy for the globalization of the sSQP method}, Comput. Optim. Appl., 54 (2012), pp. 595-617, . · Zbl 1295.90077
[16] D. Fernàndez and M. Solodov, {\it Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems}, Math. Program., 125 (2010), pp. 47-73, . · Zbl 1203.90144
[17] D. C.-L. Fong and M. A. Saunders, {\it LSMR: An iterative algorithm for sparse least-squares problems}, SIAM J. Sci. Comput., 33 (2011), pp. 2950-2971, . · Zbl 1232.65052
[18] R. Fourer, D. M. Gay, and B. W. Kernighan, {\it AMPL: A Modeling Language for Mathematical Programming}, 2nd ed., Brooks/Cole, Pacific Grove, CA, 2003. · Zbl 0701.90062
[19] M. P. Friedlander and D. Orban, {\it A primal-dual regularized interior-point method for convex quadratic programs}, Math. Program. Comput., 4 (2012), pp. 71-107, . · Zbl 1279.90193
[20] J. Gauvin, {\it A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming}, Math. Program. Ser. B, 12 (1977), pp. 136-138. · Zbl 0354.90075
[21] P. Gill and D. Robinson, {\it A globally convergent stabilized SQP method}, SIAM J. Optim., 23 (2013), pp. 1983-2010, . · Zbl 1285.49023
[22] P. E. Gill, V. Kungurtsev, and D. P. Robinson, {\it A stabilized SQP method: Global convergence}, IMA J. Numer. Anal., 37 (2017), pp. 407-443, . · Zbl 1367.49003
[23] P. E. Gill, V. Kungurtsev, and D. P. Robinson, {\it A stabilized SQP method: Superlinear convergence}, Math. Program., 163 (2017), pp. 369-410, . · Zbl 1367.49003
[24] P. E. Gill and E. Wong, {\it Sequential Quadratic Programming Methods}, in Mixed Integer Nonlinear Programming, J. Lee and S. Leyffer, eds., IMA Vol. Math. Appl. 154, Springer New York, 2011, pp. 147-224, . · Zbl 1242.90297
[25] N. I. M. Gould, {\it On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem}, Math. Program., 32 (1985), pp. 90-99, . · Zbl 0591.90068
[26] N. I. M. Gould, D. Orban, and P. L. Toint, {\it CUTEst: A constrained and unconstrained testing environment with safe threads}, Comput. Optim. Appl., 60 (2015), pp. 545-557, . · Zbl 1325.90004
[27] W. W. Hager, {\it Stabilized sequential quadratic programming}, Comput. Optim. Appl., 12 (1999), pp. 253-273, . · Zbl 1040.90566
[28] M. Heinkenschloss and D. Ridzal, {\it A matrix-free trust-region sqp method for equality constrained optimization}, SIAM J. Optim., 24 (2014), pp. 1507-1541. · Zbl 1316.90064
[29] W. Hock and K. Schittkowski, {\it Test Examples for Nonlinear Programming Codes}, Lectures Notes in Econom. and Math. Systems 187, Springer, New York, 1981. · Zbl 0452.90038
[30] A. F. Izmailov and M. V. Solodov, {\it Stabilized SQP Revisited}, Math. Program., 133 (2012), pp. 93-120, . · Zbl 1245.90145
[31] A. F. Izmailov, M. V. Solodov, and E. I. Uskov, {\it Combining stabilized SQP with the augmented Lagrangian algorithm}, Comput. Optim. Appl., 62 (2015), pp. 405-429, . · Zbl 1353.90144
[32] A. F. Izmailov, M. V. Solodov, and E. I. Uskov, {\it Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function}, J. Optim. Theory Appl., 169 (2016), pp. 148-178, . · Zbl 1360.65167
[33] D. C. Liu and J. Nocedal, {\it On the limited memory BFGS method for large scale optimization}, Math. Program., 45 (1989), pp. 503-528, . · Zbl 0696.90048
[34] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer, New York, 2006, . · Zbl 1104.65059
[35] D. Orban, {\it PyKrylov: Krylov Subspace Methods in Pure Python}, (2009).
[36] D. Orban and M. Arioli, {\it Iterative Solution of Symmetric Quasi-Definite Linear Systems}, SIAM Spotlights 3, SIAM, Philadelphia, 2017, . · Zbl 1409.65004
[37] C. Paige and M. A. Saunders, {\it Solution of sparse indefinite systems of linear equations}, SIAM J. Numer. Anal., 12 (1975), pp. 617-629, . · Zbl 0319.65025
[38] C. C. Paige and M. A. Saunders, {\it LSQR: An algorithm for sparse linear equations and sparse least squares}, ACM Trans. Math. Software, 8 (1982), pp. 43-71, . · Zbl 0478.65016
[39] M. J. D. Powell, {\it A fast algorithm for nonlinearly constrained optimization calculations}, in Numerical Analysis, Lecture Notes in Math. 630, Springer, New York, 1978, pp. 144-157, .
[40] R. T. Rockafellar, {\it Augmented Lagrangians and applications of the proximal point algorithm in convex programming}, Math. Oper. Res., 1 (1976), pp. 97-116, . · Zbl 0402.90076
[41] R. J. Vanderbei, {\it Symmetric quasi-definite matrices}, SIAM J. Optim., 5 (1995), pp. 100-113, . · Zbl 0822.65017
[42] A. Wächter and L. T. Biegler, {\it On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming}, Math. Program., 106 (2006), pp. 25-57, . · Zbl 1134.90542
[43] R. B. Wilson, {\it A Simplicial Method for Convex Programming}, Ph.D. thesis, Harvard University, Cambridge, MA, 1963.
[44] S. J. Wright, {\it Primal-Dual Interior-Point Methods}, SIAM, Philadelphia, 1997, . · Zbl 0863.65031
[45] S. J. Wright, {\it Superlinear Convergence of a Stabilized SQP Method to a Degenerate Solution}, Comput. Optim. Appl., 11 (1998), pp. 253-275, . · Zbl 0917.90279
[46] S. J. Wright, {\it An algorithm for degenerate nonlinear programming with rapid local convergence}, SIAM J. Optim., 15 (2005), pp. 673-696, . · Zbl 1077.90067
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.