Back to Search
Start Over
ITERATION-COMPLEXITY OF FIRST-ORDER AUGMENTED LAGRANGIAN METHODS FOR CONVEX CONIC PROGRAMMING.
- Source :
-
SIAM Journal on Optimization . 2023, Vol. 33 Issue 2, p1159-1190. 32p. - Publication Year :
- 2023
-
Abstract
- In this paper we consider a class of convex conic programming. In particular, we first propose an inexact augmented Lagrangian (I-AL) method that resembles the classical I-AL method for solving this problem, in which the augmented Lagrangian subproblems are solved approximately by a variant of Nesterov's optimal first-order method. We show that the total number of first-order iterations of the proposed I-AL method for finding an ϵ-KKT solution is at most O(ϵ-7/4). We then propose an adaptively regularized I-AL method and show that it achieves a first-order iteration complexity O(ϵ-1log ϵ-1), which significantly improves existing complexity bounds achieved by first-order I-AL methods for finding an ϵ-KKT solution. Our complexity analysis of the I-AL methods is based on a sharp analysis of the inexact proximal point algorithm (PPA) and the connection between the I-AL methods and inexact PPA. It is vastly different from existing complexity analyses of the first-order I-AL methods in the literature, which typically regard the I-AL methods as an inexact dual gradient method. [ABSTRACT FROM AUTHOR]
- Subjects :
- *CONVEX programming
*PROBLEM solving
*CONIC sections
Subjects
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 33
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 164895946
- Full Text :
- https://doi.org/10.1137/21M1403837