65-理论方法-增广拉格朗日函数法

知识点：增广拉格朗日函数法

知识点概述

增广拉格朗日函数法（Augmented Lagrangian Method），又称乘子法（Method of Multipliers），是罚函数法的一个重要改进。它通过引入拉格朗日乘子的估计，避免了罚函数法中惩罚因子需要趋于无穷大的问题，从而克服了数值病态的缺点。

详细解释

• 动机: 解决罚函数法的数值病态问题。
• 增广拉格朗日函数: 对于等式约束问题 $\min f(x)$ s.t. $c_i(x)=0$，其增广拉格朗日函数为： $L_A(x,\lambda ;\mu )=f(x)+{\sum }_i{\lambda }_i{c}_i(x)+\frac{\mu }{2}{\sum }_i{c}_i(x{)}^2$ 它是在标准拉格朗日函数的基础上增加了一个二次惩罚项。
• 算法 (乘子法):
  1. 在第 $k$ 步，固定拉格朗日乘子 ${\lambda }_k$ 和惩罚因子 ${\mu }_k$。
  2. 求解无约束子问题：$x_{k+1}=\arg {\min }_x{L}_A(x,{\lambda }_k;{\mu }_k)$。
  3. 更新拉格朗日乘子：${\lambda }_{k+1}={\lambda }_k+{\mu }_{k}c(x_{k+1})$。
  4. （可选）增大惩罚因子 ${\mu }_k$。 重复以上步骤。
• 优点: 与罚函数法不同，增广拉格朗日法不需要将 ${\mu }_k$ 增加到无穷大就能使解收敛到最优解。一个中等大小的 ${\mu }_k$ 通常就足够了，这大大改善了算法的数值稳定性。

学习要点

• 理解增广拉格朗日法是对罚函数法的改进。
• 掌握增广拉格朗日函数的构造（拉格朗日函数 + 惩罚项）。
• 掌握乘子法的迭代流程：极小化、更新乘子。
• 知道该方法的核心优点是避免了罚因子趋于无穷。

实践应用

• 是求解非线性约束优化问题的非常强大和流行的算法。
• 交替方向乘子法（ADMM）是增广拉格朗日思想在特定结构问题上的应用，在机器学习和统计领域取得了巨大成功。

关联知识点

• 前置知识: 64-理论方法-罚函数法, 53-理论方法-对偶理论
• 后续知识: 72-理论方法-交替方向乘子法
• 相关知识: 无