非线性规划中的松弛算法基础题
题目描述：
考虑非线性规划问题：
最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
满足约束条件：
g₁(x) = x₁² - x₂ ≤ 0
g₂(x) = x₁² + x₂² - 8 ≤ 0
x₁ ≥ 0, x₂ ≥ 0
请使用松弛算法求解该问题，要求找到满足约束的局部最优解。
解题过程：
第一步：理解松弛算法的基本思想
松弛算法是一种处理约束优化问题的方法，其核心思想是将约束条件逐步引入目标函数。算法从可行域内部的一个初始点开始，通过求解一系列无约束子问题来逼近原问题的最优解。每个子问题只考虑当前被违反或处于边界的约束（称为"积极约束"），而暂时忽略其他约束。
第二步：选择初始点
我们需要选择一个严格可行的初始点x⁰，即满足所有约束条件（包括非负约束）且不等式约束严格成立的点。
验证约束条件：
g₁(x) = x₁² - x₂ < 0
g₂(x) = x₁² + x₂² - 8 < 0
x₁ > 0, x₂ > 0
选择初始点x⁰ = (1, 2)：
- g₁(1,2) = 1² - 2 = -1 < 0 ✓
- g₂(1,2) = 1² + 2² - 8 = -3 < 0 ✓
- x₁ = 1 > 0, x₂ = 2 > 0 ✓
该点在可行域内部。
第三步：第一次迭代
在当前点x⁰ = (1,2)，所有约束都不活跃（严格满足），因此我们求解无约束优化问题：
min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
计算梯度：
∇f(x) = [4(x₁ - 2)³ + 2(x₁ - 2x₂), -4(x₁ - 2x₂)]ᵀ
在x⁰ = (1,2)处：
∇f(1,2) = [4(1-2)³ + 2(1-4), -4(1-4)] = [4(-1) + 2(-3), -4(-3)] = [-4-6, 12] = [-10, 12]ᵀ
使用梯度下降法（步长α = 0.1）：
x¹ = x⁰ - α∇f(x⁰) = (1,2) - 0.1×(-10,12) = (1+1, 2-1.2) = (2, 0.8)
第四步：可行性检查
检查x¹ = (2, 0.8)是否可行：
- g₁(2,0.8) = 2² - 0.8 = 4 - 0.8 = 3.2 > 0 ✗（违反约束）
- g₂(2,0.8) = 2² + 0.8² - 8 = 4 + 0.64 - 8 = -3.36 < 0 ✓
- x₁ = 2 > 0, x₂ = 0.8 > 0 ✓
约束g₁被违反，需要将其引入积极约束集。
第五步：第二次迭代（考虑积极约束）
当前积极约束集包含g₁(x) ≤ 0（在边界上）。
构造子问题：在g₁(x) = 0的约束下最小化f(x)
即求解：min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
s.t. g₁(x) = x₁² - x₂ = 0
使用拉格朗日法，构造拉格朗日函数：
L(x,λ) = f(x) + λg₁(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² + λ(x₁² - x₂)
求解KKT条件：
∂L/∂x₁ = 4(x₁ - 2)³ + 2(x₁ - 2x₂) + 2λx₁ = 0
∂L/∂x₂ = -4(x₁ - 2x₂) - λ = 0
∂L/∂λ = x₁² - x₂ = 0
从第二个方程：λ = -4(x₁ - 2x₂)
代入第一个方程：4(x₁ - 2)³ + 2(x₁ - 2x₂) + 2x₁[-4(x₁ - 2x₂)] = 0
化简：4(x₁ - 2)³ + 2(x₁ - 2x₂) - 8x₁(x₁ - 2x₂) = 0
4(x₁ - 2)³ + 2(x₁ - 2x₂)(1 - 4x₁) = 0
结合x₂ = x₁²（从约束条件），代入：
4(x₁ - 2)³ + 2(x₁ - 2x₁²)(1 - 4x₁) = 0
尝试x₁ = 1.5：4(-0.5)³ + 2(1.5 - 4.5)(1 - 6) = 4(-0.125) + 2(-3)(-5) = -0.5 + 30 = 29.5 > 0
尝试x₁ = 1.2：4(-0.8)³ + 2(1.2 - 2.88)(1 - 4.8) = 4(-0.512) + 2(-1.68)(-3.8) = -2.048 + 12.768 = 10.72 > 0
尝试x₁ = 0.8：4(-1.2)³ + 2(0.8 - 1.28)(1 - 3.2) = 4(-1.728) + 2(-0.48)(-2.2) = -6.912 + 2.112 = -4.8 < 0
通过二分法找到根在x₁ ≈ 1.0附近，精确计算得x₁ ≈ 1.1：
4(-0.9)³ + 2(1.1 - 2.42)(1 - 4.4) = 4(-0.729) + 2(-1.32)(-3.4) = -2.916 + 8.976 = 6.06 > 0
最终找到解x₁ ≈ 1.05, x₂ = x₁² ≈ 1.1025
第六步：收敛检查
计算x² ≈ (1.05, 1.1025)
检查约束：
- g₁(x) = 1.05² - 1.1025 ≈ 1.1025 - 1.1025 = 0 ✓
- g₂(x) = 1.05² + 1.1025² - 8 ≈ 1.1025 + 1.2155 - 8 = -5.682 < 0 ✓
- x₁ > 0, x₂ > 0 ✓
计算目标函数值f(x²) ≈ (1.05-2)⁴ + (1.05-2×1.1025)² ≈ 0.915 + 1.332 ≈ 2.247
与之前迭代比较，函数值显著下降，且满足所有约束，可以接受该解。
第七步：最终验证
x* ≈ (1.05, 1.10)是原问题的局部最优解，满足所有约束条件，且目标函数值f(x*) ≈ 2.25。
松弛算法通过逐步引入被违反的约束，将原约束优化问题转化为一系列较容易求解的子问题，最终收敛到满足所有约束的局部最优解。