EUVIMEDEUVIMED entdecken
Crossref

Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming

Zhaosong Lu, Zirui Zhou

SIAM Journal on Optimization · 30.06.2023 · 33 (2) · 1159-1190

DOI: 10.1137/21m1403837 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 23.06.2023. Verfasst von Zhaosong Lu und 1 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 29 Literaturangaben. Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 [Formula: see text]-KKT solution is at most [Formula: see text]. We then propose an adaptively regularized I-AL method and show that it achieves a first-order iteration complexity [Formula: see text], which significantly improves existing complexity bounds achieved by first-order I-AL methods for finding an [Formula: see text]-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.

Förderung

  • NSF

Zitieren

APA

Lu, Z., & Zhou, Z. (2023). Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming. SIAM Journal on Optimization, 33(2), 1159-1190. https://doi.org/10.1137/21m1403837

Vancouver

Lu Z, Zhou Z. Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming. SIAM Journal on Optimization. 2023;33(2):1159-1190. doi:10.1137/21m1403837

BibTeX
@article{Lu2023,
  author = {Lu, Zhaosong and Zhou, Zirui},
  title = {Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming},
  journal = {SIAM Journal on Optimization},
  year = {2023},
  volume = {33},
  number = {2},
  pages = {1159--1190},
  doi = {10.1137/21m1403837}
}
Kostenlos starten →