基于ALM的非精确加速算法

Inexact Acceleration Algorithm Based on ALM

摘要: 增广拉格朗日乘子法为经典有效的解决线性等式约束凸优化问题的一阶优化方法，算法通过原变量与对偶变量的交替迭代更新收敛至最优点。然而，子问题中原变量的更新在实际应用中往往无法精确求解。本文基于增广拉格朗日乘子法、对偶优化以及Nesterov加速技巧，提出一种非精确求解的增广拉格朗日乘子法，利用KKT条件从对偶残差的角度分析并从理论上证明该算法的收敛速率可达到$O\left(1/k^2\right)$ 。

Abstract: The Augmented Lagrangian Method is a classical and effective first-order optimization technique for solving convex optimization problems with linear equality constraints. The algorithm converges to the optimal solution through alternating iterative updates between the primal and dual variables. However, in practical applications, the update of the primal variables in the subproblem is often not solved exactly. In this paper, based on the Augmented Lagrangian Method, dual optimization, and Nesterov’s acceleration technique, we propose an inexact solution version of the Augmented Lagrangian Method. By leveraging the Karush-Kuhn-Tucker (KKT) conditions, we analyze and prove that the convergence rate of the proposed algorithm can achieve a rate of $O\left(1/k^2\right)$ .