非线性规划中的松弛变量法基础题
题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
约束条件：
\(g_1(x) = x_1 + x_2 - 2 \leq 0\)
\(g_2(x) = x_1^2 - x_2 \leq 0\)
\(x_1 \geq 0, x_2 \geq 0\)
解题过程
-
问题分析
目标函数 \(f(x)\) 是凸二次函数，约束 \(g_1(x)\) 是线性不等式，\(g_2(x)\) 是非线性不等式。松弛变量法的核心是将不等式约束转化为等式约束，通过引入非负松弛变量，将原问题转化为仅含等式约束和变量非负性的问题。 -
引入松弛变量
对每个不等式约束引入松弛变量 \(s_i \geq 0\)：- \(g_1(x) \leq 0\) 变为 \(x_1 + x_2 - 2 + s_1 = 0\)，其中 \(s_1 \geq 0\)
- \(g_2(x) \leq 0\) 变为 \(x_1^2 - x_2 + s_2 = 0\)，其中 \(s_2 \geq 0\)
原问题转化为：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
约束条件：
\(h_1(x, s) = x_1 + x_2 - 2 + s_1 = 0\)
\(h_2(x, s) = x_1^2 - x_2 + s_2 = 0\)
\(x_1 \geq 0, x_2 \geq 0, s_1 \geq 0, s_2 \geq 0\)
-
构造拉格朗日函数
引入拉格朗日乘子 \(\lambda_1, \lambda_2\) 对应等式约束：
\[ L(x, s, \lambda) = (x_1 - 2)^2 + (x_2 - 1)^2 + \lambda_1 (x_1 + x_2 - 2 + s_1) + \lambda_2 (x_1^2 - x_2 + s_2) \]
-
KKT条件求解
对变量和乘子求偏导，得到KKT条件：- \(\frac{\partial L}{\partial x_1} = 2(x_1 - 2) + \lambda_1 + 2\lambda_2 x_1 = 0\)
- \(\frac{\partial L}{\partial x_2} = 2(x_2 - 1) + \lambda_1 - \lambda_2 = 0\)
- \(\frac{\partial L}{\partial s_1} = \lambda_1 = 0\)（因为 \(s_1 \geq 0\)，且松弛变量无成本）
- \(\frac{\partial L}{\partial s_2} = \lambda_2 = 0\)
- 原始可行性：\(x_1 + x_2 - 2 + s_1 = 0\), \(x_1^2 - x_2 + s_2 = 0\)
- 互补松弛：\(\lambda_1 s_1 = 0\), \(\lambda_2 s_2 = 0\)
-
分情况讨论
-
情况1：\(\lambda_1 = 0, \lambda_2 = 0\)
从梯度方程得：\(x_1 = 2, x_2 = 1\)
检查约束：\(g_1(2,1) = 2+1-2=1 > 0\)（违反），舍去。 -
情况2：\(\lambda_1 = 0, s_2 = 0\)（即 \(\lambda_2 \neq 0\)）
梯度方程：- \(2(x_1 - 2) + 2\lambda_2 x_1 = 0\)
- \(2(x_2 - 1) - \lambda_2 = 0\)
约束：\(x_1^2 - x_2 = 0\)（因 \(s_2=0\)）
解得：\(x_1 = 1, x_2 = 1, \lambda_2 = 0\)，但此时 \(\lambda_2 = 0\) 与假设矛盾，舍去。
-
情况3：\(s_1 = 0, \lambda_2 = 0\)（即 \(\lambda_1 \neq 0\)）
梯度方程：- \(2(x_1 - 2) + \lambda_1 = 0\)
- \(2(x_2 - 1) + \lambda_1 = 0\)
约束：\(x_1 + x_2 - 2 = 0\)（因 \(s_1=0\)）
解得：\(x_1 = 1, x_2 = 1, \lambda_1 = 2\)
检查 \(g_2(1,1) = 1 - 1 = 0 \leq 0\)，可行。
-
情况4：\(s_1 = 0, s_2 = 0\)（即 \(\lambda_1 \neq 0, \lambda_2 \neq 0\)）
梯度方程：- \(2(x_1 - 2) + \lambda_1 + 2\lambda_2 x_1 = 0\)
- \(2(x_2 - 1) + \lambda_1 - \lambda_2 = 0\)
约束：\(x_1 + x_2 = 2\), \(x_1^2 = x_2\)
代入 \(x_2 = 2 - x_1\) 到 \(x_1^2 = 2 - x_1\)，得 \(x_1^2 + x_1 - 2 = 0\)
解得 \(x_1 = 1\) 或 \(x_1 = -2\)（舍去负值），则 \(x_2 = 1\)
代入梯度方程得 \(\lambda_1 = 2, \lambda_2 = 0\)，与 \(\lambda_2 \neq 0\) 矛盾，舍去。
-
-
最优解验证
唯一可行解为情况3：\(x^* = (1, 1)\)，目标函数值 \(f(1,1) = (1-2)^2 + (1-1)^2 = 1\)
验证约束：\(g_1(1,1) = 0 \leq 0\), \(g_2(1,1) = 0 \leq 0\)，满足。
总结
松弛变量法通过引入松弛变量将不等式约束转化为等式约束，使问题可应用拉格朗日乘数法。求解时需结合KKT条件，分情况讨论乘子和松弛变量的取值，最终找到满足所有条件的最优解。