Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/106713
Title: | A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees | Authors: | He, C Lu, Z Pong, TK |
Issue Date: | 2023 | Source: | SIAM journal on optimization, 2023, v. 33, no. 3, p. 1734-1766 | Abstract: | In this paper we consider finding a second-order stationary point (SOSP) of noncon-vex equality constrained optimization when a nearly feasible point is known. In particular, we firstpropose a new Newton-conjugate gradient (Newton-CG) method for finding an approximate SOSPof unconstrained optimization and show that it enjoys a substantially better complexity than theNewton-CG method in [C. W. Royer, M. O'Neill, and S. J. Wright, Math. Program., 180 (2020),pp. 451--488]. We then propose a Newton-CG based augmented Lagrangian (AL) method for find-ing an approximate SOSP of nonconvex equality constrained optimization, in which the proposedNewton-CG method is used as a subproblem solver. We show that under a generalized linear indepen-dence constraint qualification (GLICQ), our AL method enjoys a total inner iteration complexity of\widetilde \scrO (\epsilon 7/2) and an operation complexity of \widetilde \scrO (\epsilon 7/2 min\{ n, \epsilon 3/4\} ) for finding an (\epsilon , \surd \epsilon )-SOSP of non-convex equality constrained optimization with high probability, which are significantly better thanthe ones achieved by the proximal AL method in [Y. Xie and S. J. Wright, J. Sci. Comput., 86 (2021),pp. 1--30]. In addition, we show that it has a total inner iteration complexity of \widetilde \scrO (\epsilon 11/2) and anoperation complexity of \widetilde \scrO (\epsilon 11/2 min\{ n, \epsilon 5/4\} ) when the GLICQ does not hold. To the best of ourknowledge, all the complexity results obtained in this paper are new for finding an approximate SOSPof nonconvex equality constrained optimization with high probability. Preliminary numerical resultsalso demonstrate the superiority of our proposed methods over the other competing algorithms. | Keywords: | Augmented Lagrangian method Iteration complexity Newton conjugate gradient method Nonconvex equality constrained optimization Operation complexity Second-order stationary point |
Publisher: | Society for Industrial and Applied Mathematics Publications | Journal: | SIAM journal on optimization | ISSN: | 1052-6234 | EISSN: | 1095-7189 | DOI: | 10.1137/22M1489824 | Rights: | Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. The following publication He, C., Lu, Z., & Pong, T. K. (2023). A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees. SIAM Journal on Optimization, 33(3), 1734-1766 is available at https://doi.org/10.1137/22m1489824. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
22m1489824.pdf | 2.18 MB | Adobe PDF | View/Open |
Page views
6
Citations as of Jun 30, 2024
Downloads
4
Citations as of Jun 30, 2024
SCOPUSTM
Citations
2
Citations as of Jun 21, 2024
WEB OF SCIENCETM
Citations
1
Citations as of Jun 27, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.