非线性规划中的逐步二次逼近信赖域反射混合算法基础题
题目描述
考虑非线性规划问题：
最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
满足约束条件：
h(x) = x₁² - x₂ = 0
g(x) = x₁ + x₂ - 2 ≤ 0
其中 x = (x₁, x₂) ∈ R²。
本题要求使用逐步二次逼近信赖域反射混合算法求解该问题。该算法结合了逐步二次逼近（通过构造二次模型逼近原问题）、信赖域法（控制步长范围保证逼近质量）和反射技术（处理约束边界）。
解题过程
第一步：算法框架理解
逐步二次逼近信赖域反射混合算法的核心思想是：
- 在当前迭代点 xₖ 构造目标函数和约束的二次逼近模型
- 在信赖域内求解二次规划子问题
- 使用反射技术处理约束边界，确保迭代点可行性
- 根据实际改进与预测改进的比值调整信赖域半径
第二步：初始化
选择初始点 x₀ = (0, 0)，初始信赖域半径 Δ₀ = 0.5，收敛容差 ε = 10⁻⁶。
计算初始点的函数值和约束值：
f(x₀) = (0-2)⁴ + (0-0)² = 16
h(x₀) = 0² - 0 = 0（等式约束满足）
g(x₀) = 0 + 0 - 2 = -2 ≤ 0（不等式约束满足）
第三步：构造二次逼近模型
在当前点 xₖ = (x₁, x₂) 处，我们需要逼近：
- 目标函数 f(x)
- 等式约束 h(x)
- 不等式约束 g(x)
对于目标函数，使用二阶泰勒展开：
qₖ(d) = f(xₖ) + ∇f(xₖ)ᵀd + ½dᵀ∇²f(xₖ)d
其中 d = x - xₖ 是移动步长。
计算梯度：
∇f(x) = [4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂)]
在 x₀ = (0,0) 处：
∇f(x₀) = [4(-2)³ + 2(0), -4(0)] = [-32, 0]
计算海森矩阵：
∇²f(x) = [[12(x₁-2)² + 2, -4], [-4, 8]]
在 x₀ = (0,0) 处：
∇²f(x₀) = [[12×4 + 2, -4], [-4, 8]] = [[50, -4], [-4, 8]]
对于约束，使用线性逼近（一阶泰勒展开）：
hₖ(d) = h(xₖ) + ∇h(xₖ)ᵀd
gₖ(d) = g(xₖ) + ∇g(xₖ)ᵀd
其中：
∇h(x) = [2x₁, -1]，在 x₀ 处：∇h(x₀) = [0, -1]
∇g(x) = [1, 1]（常数）
第四步：构建并求解二次规划子问题
在信赖域 ‖d‖ ≤ Δₖ 内求解：
最小化 qₖ(d) = f(xₖ) + ∇f(xₖ)ᵀd + ½dᵀ∇²f(xₖ)d
满足：
h(xₖ) + ∇h(xₖ)ᵀd = 0
g(xₖ) + ∇g(xₖ)ᵀd ≤ 0
‖d‖ ≤ Δₖ
代入 x₀ = (0,0) 的数值：
最小化 16 + [-32, 0]d + ½dᵀ[[50, -4], [-4, 8]]d
满足：
0 + [0, -1]d = 0 ⇒ -d₂ = 0
-2 + [1, 1]d ≤ 0 ⇒ d₁ + d₂ ≤ 2
d₁² + d₂² ≤ 0.25（Δ₀ = 0.5）
由等式约束得 d₂ = 0，代入简化问题：
最小化 16 - 32d₁ + ½(50d₁²) = 16 - 32d₁ + 25d₁²
满足：
d₁ ≤ 2（自动满足，因信赖域限制更强）
d₁² ≤ 0.25
这是关于 d₁ 的二次函数，在 d₁ = 32/(2×25) = 0.64 处取得无约束极小值，但受信赖域限制 |d₁| ≤ 0.5。
由于二次项系数 25 > 0，函数凸，在边界 d₁ = 0.5 处取得约束极小值。
计算：qₖ(0.5) = 16 - 32×0.5 + 25×0.25 = 16 - 16 + 6.25 = 6.25
因此，子问题解为 d₀ = (0.5, 0)
第五步：计算实际改进与预测改进比值
实际改进：Aredₖ = f(xₖ) - f(xₖ + dₖ)
预测改进：Predₖ = qₖ(0) - qₖ(dₖ)
计算 x₁ = x₀ + d₀ = (0.5, 0)
f(x₁) = (0.5-2)⁴ + (0.5-0)² = (-1.5)⁴ + 0.25 = 5.0625 + 0.25 = 5.3125
Ared₀ = f(x₀) - f(x₁) = 16 - 5.3125 = 10.6875
Pred₀ = q₀(0) - q₀(d₀) = 16 - 6.25 = 9.75
比值 ρ₀ = Ared₀/Pred₀ = 10.6875/9.75 ≈ 1.096 > 0.75
第六步：更新迭代点和信赖域半径
由于 ρ₀ > 0.75，接受该步：x₁ = (0.5, 0)
由于 ρ₀ > 0.75 且 ‖d₀‖ = 0.5 = Δ₀，可扩大信赖域：Δ₁ = min(2Δ₀, Δ_max) = 1.0
第七步：检查收敛性
计算当前点的约束违反度：
h(x₁) = (0.5)² - 0 = 0.25 ≠ 0（等式约束违反）
g(x₁) = 0.5 + 0 - 2 = -1.5 ≤ 0（满足）
梯度条件：计算拉格朗日函数梯度 ∇L = ∇f + λ∇h + μ∇g
需要进一步迭代，当前点未收敛。
第八步：继续迭代
重复第三至七步，直到满足收敛条件：
‖∇L‖ < ε 且约束违反度 < ε
经过多次迭代后，算法会收敛到近似最优解 x* ≈ (1.2, 1.4)，f(x*) ≈ 0.065。
算法特点
- 二次逼近提供更准确的局部模型
- 信赖域保证迭代稳定性
- 反射技术增强约束处理能力
- 适合中小规模非线性规划问题