非线性规划中的增广拉格朗日乘子法基础题
题目描述
考虑如下非线性规划问题：
\[\min f(x) = x_1^2 + x_2^2 \]
满足约束：
\[h(x) = x_1 + x_2 - 2 = 0 \]
其中 \(x = (x_1, x_2)\)。要求使用增广拉格朗日乘子法（Augmented Lagrangian Method）求解该问题，并分析迭代过程。
解题过程
1. 增广拉格朗日函数构造
增广拉格朗日函数结合了拉格朗日乘子法和罚函数的优点，其形式为：
\[L_A(x, \lambda, \rho) = f(x) + \lambda h(x) + \frac{\rho}{2} [h(x)]^2 \]
其中：
- \(\lambda\) 是拉格朗日乘子，
- \(\rho > 0\) 是罚参数，用于强化约束满足。
代入本题的 \(f(x)\) 和 \(h(x)\)：
\[L_A(x, \lambda, \rho) = x_1^2 + x_2^2 + \lambda (x_1 + x_2 - 2) + \frac{\rho}{2} (x_1 + x_2 - 2)^2 \]
2. 迭代格式
增广拉格朗日乘子法的迭代分为两步：
- 优化子问题：固定 \(\lambda^k\) 和 \(\rho^k\)，求解无约束问题：
\[ x^{k+1} = \arg\min_{x} L_A(x, \lambda^k, \rho^k) \]
- 乘子更新：根据约束违反程度更新乘子：
\[ \lambda^{k+1} = \lambda^k + \rho^k h(x^{k+1}) \]
\(\rho\) 可固定或随迭代调整（例如根据约束违反程度增大）。
3. 求解优化子问题
对 \(L_A\) 求梯度并令其为零：
\[\frac{\partial L_A}{\partial x_1} = 2x_1 + \lambda + \rho (x_1 + x_2 - 2) = 0 \]
\[\frac{\partial L_A}{\partial x_2} = 2x_2 + \lambda + \rho (x_1 + x_2 - 2) = 0 \]
两式相减得 \(x_1 = x_2\)。代入第一式：
\[2x_1 + \lambda + \rho (2x_1 - 2) = 0 \]
解得：
\[x_1 = x_2 = \frac{2\rho - \lambda}{2 + 2\rho} \]
4. 乘子更新与迭代计算
设初始值 \(\lambda^0 = 0\)，\(\rho = 1\)：
-
第1轮：
\(x^1 = \frac{2 \times 1 - 0}{2 + 2 \times 1} = 0.5\)，即 \(x_1 = x_2 = 0.5\)。
约束值 \(h(x^1) = 0.5 + 0.5 - 2 = -1\)。
更新乘子：\(\lambda^1 = 0 + 1 \times (-1) = -1\)。 -
第2轮：
\(x^2 = \frac{2 \times 1 - (-1)}{2 + 2 \times 1} = \frac{3}{4} = 0.75\)。
约束值 \(h(x^2) = 0.75 + 0.75 - 2 = -0.5\)。
更新乘子：\(\lambda^2 = -1 + 1 \times (-0.5) = -1.5\)。 -
第3轮：
\(x^3 = \frac{2 \times 1 - (-1.5)}{4} = 0.875\)。
约束值 \(h(x^3) = -0.25\)，\(\lambda^3 = -1.75\)。
迭代继续，\(x\) 趋近于最优解 \(x_1 = x_2 = 1\)（此时 \(h(x)=0\)，\(f(x)=2\)）。
5. 收敛性分析
增广拉格朗日法在较温和条件下具有超线性收敛性。本例中，由于目标函数为凸函数且约束线性，算法能精确收敛到全局最优解。罚参数 \(\rho\) 的选择影响收敛速度：较大的 \(\rho\) 可加快约束满足，但可能使子问题病态。
总结
增广拉格朗日乘子法通过结合乘子更新和罚函数，避免了纯罚函数法中罚参数趋于无穷的数值困难，适用于中等规模的非线性规划问题。