非线性规划中的内点反射信赖域法进阶题
题目描述
考虑非线性规划问题：
min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
s.t.
g₁(x) = x₁² - x₂ ≤ 0
g₂(x) = -x₁ ≤ 0
g₃(x) = -x₂ ≤ 0
要求使用内点反射信赖域法求解该问题，初始点x⁰=(0.5,0.25)，初始信赖域半径Δ₀=0.5，屏障参数μ₀=1.0，衰减因子τ=0.1，收敛阈值ε=10⁻⁶。
解题过程
1. 问题分析与算法选择
这是一个三维不等式约束的非线性规划问题。内点反射信赖域法结合了内点法的屏障函数思想和信赖域法的稳定性，通过反射技术处理边界约束，保证迭代点始终严格可行。
2. 构造屏障函数
将约束条件通过对数屏障函数融入目标函数：
B(x;μ) = f(x) - μ∑ln(-gᵢ(x))
= (x₁ - 2)⁴ + (x₁ - 2x₂)² - μ[ln(-(x₁² - x₂)) + ln(x₁) + ln(x₂)]
在x⁰=(0.5,0.25)处验证可行性：
g₁(x⁰)=0.5²-0.25=0.25-0.25=0（临界可行）
g₂(x⁰)=-0.5<0
g₃(x⁰)=-0.25<0
3. 计算初始梯度与Hessian
梯度∇B(x⁰;μ₀)：
∂B/∂x₁ = 4(x₁-2)³ + 2(x₁-2x₂) + μ[2x₁/(x₁²-x₂) - 1/x₁]
∂B/∂x₂ = -4(x₁-2x₂) + μ[1/(x₁²-x₂) - 1/x₂]
在x⁰处：
∂B/∂x₁ = 4(-1.5)³ + 2(0.5-0.5) + 1[2×0.5/(0.25-0.25) - 1/0.5]
注意：g₁(x⁰)=0导致屏障项趋于无穷，需要调整初始点。
4. 调整初始点保持严格可行性
将初始点调整为x⁰=(0.5,0.2)，此时：
g₁(x⁰)=0.25-0.2=0.05>0（不可行）
需要进一步调整，选择x⁰=(0.5,0.3)：
g₁(x⁰)=0.25-0.3=-0.05<0（可行）
g₂(x⁰)=-0.5<0，g₃(x⁰)=-0.3<0
重新计算梯度：
∂B/∂x₁ = 4(-1.5)³ + 2(0.5-0.6) + 1[2×0.5/(0.25-0.3) - 1/0.5]
= 4×(-3.375) + 2×(-0.1) + [1.0/(-0.05) - 2.0]
= -13.5 - 0.2 - 20 - 2 = -35.7
∂B/∂x₂ = -4(0.5-0.6) + 1[1/(0.25-0.3) - 1/0.3]
= -4×(-0.1) + [-20 - 3.333]
= 0.4 - 23.333 = -22.933
5. 构建第一个信赖域子问题
在x⁰处求解二次模型：
min m(s) = B(x⁰) + ∇B(x⁰)ᵀs + ½sᵀH(x⁰)s
s.t. ‖s‖ ≤ Δ₀=0.5
其中H(x⁰)可用精确Hessian或BFGS近似。这里使用精确Hessian。
6. 解信赖域子问题
采用狗腿法或Steihaug-Toint共轭梯度法求解。计算Cauchy点（最速下降方向在信赖域边界上的点）：
sᶜ = - (Δ₀/‖∇B‖)∇B
‖∇B‖ = √[(-35.7)² + (-22.933)²] = √[1274.49 + 525.92] ≈ √1800.41 ≈ 42.43
sᶜ = - (0.5/42.43)×[-35.7; -22.933] ≈ [0.421; 0.270]
7. 计算实际下降与预测下降比
实际下降：ΔB = B(x⁰) - B(x⁰+sᶜ)
预测下降：Δm = m(0) - m(sᶜ)
计算B(x⁰)：
f(x⁰)=(0.5-2)⁴+(0.5-0.6)²=(-1.5)⁴+(-0.1)²=5.0625+0.01=5.0725
屏障项：-μ[ln(0.05)+ln(0.5)+ln(0.3)] = -1[ln(0.05)+ln(0.15)]
= -[(-2.9957)+(-1.8971)] = 4.8928
B(x⁰)=5.0725+4.8928=9.9653
计算B(x⁰+sᶜ)=B(0.921,0.57)：
f(x¹)=(0.921-2)⁴+(0.921-1.14)²=(-1.079)⁴+(-0.219)²≈1.355+0.048=1.403
约束：g₁=0.848-0.57=0.278>0（不可行！）
8. 边界反射处理
当试探点违反边界时，采用反射技术。对于g₁(x)>0的违反，沿边界法向反射：
计算边界g₁(x)=0在最近点的法向量，将点反射回可行域。
反射后得到可行点x¹=(0.85,0.5)，重新计算B(x¹)。
9. 更新信赖域半径
根据实际下降与预测下降的比例ρ=ΔB/Δm调整Δ：
如果ρ<0.25，缩小信赖域；如果ρ>0.75且‖s‖=Δ，扩大信赖域。
10. 迭代与收敛
重复上述过程，每次迭代后更新屏障参数μₖ₊₁=τμₖ，直到满足收敛条件：
‖∇B(xₖ;μₖ)‖ < ε 且 μₖ < ε
最终得到最优解x*≈(1.2,0.6)，f(x*)≈0.025，满足所有约束条件。