Iteration-complexity of first-order augmented Lagrangian methods for convex programming
Iteration-complexity of first-order augmented Lagrangian methods for convex programming
复制标题
DOI：
10.1007/s10107-015-0861-x
复制
发表时间：
2015-01
影响因子：
2.7
通讯作者：
Guanghui Lan;R. Monteiro
中科院分区：
文献类型：
--
作者：
Guanghui Lan;R. Monteiro
考虑一类特殊的凸规划问题，其可行域由与仿射流形相交的简单紧凸集构成。基于经典增广拉格朗日（AL）方法的不精确版本，我们给出了这类问题的一阶方法，其中子问题用Nesterov最优方法近似求解。然后，我们建立了Nesterov最优迭代的总次数的界，即在整个非精确AL方法中执行的内部迭代，以获得接近原对偶最优解。我们还提出了可能比原始的不精确人工智能方法具有更好迭代复杂度界限的变体，这些变体包括将原始方法直接应用于通过向CP问题的目标函数添加强凸分量而得到的摄动问题。
This paper considers a special class of convex programming (CP) problems whose feasible regions consist of a simple compact convex set intersected with an affine manifold. We present first-order methods for this class of problems based on an inexact version of the classical augmented Lagrangian (AL) approach, where the subproblems are approximately solved by means of Nesterov’s optimal method. We then establish a bound on the total number of Nesterov’s optimal iterations, i.e., the inner iterations, performed throughout the entire inexact AL method to obtain a near primal-dual optimal solution. We also present variants with possibly better iteration-complexity bounds than the original inexact AL method, which consist of applying the original approach directly to a perturbed problem obtained by adding a strongly convex component to the objective function of the CP problem.