整体说明
- 增广拉格朗日方法（Augmented Lagrangian Method, ALM）是一种用于求解约束优化问题的数值优化算法。它结合了拉格朗日乘子法和罚函数法的优点，能够在保证收敛性的同时避免传统罚函数法中罚参数过大导致的数值不稳定问题
问题描述
- 考虑一个约束优化问题：
$$
\begin{align}
&\min_{x \in \mathbb{R}^n} , f(x) \\
\text{s.t.} \quad &g_i(x) = 0, \quad i = 1, \dots, m, \\
&h_j(x) \leq 0, \quad j = 1, \dots, p.
\end{align}
$$ - 其中：
- \(f(x)\) 是目标函数；
- \(g_i(x)\) 是等式约束；
- \(h_j(x)\) 是不等式约束
增广拉格朗日函数
- 为了处理上述约束优化问题，引入拉格朗日乘子 \(\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\) 是罚参数，用于平衡约束违反的程度
算法步骤
- 增广拉格朗日方法通过迭代更新变量 \(x\)、拉格朗日乘子 \(\lambda\) 和 \(\mu\)，以及罚参数 \(\rho\) 来求解优化问题。具体步骤如下：
初始化
- 初始化 \(x^{(0)}\)，\(\lambda^{(0)}\)，\(\mu^{(0)}\)，以及初始罚参数 \(\rho^{(0)} > 0\)
- 设置收敛容差 \(\epsilon > 0\) 和最大迭代次数 \(k_{\text{max}}\)
迭代过程
对于第 \(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{ And } \quad |\max(0, h(x^{(k+1)}))|_\infty \leq \epsilon,
$$更新罚参数 ：通常选择逐步增大罚参数，例如按下面的方法更新
$$
\rho^{(k+1)} = \beta \rho^{(k)},
$$- 其中 \(\beta > 1\) 是一个预设的增长因子
终止条件
- 当达到最大迭代次数或满足收敛条件时，算法终止
特点与优势
- 稳定性 ：相比于传统罚函数法，增广拉格朗日方法对罚参数 \(\rho\) 的依赖较小，能够避免数值不稳定问题
- 灵活性 ：可以处理等式和不等式约束，适用范围广泛
- 全局收敛性 ：在适当的条件下，增广拉格朗日方法具有全局收敛性
附录：对偶上升法与增广拉格朗日乘子法
- 对偶上升法（Dual Ascent）和增广拉格朗日乘子法（Augmented Lagrangian Method，ALM）都是用于解决约束优化问题的迭代算法。它们在更新变量的方式上有显著的不同
- 特别说明 ：两者的区别不仅仅是对偶变量更新的公式不同，最小化求解原始变量时，分别在最小化拉格朗日函数和增广拉格朗日函数 ，这里区别也很大
- 以下对照均已等式约束为例
对偶上升法
- 对偶上升法是一种基于拉格朗日对偶理论的优化方法。它的基本思想是通过交替更新原始变量和对偶变量来逼近最优解。具体步骤如下：
- 初始化 ：选择初始值 \(x^{(0)}\) 和对偶变量 \(\lambda^{(0)}\)
- 构建增广拉格朗日函数 ：构造带拉格朗日函数 \(L(x, \lambda) = f(x) + \lambda^T h(x) \)
- 最小化拉格朗日函数 ：对于固定的 \(\lambda^{(k)}\)，求解无约束优化问题（拉格朗日函数）以找到 \(x^{(k+1)}\)
- 更新对偶变量 ：更新对偶变量 \(\lambda^{(k+1)} = \lambda^{(k)} + \alpha_k \nabla_\lambda L(x^{(k+1)}, \lambda^{(k)})\)，其中 \(\alpha_k\) 是步长参数
- 说明：这是根据梯度上升法来更新参数（使用梯度上升是因为更新对偶变量时，目标是最大化原始拉格朗日函数 \(L(x^{(k+1)}, \lambda^{(k)})\)）,其中有\(\nabla_\lambda L(x^{(k+1)}, \lambda^{(k)}) = h(x^{(k+1)})\)
- 这种方法要求目标函数和约束条件满足一定的凸性条件，并且通常需要较小的步长 \(\alpha_k\) 来保证收敛性
增广拉格朗日乘子法
- 增广拉格朗日乘子法是在拉格朗日乘子法的基础上添加了一个二次惩罚项 ，从而增强了原问题的凸性和稳定性。其主要特点如下：
- 初始化 ：同样选择初始值 \(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\) 了），并且由于惩罚项的存在，它能够更好地处理非凸问题，并且通常具有更好的数值稳定性和收敛速度
比较总结
- 收敛性 ：增广拉格朗日乘子法通常比对偶上升法有更强的收敛性，特别是在非凸问题上
- 鲁棒性 ：由于加入了惩罚项，增广拉格朗日乘子法通常更稳健，不易受到数值不稳定的影响
- 计算复杂度 ：每一步中，增广拉格朗日乘子法可能需要解决一个更加复杂的优化问题 ，因为它包含了额外的惩罚项
- 适用场景 ：如果问题是严格凸的，对偶上升法可能是足够的；但如果存在非凸性或需要更高的鲁棒性 ，则增广拉格朗日乘子法通常是更好的选择
附录：其他相关方法之拉格朗日乘子法
- 拉格朗日乘子法一般用于求解一个原始问题的最优形式（最优形式一般包含着拉格朗日乘子），部分时候根据KKT条件可以直接求得最优解
具体示例
- 拉格朗日乘子法 ：通过引入拉格朗日乘子将约束条件与目标函数结合成一个新的函数，即拉格朗日函数。其基本思想是将原约束优化问题转化为无约束的拉格朗日函数的极值问题
- 对于具有等式约束的优化问题：
$$
\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\) 来得到原问题的最优解
- 对于具有等式约束的优化问题：
求解方式
- 拉格朗日乘子法 ：直接对拉格朗日函数求偏导数并令其为零，得到一组方程组，然后求解方程组得到最优解。这种方法在理论上很优美，但在实际求解中，当约束条件较多或问题较为复杂时，求解方程组可能会变得非常困难
