A novel augmented Lagrangian method of multipliers for optimization with general inequality constraints
HTML articles powered by AMS MathViewer
- by Xin-Wei Liu, Yu-Hong Dai, Ya-Kui Huang and Jie Sun;
- Math. Comp. 92 (2023), 1301-1330
- DOI: https://doi.org/10.1090/mcom/3799
- Published electronically: December 20, 2022
- HTML | PDF | Request permission
Abstract:
We introduce a twice differentiable augmented Lagrangian for nonlinear optimization with general inequality constraints and show that a strict local minimizer of the original problem is an approximate strict local solution of the augmented Lagrangian. A novel augmented Lagrangian method of multipliers (ALM) is then presented. Our method is originated from a generalization of the Hestenes-Powell augmented Lagrangian, and is a combination of the augmented Lagrangian and the interior-point technique. It shares a similar algorithmic framework with existing ALMs for optimization with inequality constraints, but it can use the second derivatives and does not depend on projections on the set of inequality constraints. In each iteration, our method solves a twice continuously differentiable unconstrained optimization subproblem on primal variables. The dual iterates, penalty and smoothing parameters are updated adaptively. The global and local convergence are analyzed. Without assuming any constraint qualification, it is proved that the proposed method has strong global convergence. The method may converge to either a Karush-Kuhn-Tucker (KKT) point or a singular stationary point when the converging point is a minimizer. It may also converge to an infeasible stationary point of nonlinear program when the problem is infeasible. Furthermore, our method is capable of rapidly detecting the possible infeasibility of the solved problem. Under suitable conditions, it is locally linearly convergent to the KKT point, which is consistent with ALMs for optimization with equality constraints. The preliminary numerical experiments on some small benchmark test problems demonstrate our theoretical results.References
- R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program. 111 (2008), no. 1-2, Ser. B, 5–32. MR 2322882, DOI 10.1007/s10107-006-0077-1
- R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim. 18 (2007), no. 4, 1286–1309. MR 2373302, DOI 10.1137/060654797
- Hande Y. Benson and David F. Shanno, An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming, Comput. Optim. Appl. 38 (2007), no. 3, 371–399. MR 2354201, DOI 10.1007/s10589-007-9048-6
- Hande Y. Benson and David F. Shanno, Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts, Comput. Optim. Appl. 40 (2008), no. 2, 143–189. MR 2390823, DOI 10.1007/s10589-007-9089-x
- Dimitri P. Bertsekas, On penalty and multiplier methods for constrained minimization, SIAM J. Control Optim. 14 (1976), no. 2, 216–235. MR 408830, DOI 10.1137/0314017
- D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier methods, Academic Press, New York, 1982.
- E. G. Birgin and J. M. Martínez, Practical augmented Lagrangian methods for constrained optimization, Fundamentals of Algorithms, vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2014. MR 3186234, DOI 10.1137/1.9781611973365
- James V. Burke, Frank E. Curtis, and Hao Wang, A sequential quadratic optimization algorithm with rapid infeasibility detection, SIAM J. Optim. 24 (2014), no. 2, 839–872. MR 3215068, DOI 10.1137/120880045
- J. V. Burke and S.-P. Han, A robust sequential quadratic programming method, Math. Programming 43 (1989), no. 3, (Ser. A), 277–303. MR 993466, DOI 10.1007/BF01582294
- Richard H. Byrd, Frank E. Curtis, and Jorge Nocedal, Infeasibility detection and SQP methods for nonlinear optimization, SIAM J. Optim. 20 (2010), no. 5, 2281–2299. MR 2650848, DOI 10.1137/080738222
- Richard H. Byrd, Marcelo Marazzi, and Jorge Nocedal, On the convergence of Newton iterations to non-stationary points, Math. Program. 99 (2004), no. 1, Ser. A, 127–148. MR 2031780, DOI 10.1007/s10107-003-0376-8
- Nikolaos Chatzipanagiotis, Darinka Dentcheva, and Michael M. Zavlanos, An augmented Lagrangian method for distributed optimization, Math. Program. 152 (2015), no. 1-2, Ser. A, 405–434. MR 3369487, DOI 10.1007/s10107-014-0808-7
- L. Chen and D. Goldfarb, Interior-point $l_2$-penalty methods for nonlinear programming with strong global convergence properties, Math. Program. 108 (2006), no. 1, Ser. A, 1–36. MR 2229450, DOI 10.1007/s10107-005-0701-5
- Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint, A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM J. Numer. Anal. 28 (1991), no. 2, 545–572. MR 1087519, DOI 10.1137/0728030
- Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint, Testing a class of methods for solving minimization problems with simple bounds on the variables, Math. Comp. 50 (1988), no. 182, 399–430. MR 929544, DOI 10.1090/S0025-5718-1988-0929544-3
- A. R. Conn, N. I. M. Gould, and Ph. L. Toint, LANCELOT, Springer Series in Computational Mathematics, vol. 17, Springer-Verlag, Berlin, 1992. A Fortran package for large-scale nonlinear optimization (release A). MR 1218171, DOI 10.1007/978-3-662-12211-2
- Yu-Hong Dai, Xin-Wei Liu, and Jie Sun, A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs, J. Ind. Manag. Optim. 16 (2020), no. 2, 1009–1035. MR 4155103, DOI 10.3934/jimo.2018190
- Philip E. Gill, Vyacheslav Kungurtsev, and Daniel P. Robinson, A shifted primal-dual penalty-barrier method for nonlinear optimization, SIAM J. Optim. 30 (2020), no. 2, 1067–1093. MR 4081804, DOI 10.1137/19M1247425
- P. E. Gill and D. P. Robinson, A primal-dual augmented Lagrangian, Comput. Optim. Appl., 51 (2012), 1-25.
- D. Goldfarb, R. Polyak, K. Scheinberg, and I. Yuzefovich, A modified barrier-augmented Lagrangian method for constrained minimization, Comput. Optim. Appl. 14 (1999), no. 1, 55–74. MR 1704946, DOI 10.1023/A:1008705028512
- Magnus R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), 303–320. MR 271809, DOI 10.1007/BF00927673
- Willi Hock and Klaus Schittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems, vol. 187, Springer-Verlag, Berlin-New York, 1981. MR 611512, DOI 10.1007/BF00934594
- Mingyi Hong and Zhi-Quan Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program. 162 (2017), no. 1-2, Ser. A, 165–199. MR 3612937, DOI 10.1007/s10107-016-1034-2
- Boris Houska, Janick Frasch, and Moritz Diehl, An augmented Lagrangian based algorithm for distributed nonconvex optimization, SIAM J. Optim. 26 (2016), no. 2, 1101–1127. MR 3493126, DOI 10.1137/140975991
- Christian Kanzow and Daniel Steck, Improved local convergence results for augmented Lagrangian methods in $C^2$-cone reducible constrained optimization, Math. Program. 177 (2019), no. 1-2, Ser. A, 425–438. MR 3987206, DOI 10.1007/s10107-018-1261-9
- Xin-Wei Liu and Yu-Hong Dai, A globally convergent primal-dual interior-point relaxation method for nonlinear programs, Math. Comp. 89 (2020), no. 323, 1301–1329. MR 4063319, DOI 10.1090/mcom/3487
- X.-W. Liu, Y.-H. Dai, and Y.-K. Huang, A primal-dual interior-point relaxation method with global and rapidly local convergence for nonlinear programs, Math. Meth. Oper. Res. 96 (2022), no. 3, 351-382, DOI 10.1007/s00186-022-00797-7.
- Xinwei Liu, Georgia Perakis, and Jie Sun, A robust SQP method for mathematical programs with linear complementarity constraints, Comput. Optim. Appl. 34 (2006), no. 1, 5–33. MR 2224972, DOI 10.1007/s10589-005-3075-y
- Xinwei Liu and Jie Sun, A robust primal-dual interior-point algorithm for nonlinear programs, SIAM J. Optim. 14 (2004), no. 4, 1163–1186. MR 2112969, DOI 10.1137/S1052623402400641
- Xinwei Liu and Yaxiang Yuan, A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties, Math. Program. 125 (2010), no. 1, Ser. A, 163–193. MR 2718699, DOI 10.1007/s10107-009-0272-y
- Xinwei Liu and Yaxiang Yuan, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization, SIAM J. Optim. 21 (2011), no. 2, 545–571. MR 2817478, DOI 10.1137/080739884
- Ya-Feng Liu, Xin Liu, and Shiqian Ma, On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming, Math. Oper. Res. 44 (2019), no. 2, 632–650. MR 3959087, DOI 10.1287/moor.2018.0939
- Jorge Nocedal, Figen Öztoprak, and Richard A. Waltz, An interior point method for nonlinear programming with infeasibility detection capabilities, Optim. Methods Softw. 29 (2014), no. 4, 837–854. MR 3175518, DOI 10.1080/10556788.2013.858156
- Jorge Nocedal and Stephen J. Wright, Numerical optimization, Springer Series in Operations Research, Springer-Verlag, New York, 1999. MR 1713114, DOI 10.1007/b98874
- M. J. D. Powell, A method for nonlinear constraints in minimization problems, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London-New York, 1969, pp. 283–298. MR 272403
- Li Qun Qi and Jie Sun, A nonsmooth version of Newton’s method, Math. Programming 58 (1993), no. 3, Ser. A, 353–367. MR 1216791, DOI 10.1007/BF01581275
- R. T. Rockafellar, The multiplier method of Hestenes and Powell applied to convex programming, J. Optim. Theory Appl. 12 (1973), 555–562. MR 334953, DOI 10.1007/BF00934777
- R. Tyrrell Rockafellar, A dual approach to solving nonlinear programming problems by unconstrained optimization, Math. Programming 5 (1973), 354–373. MR 371416, DOI 10.1007/BF01580138
- R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1 (1976), no. 2, 97–116. MR 418919, DOI 10.1287/moor.1.2.97
- R. Tyrrell Rockafellar, Lagrange multipliers and optimality, SIAM Rev. 35 (1993), no. 2, 183–238. MR 1220880, DOI 10.1137/1035044
- Wenyu Sun and Ya-Xiang Yuan, Optimization theory and methods, Springer Optimization and Its Applications, vol. 1, Springer, New York, 2006. Nonlinear programming. MR 2232297
- Andreas Wächter and Lorenz T. Biegler, Failure of global convergence for a class of interior point methods for nonlinear programming, Math. Program. 88 (2000), no. 3, Ser. A, 565–574. MR 1782156, DOI 10.1007/PL00011386
- Ya Xiang Yuan, On the convergence of a new trust region algorithm, Numer. Math. 70 (1995), no. 4, 515–539. MR 1337231, DOI 10.1007/s002110050133
Bibliographic Information
- Xin-Wei Liu
- Affiliation: Institute of Mathematics, Hebei University of Technology, Tianjin 300401, People’s Republic of China
- MR Author ID: 667307
- ORCID: 0000-0002-9829-3395
- Email: mathlxw@hebut.edu.cn
- Yu-Hong Dai
- Affiliation: Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, People’s Republic of China; and School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, People’s Republic of China
- MR Author ID: 620453
- ORCID: 0000-0002-6932-9512
- Email: dyh@lsec.cc.ac.cn
- Ya-Kui Huang
- Affiliation: Institute of Mathematics, Hebei University of Technology, Tianjin 300401, People’s Republic of China
- ORCID: 0000-0001-6149-3222
- Email: hyk@hebut.edu.cn
- Jie Sun
- Affiliation: Institute of Mathematics, Hebei University of Technology, Tianjin 300401, People’s Republic of China; and School of Business, National University of Singapore, Singapore 119245, Singapore
- ORCID: 0000-0001-5611-1672
- Email: jsun@nus.edu.sg
- Received by editor(s): July 27, 2021
- Received by editor(s) in revised form: March 15, 2022, and August 8, 2022
- Published electronically: December 20, 2022
- Additional Notes: The first author was supported by the NSFC grants (nos. 12071108 and 11671116). The second author was supported by the NSFC grants (nos. 12021001, 11991021, 11991020 and 11971372), the National Key R&D Program of China (nos. 2021YFA 1000300 & 2021YFA 1000301), the Strategic Priority Research Program of Chinese Academy of Sciences (no. XDA27000000). The third author was supported by the NSFC grant (no. 11701137) and Natural Science Foundation of Hebei Province (no. A2021202010).
The first author is the corresponding author. - © Copyright 2022 American Mathematical Society
- Journal: Math. Comp. 92 (2023), 1301-1330
- MSC (2020): Primary 90C26, 90C30, 90C51
- DOI: https://doi.org/10.1090/mcom/3799
- MathSciNet review: 4550327