非线性规划中的割平面法基础题
题目描述
考虑非线性规划问题：
最小化 \(f(x) = x^2 + 4x + 4\)
满足约束 \(g(x) = x^2 - 4x \leq 0\)。
要求使用割平面法求解该问题，并详细说明每一步的推导过程。
解题过程
1. 问题分析
目标函数 \(f(x) = (x+2)^2\) 是凸函数，约束 \(g(x) = x(x-4) \leq 0\) 定义了一个闭区间 \([0, 4]\)。由于问题规模小，可直接验证最优解为 \(x^* = 0\)（在约束边界上），但此处要求用割平面法演示流程。割平面法的核心思想是通过逐步添加线性约束（割平面）来逼近非线性约束的可行域。
2. 割平面法步骤
步骤1：构造初始松弛问题
将原问题松弛为无约束问题，或保留部分简单约束。本例中，约束 \(g(x) \leq 0\) 是非线性的，需用线性割平面逼近。初始问题可设为：
最小化 \(f(x)\)，满足 \(x \in \mathbb{R}\)（无约束）。
求解得初始点 \(x_0 = -2\)（无约束极小点），但此点不满足 \(g(x) \leq 0\)（因 \(g(-2) = 12 > 0\)）。
步骤2：生成割平面
在不可行点 \(x_0 = -2\) 处，对非线性约束 \(g(x) \leq 0\) 进行线性化：
- 计算梯度 \(\nabla g(x) = 2x - 4\)，在 \(x_0 = -2\) 处得 \(\nabla g(-2) = -8\)。
- 线性逼近：
\[ g(x) \approx g(-2) + \nabla g(-2)(x - (-2)) = 12 - 8(x + 2) = -8x - 4. \]
- 割平面条件：要求 \(g(x) \leq 0\)，但当前逼近在 \(x_0\) 处有 \(g(-2) = 12 > 0\)，因此添加约束
\[ -8x - 4 \leq 0 \quad \Rightarrow \quad x \geq -0.5. \]
此即为第一个割平面，切掉不可行区域 \(x < -0.5\)。
步骤3：求解带割平面的子问题
新的子问题：
最小化 \(f(x) = x^2 + 4x + 4\)，满足 \(x \geq -0.5\)。
- 拉格朗日函数： \(L(x, \lambda) = f(x) - \lambda (x + 0.5)\)，其中 \(\lambda \geq 0\)。
- KKT 条件：
\[ \frac{\partial L}{\partial x} = 2x + 4 - \lambda = 0, \quad \lambda (x + 0.5) = 0. \]
- 若 \(\lambda = 0\)，则 \(2x + 4 = 0\) 得 \(x = -2\)，但此点不满足 \(x \geq -0.5\)，舍去。
- 若 \(x = -0.5\)，则 \(\lambda = 2(-0.5) + 4 = 3 \geq 0\)，符合条件。
子问题解为 \(x_1 = -0.5\)，此时 \(g(x_1) = (-0.5)^2 - 4(-0.5) = 0.25 + 2 = 2.25 > 0\)，仍不可行。
步骤4：迭代添加割平面
在 \(x_1 = -0.5\) 处再次线性化 \(g(x)\)：
- \(\nabla g(-0.5) = 2(-0.5) - 4 = -5\)。
- 线性逼近：
\[ g(x) \approx g(-0.5) + \nabla g(-0.5)(x + 0.5) = 2.25 - 5(x + 0.5) = -5x - 0.25. \]
- 添加割平面：
\[ -5x - 0.25 \leq 0 \quad \Rightarrow \quad x \geq -0.05. \]
新子问题：最小化 \(f(x)\)，满足 \(x \geq -0.5\) 且 \(x \geq -0.05\)。合并约束得 \(x \geq -0.05\)。
求解该问题：
- KKT 条件：若 \(x > -0.05\)，则 \(\lambda = 0\)，解得 \(x = -2\)（不可行）；若 \(x = -0.05\)，则 \(\lambda = 2(-0.05) + 4 = 3.9 \geq 0\)。
得 \(x_2 = -0.05\)，检查 \(g(x_2) = (-0.05)^2 - 4(-0.05) = 0.0025 + 0.2 = 0.2025 > 0\)，仍不可行。
步骤5：继续迭代
在 \(x_2 = -0.05\) 处线性化：
- \(\nabla g(-0.05) = 2(-0.05) - 4 = -4.1\)。
- 线性逼近：
\[ g(x) \approx 0.2025 - 4.1(x + 0.05) = -4.1x - 0.0025. \]
- 割平面：
\[ -4.1x - 0.0025 \leq 0 \quad \Rightarrow \quad x \geq -0.00061. \]
新子问题约束为 \(x \geq -0.00061\)，解为 \(x_3 = -0.00061\)。此时 \(g(x_3) \approx 0.00000037 + 0.00244 \approx 0.00244 > 0\)，但已非常接近 0。
步骤6：收敛判断
重复迭代，割平面会不断逼近 \(x \geq 0\)（因 \(g(x) \leq 0\) 等价于 \(0 \leq x \leq 4\)）。当 \(x_k\) 足够接近 0 时（如 \(|g(x_k)| < \epsilon\)），停止迭代。最终解为 \(x^* = 0\)，对应 \(f(0) = 4\)。
3. 算法总结
割平面法通过逐步添加线性约束逼近非线性约束的可行域。每次在不可行点线性化约束，生成割平面排除部分不可行区域，直至找到可行解。本例中，经过多次迭代，割平面从右侧逼近真实可行域边界 \(x = 0\)。