非线性规划中的逐步二次逼近法基础题
题目描述
考虑非线性规划问题：
最小化 f(x) = x₁² + 2x₂² - 4x₁ - 8x₂ + 10
满足约束条件：x₁ + x₂ ≤ 3
其中 x = (x₁, x₂) ∈ R²
这是一个带不等式约束的二次规划问题，我们将使用逐步二次逼近法（SQA）求解，该方法通过迭代求解一系列二次规划子问题来逼近原问题的最优解。
解题过程
第一步：理解逐步二次逼近法的基本思想
逐步二次逼近法的核心是将复杂的非线性规划问题转化为一系列较易求解的二次规划子问题。每个子问题通过在当前迭代点对目标函数和约束函数进行二次近似得到，通过求解这些二次规划子问题，逐步逼近原问题的最优解。
第二步：准备迭代所需的一阶和二阶导数信息
目标函数 f(x) = x₁² + 2x₂² - 4x₁ - 8x₂ + 10
梯度：∇f(x) = [2x₁ - 4, 4x₂ - 8]ᵀ
Hessian矩阵：H = [[2, 0], [0, 4]]（常数矩阵）
约束函数 g(x) = x₁ + x₂ - 3 ≤ 0
梯度：∇g(x) = [1, 1]ᵀ
Hessian矩阵：零矩阵（线性约束）
第四步：选择初始点并开始迭代
我们选择初始点 x⁰ = (0, 0)，该点满足约束条件。
第一次迭代（k=0）
在当前点 x⁰ = (0, 0) 构建二次近似：
目标函数二次近似：f₀(x) ≈ f(x⁰) + ∇f(x⁰)ᵀ(x - x⁰) + ½(x - x⁰)ᵀH(x - x⁰)
= 10 + [-4, -8]·[x₁, x₂]ᵀ + ½[x₁, x₂]·[[2,0],[0,4]]·[x₁, x₂]ᵀ
= x₁² + 2x₂² - 4x₁ - 8x₂ + 10
约束函数线性近似：g₀(x) ≈ g(x⁰) + ∇g(x⁰)ᵀ(x - x⁰)
= -3 + [1, 1]·[x₁, x₂]ᵀ = x₁ + x₂ - 3 ≤ 0
求解二次规划子问题：
最小化 q₀(x) = x₁² + 2x₂² - 4x₁ - 8x₂ + 10
满足 x₁ + x₂ ≤ 3
使用拉格朗日法求解，拉格朗日函数：
L(x,λ) = x₁² + 2x₂² - 4x₁ - 8x₂ + 10 + λ(x₁ + x₂ - 3)
KKT条件：
∂L/∂x₁ = 2x₁ - 4 + λ = 0
∂L/∂x₂ = 4x₂ - 8 + λ = 0
λ(x₁ + x₂ - 3) = 0, λ ≥ 0, x₁ + x₂ ≤ 3
情况1：λ = 0（约束不起作用）
解得 x₁ = 2, x₂ = 2，但 x₁ + x₂ = 4 > 3，违反约束
情况2：λ > 0（约束起作用）
x₁ + x₂ = 3
联立方程解得：x₁ = 5/3, x₂ = 4/3, λ = 2/3
得到新迭代点 x¹ = (5/3, 4/3) ≈ (1.667, 1.333)
第五步：检查收敛条件并继续迭代
计算目标函数值变化：f(x⁰) = 10, f(x¹) = (5/3)² + 2(4/3)² - 4(5/3) - 8(4/3) + 10 = 1/3
变化显著，需要继续迭代。
第二次迭代（k=1）
在当前点 x¹ = (5/3, 4/3) 构建二次近似：
目标函数二次近似与第一次相同（因为Hessian是常数）
约束函数线性近似：g₁(x) ≈ x₁ + x₂ - 3 ≤ 0
求解二次规划子问题得到与第一次相同的最优解 x² = (5/3, 4/3)
由于 x² = x¹，算法收敛。
第六步：验证最优性
最终解 x* = (5/3, 4/3)
目标函数值 f(x*) = 1/3
梯度 ∇f(x*) = [2/3, -8/3]ᵀ
约束梯度 ∇g(x*) = [1, 1]ᵀ
满足KKT条件：存在 λ* = 2/3 > 0，使得 ∇f(x*) + λ*∇g(x*) = 0
且 λg(x) = 0，g(x*) = 0
结论
通过两次迭代，逐步二次逼近法找到了原问题的最优解 x* = (5/3, 4/3)，目标函数最小值为 1/3。该方法通过求解简单的二次规划子问题，有效处理了带约束的非线性优化问题。