非线性规划中的增广拉格朗日乘子法基础题
题目描述
考虑非线性规划问题：
minimize \(f(x) = x_1^2 + x_2^2\)
subject to \(h(x) = x_1 + x_2 - 2 = 0\)
其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。请使用增广拉格朗日乘子法求解该问题。
解题过程
-
方法原理
增广拉格朗日乘子法结合了拉格朗日乘子法和罚函数法的优点。它构造一个增广拉格朗日函数，其中包含拉格朗日乘子项和一个惩罚约束违反的二次项。通过交替更新乘子和求解无约束子问题，逐步逼近原问题的最优解。其核心公式为：
\(L_A(x, \lambda; \rho) = f(x) + \lambda^T h(x) + \frac{\rho}{2} \|h(x)\|^2\)
其中，\(\lambda\) 是拉格朗日乘子，\(\rho > 0\) 是惩罚参数。 -
构造增广拉格朗日函数
对于给定的问题，等式约束为 \(h(x) = x_1 + x_2 - 2\)。增广拉格朗日函数为：
\(L_A(x_1, x_2, \lambda; \rho) = x_1^2 + x_2^2 + \lambda (x_1 + x_2 - 2) + \frac{\rho}{2} (x_1 + x_2 - 2)^2\) -
算法迭代步骤
算法迭代进行以下两步，直到收敛：
a. 无约束最小化：固定乘子 \(\lambda^k\) 和参数 \(\rho^k\)，求解 \(\min_{x} L_A(x, \lambda^k; \rho^k)\) 得到 \(x^{k+1}\)。
b. 乘子更新：根据约束违反程度更新乘子： \(\lambda^{k+1} = \lambda^k + \rho^k h(x^{k+1})\)。
惩罚参数 \(\rho\) 通常可保持不变或根据规则增加以加速收敛。 -
手动迭代求解
- 初始化：设 \(\lambda^0 = 0\)，\(\rho = 1\)（为简单起见，固定 \(\rho\)）。
- 第1轮迭代：
- 最小化子问题：求解 \(\min L_A = x_1^2 + x_2^2 + 0 \cdot (x_1 + x_2 - 2) + \frac{1}{2} (x_1 + x_2 - 2)^2\)。
展开：\(L_A = x_1^2 + x_2^2 + \frac{1}{2} (x_1^2 + 2x_1x_2 + x_2^2 - 4x_1 - 4x_2 + 4) = \frac{3}{2}x_1^2 + \frac{3}{2}x_2^2 + x_1x_2 - 2x_1 - 2x_2 + 2\)。
求梯度并令其为0：
\(\frac{\partial L_A}{\partial x_1} = 3x_1 + x_2 - 2 = 0\)
\(\frac{\partial L_A}{\partial x_2} = x_1 + 3x_2 - 2 = 0\)
解线性方程组：相减得 \(2x_1 - 2x_2 = 0 \Rightarrow x_1 = x_2\)。代入第一个方程：\(3x_1 + x_1 - 2 = 0 \Rightarrow x_1 = 0.5\)。所以 \(x^1 = (0.5, 0.5)\)。 - 乘子更新：\(h(x^1) = 0.5 + 0.5 - 2 = -1\)，\(\lambda^1 = \lambda^0 + \rho \cdot h(x^1) = 0 + 1 \cdot (-1) = -1\)。
- 最小化子问题：求解 \(\min L_A = x_1^2 + x_2^2 + 0 \cdot (x_1 + x_2 - 2) + \frac{1}{2} (x_1 + x_2 - 2)^2\)。
- 第2轮迭代：
- 最小化子问题：\(L_A = x_1^2 + x_2^2 + (-1)(x_1 + x_2 - 2) + \frac{1}{2} (x_1 + x_2 - 2)^2\)。
展开常数项合并后，梯度方程为：
\(\frac{\partial L_A}{\partial x_1} = 3x_1 + x_2 - 2 - 1 + (-2) = 3x_1 + x_2 - 5 = 0\)（需系统推导：从展开式求导）。
更稳妥地，直接求导：
\(L_A = x_1^2 + x_2^2 - (x_1 + x_2 - 2) + 0.5(x_1 + x_2 - 2)^2\)
\(\frac{\partial L_A}{\partial x_1} = 2x_1 - 1 + (x_1 + x_2 - 2) = 3x_1 + x_2 - 3 = 0\)
\(\frac{\partial L_A}{\partial x_2} = 2x_2 - 1 + (x_1 + x_2 - 2) = x_1 + 3x_2 - 3 = 0\)
解方程组：相减得 \(2x_1 - 2x_2 = 0 \Rightarrow x_1 = x_2\)。代入 \(3x_1 + x_1 - 3 = 0 \Rightarrow x_1 = 0.75\)。所以 \(x^2 = (0.75, 0.75)\)。 - 乘子更新：\(h(x^2) = 0.75 + 0.75 - 2 = -0.5\)，\(\lambda^2 = \lambda^1 + \rho \cdot h(x^2) = -1 + 1 \cdot (-0.5) = -1.5\)。
- 最小化子问题：\(L_A = x_1^2 + x_2^2 + (-1)(x_1 + x_2 - 2) + \frac{1}{2} (x_1 + x_2 - 2)^2\)。
- 第3轮迭代：
- 最小化子问题：梯度方程：
\(\frac{\partial L_A}{\partial x_1} = 2x_1 - 1.5 + (x_1 + x_2 - 2) = 3x_1 + x_2 - 3.5 = 0\)
\(\frac{\partial L_A}{\partial x_2} = 2x_2 - 1.5 + (x_1 + x_2 - 2) = x_1 + 3x_2 - 3.5 = 0\)
解方程组：相减得 \(x_1 = x_2\)，代入得 \(4x_1 = 3.5 \Rightarrow x_1 = 0.875\)。所以 \(x^3 = (0.875, 0.875)\)。 - 乘子更新：\(h(x^3) = 0.875 + 0.875 - 2 = -0.25\)，\(\lambda^3 = -1.5 + 1 \cdot (-0.25) = -1.75\)。
- 最小化子问题：梯度方程：
-
收敛分析
迭代继续，\(x^k\) 趋近于 \((1, 1)\)，\(\lambda^k\) 趋近于 \(-2\)。解析解可验证：原问题通过拉格朗日法得最优解 \(x^* = (1, 1)\)，乘子 \(\lambda^* = -2\)。增广拉格朗日法通过简单迭代逼近了这个解。
总结
增广拉格朗日法通过引入二次惩罚项，使无约束子问题更易求解，同时乘子更新更稳定。本例展示了其逐步收敛到约束问题最优解的过程。