非线性规划中的增广拉格朗日乘子法进阶题

题目描述
考虑非线性规划问题：

\[\min f(x) = x_1^2 + x_2^2 \text{s.t. } c(x) = x_1 + x_2 - 1 = 0 \]

其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。要求使用增广拉格朗日乘子法（Augmented Lagrangian Method）求解该问题，并分析其收敛性。

解题过程

1. 增广拉格朗日函数构造
   增广拉格朗日函数结合了拉格朗日函数和罚函数，形式为：

\[ L_\rho(x, \lambda) = f(x) + \lambda c(x) + \frac{\rho}{2} \|c(x)\|^2 \]

其中 \(\lambda\) 是拉格朗日乘子，\(\rho > 0\) 是罚参数。代入本题的具体函数：

\[ L_\rho(x, \lambda) = x_1^2 + x_2^2 + \lambda (x_1 + x_2 - 1) + \frac{\rho}{2} (x_1 + x_2 - 1)^2 \]

2. 迭代格式
   算法交替更新变量 \(x\) 和乘子 \(\lambda\)：
   • 步骤1（极小化）：固定 \(\lambda^k\)，求解无约束子问题：

\[ x^{k+1} = \arg\min_{x} L_{\rho}(x, \lambda^k) \]

• 步骤2（乘子更新）：根据约束违反程度更新乘子：

\[ \lambda^{k+1} = \lambda^k + \rho c(x^{k+1}) \]

重复直至收敛（如 \(\|c(x^k)\| < \epsilon\)）。

3. 求解无约束子问题
   对 \(L_\rho(x, \lambda^k)\) 求梯度并令其为0：

\[ \nabla_{x_1} L_\rho = 2x_1 + \lambda^k + \rho (x_1 + x_2 - 1) = 0 \]

\[ \nabla_{x_2} L_\rho = 2x_2 + \lambda^k + \rho (x_1 + x_2 - 1) = 0 \]

两式相减得 \(x_1 = x_2\)。代入约束近似形式：

\[ 2x_1 + \lambda^k + \rho (2x_1 - 1) = 0 \implies x_1 = \frac{\rho - \lambda^k}{2(1 + \rho)} \]

因此 \(x^{k+1} = \left( \frac{\rho - \lambda^k}{2(1 + \rho)}, \frac{\rho - \lambda^k}{2(1 + \rho)} \right)\)。

4. 乘子更新与收敛分析
   代入乘子更新公式：

\[ \lambda^{k+1} = \lambda^k + \rho \left( \frac{\rho - \lambda^k}{1 + \rho} - 1 \right) = \lambda^k - \frac{\rho}{1 + \rho} (\lambda^k + \rho) \]

简化后得：

\[ \lambda^{k+1} = \frac{1}{1 + \rho} \lambda^k - \frac{\rho^2}{1 + \rho} \]

这是一个线性递推关系。当 \(\rho > 0\) 时，系数 \(\frac{1}{1 + \rho} < 1\)，因此迭代线性收敛到固定点 \(\lambda^* = -\rho\)。此时 \(x^* = (0.5, 0.5)\)，满足约束且为目标函数极小点。

5. 对比基本拉格朗日法
   若使用基本拉格朗日法（无罚项），需精确求解 \(\nabla L = 0\)，但子问题可能非凸。增广拉格朗日法通过罚项增强凸性，即使 \(\rho\) 较小，也能保证子问题可解，且收敛更稳定。

总结
增广拉格朗日法通过结合乘子更新和罚函数，平衡了收敛速度与数值稳定性。本题展示了其迭代过程的理论收敛性，实际应用中可自适应调整 \(\rho\) 以加速收敛。