Math——增广拉格朗日乘子法

增广拉格朗日方法（Augmented Lagrangian Method, ALM）是一种用于求解约束优化问题的数值优化算法。它结合了拉格朗日乘子法和罚函数法的优点，能够在保证收敛性的同时避免传统罚函数法中罚参数过大导致的数值不稳定问题

为了处理上述约束优化问题，引入拉格朗日乘子 $\lambda \in \mathbb{R}^m$ 和 $\mu \in \mathbb{R}^p$，并定义增广拉格朗日函数为：
$$
L_A(x, \lambda, \mu; \rho) = f(x) + \sum_{i=1}^m \left[ \lambda_i g_i(x) + \frac{\rho}{2} g_i(x)^2 \right] + \sum_{j=1}^p \left[ \mu_j h_j(x) + \frac{\rho}{2} \max(0, h_j(x))^2 \right],
$$
其中：
- $\lambda_i$ 是等式约束 $g_i(x) = 0$ 的拉格朗日乘子；
- $\mu_j$ 是不等式约束 $h_j(x) \leq 0$ 的拉格朗日乘子；
- $\rho > 0$ 是罚参数，用于平衡约束违反的程度

对于第 $k$ 次迭代依次执行下面的流程：

优化子问题（更新原始变量） ：固定 $\lambda^{(k)}$、$\mu^{(k)}$ 和 $\rho^{(k)}$，求解以下无约束优化问题：
$$
x^{(k+1)} = \arg\min_x L_A(x, \lambda^{(k)}, \mu^{(k)}; \rho^{(k)}).
$$
更新拉格朗日乘子 ：
- 对于等式约束 ：
  $$
  \lambda_i^{(k+1)} = \lambda_i^{(k)} + \rho^{(k)} g_i(x^{(k+1)}), \quad i = 1, \dots, m.
  $$
  - 问题：为什么拉格朗日乘子的更新公式是这样的？理论上，这等价于梯度上升法
  - 直观理解：目标是让 $g_i(x^{(k+1)}) \rightarrow 0$?
    - 当 $g_i(x^{(k+1)}) < 0$ 时，缩小 $\lambda$，表示可适当放开约束，使得下次优化子问题时 $g_i(x^{(k+1)})$ 变大？
    - 当 $g_i(x^{(k+1)}) > 0$ 时，增大 $\lambda$，表示可适当收紧约束，使得下次优化子问题时 $g_i(x^{(k+1)})$ 变小？
- 对于不等式约束 ：
  $$
  \mu_j^{(k+1)} = \max\left(0, \mu_j^{(k)} + \rho^{(k)} h_j(x^{(k+1)})\right), \quad j = 1, \dots, p.
  $$
检查收敛条件 ：如果满足下面条件，则停止迭代，输出 $x^{(k+1)}$ 作为解，否则继续迭代
$$
|g(x^{(k+1)})|_\infty \leq \epsilon \quad \text{且} \quad |\max(0, h(x^{(k+1)}))|_\infty \leq \epsilon,
$$
更新罚参数 ：通常选择逐步增大罚参数，例如按下面的方法更新
$$
\rho^{(k+1)} = \beta \rho^{(k)},
$$
- 其中 $\beta > 1$ 是一个预设的增长因子

对偶上升法（Dual Ascent）和增广拉格朗日乘子法（Augmented Lagrangian Method，ALM）都是用于解决约束优化问题的迭代算法。它们在更新变量的方式上有显著的不同
特别说明 ：两者的区别不仅仅是对偶变量更新的公式不同，最小化求解原始变量时，分别在最小化拉格朗日函数和增广拉格朗日函数 ，这里区别也很大
以下对照均已等式约束为例

增广拉格朗日乘子法是在拉格朗日乘子法的基础上添加了一个二次惩罚项 ，从而增强了原问题的凸性和稳定性。其主要特点如下：
- 初始化 ：同样选择初始值 $x^{(0)}$ 和 $\lambda^{(0)}$
- 构建增广拉格朗日函数 ：构造带有惩罚项的拉格朗日函数 $L_{\rho}(x, \lambda) = f(x) + \lambda^T h(x) + \frac{\rho}{2} |h(x)|^2$，其中 $\rho > 0$ 是惩罚参数
- 最小化增广拉格朗日函数 ：对于固定的 $\lambda^{(k)}$ 和 $\rho$，求解无约束优化问题（增广拉格朗日函数）以找到 $x^{(k+1)}$
- 更新对偶变量 ：更新 $\lambda^{(k+1)} = \lambda^{(k)} + \rho h(x^{(k+1)})$
  - 说明：这等价于固定学习率为 $\rho$ 的梯度上升法更新 $\lambda$，其中有$\nabla_\lambda L_{\rho}(x^{(k+1)}, \lambda^{(k)}) = h(x^{(k+1)})$
与对偶上升法相比，增广拉格朗日乘子法不需要特别小的步长（固定为 $\rho$ 了），并且由于惩罚项的存在，它能够更好地处理非凸问题，并且通常具有更好的数值稳定性和收敛速度

收敛性 ：增广拉格朗日乘子法通常比对偶上升法有更强的收敛性，特别是在非凸问题上
鲁棒性 ：由于加入了惩罚项，增广拉格朗日乘子法通常更稳健，不易受到数值不稳定的影响
计算复杂度 ：每一步中，增广拉格朗日乘子法可能需要解决一个更加复杂的优化问题 ，因为它包含了额外的惩罚项
适用场景 ：如果问题是严格凸的，对偶上升法可能是足够的；但如果存在非凸性或需要更高的鲁棒性 ，则增广拉格朗日乘子法通常是更好的选择

拉格朗日乘子法 ：通过引入拉格朗日乘子将约束条件与目标函数结合成一个新的函数，即拉格朗日函数。其基本思想是将原约束优化问题转化为无约束的拉格朗日函数的极值问题
- 对于具有等式约束的优化问题：
  $$
  \begin{align}
  &\min f(x) ， \\
  \text{s.t.} \ &h_i(x)=0 ， i = 1,2,\cdots,m
  \end{align}
  $$
- 拉格朗日函数定义为：
  $$ L(x,\lambda)=f(x)+\sum_{i = 1}^{m}\lambda_ih_i(x)$$
- 通过求解 $\nabla L = 0$ 来得到原问题的最优解

拉格朗日乘子法 ：直接对拉格朗日函数求偏导数并令其为零，得到一组方程组，然后求解方程组得到最优解。这种方法在理论上很优美，但在实际求解中，当约束条件较多或问题较为复杂时，求解方程组可能会变得非常困难