Text

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

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 . We then propose an adaptively regularized I-AL method and show that it achieves a first-order iteration complexity , 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.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.33 No.2 April-June 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1159-1190

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

FIRST-ORDER METHOD
ITERATION COMPLEXITY
AUGMENTED LAGRANGIAN METHOD
CONVEX CONIC PROGRAMMING

Info Detail Spesifik

https://doi.org/10.1137/21M1403837

Pernyataan Tanggungjawab

Zhaosong Lu, Zirui Zhou

Versi lain/terkait

Lampiran Berkas

Komentar