Iteration-complexity of first-order augmented Lagrangian methods for convex conic programming
Iteration-complexity of first-order augmented Lagrangian methods for convex conic programming
复制标题
DOI：
10.1137/21m1403837
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Zhaosong Lu;Zirui Zhou
中科院分区：
文献类型：
--
作者：
Zhaosong Lu;Zirui Zhou
本文考虑一类凸锥规划。特别是，我们提出了一个不精确的增广拉格朗日（I-AL）方法来解决这个问题，其中增广拉格朗日子问题近似解决的一个变种Nesterov的最佳一阶方法。我们表明，建议的I-AL方法计算$\mathcal $-KKT解决方案的一阶迭代的总数是最多$\mathcal{O}（\mathcal ^{-7/4}）$。我们还提出了一种改进的I-AL方法，并证明了它具有改进的迭代复杂度$\mathcal{O}（\log ^{-1}）$，这是迄今为止计算$\mathcal $-KKT解的所有一阶I-AL类型方法中复杂度最低的。我们的I-AL方法的复杂性分析主要是基于不精确邻近点算法（PPA）的分析和I-AL方法和不精确PPA之间的联系。这与现有文献中一阶I-AL方法的复杂性分析有很大不同，后者通常将I-AL方法视为不精确的对偶梯度方法。与大多数相关的I-AL方法相比，我们的改进的I-AL方法是更实际有效的，也适用于更广泛的一类问题。
In this paper we consider a class of convex conic programming. In particular, we propose an inexact augmented Lagrangian (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 computing an $\epsilon$-KKT solution is at most $\mathcal{O}(\epsilon^{-7/4})$. We also propose a modified I-AL method and show that it has an improved iteration-complexity $\mathcal{O}(\epsilon^{-1}\log\epsilon^{-1})$, which is so far the lowest complexity bound among all first-order I-AL type of methods for computing an $\epsilon$-KKT solution. Our complexity analysis of the I-AL methods is mainly based on an analysis on inexact proximal point algorithm (PPA) and the link between the I-AL methods and inexact PPA. It is substantially different from the 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. Compared to the mostly related I-AL methods \cite{Lan16}, our modified I-AL method is more practically efficient and also applicable to a broader class of problems.