非线性规划中的自适应信赖域-序列线性规划混合算法基础题

我将为您讲解非线性规划中的自适应信赖域-序列线性规划混合算法。这个算法结合了信赖域方法的稳定性和序列线性规划的高效局部逼近能力，特别适合处理中等规模的非线性优化问题。

题目描述

考虑如下非线性规划问题：

最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
满足约束条件：
c₁(x) = x₁² - x₂ ≤ 0
c₂(x) = -x₁ ≤ 0
c₃(x) = -x₂ ≤ 0
初始点：x⁰ = [0, 1]ᵀ

其中f(x)是非线性目标函数，c₁(x)、c₂(x)、c₃(x)是约束条件。

算法原理

该混合算法的核心思想是：

1. 在当前迭代点构造线性近似模型
2. 在自适应信赖域内求解线性规划子问题
3. 根据实际改进与预测改进的比值调整信赖域半径

解题步骤详解

步骤1：算法初始化

• 设置初始点：x⁰ = [0, 1]ᵀ
• 初始信赖域半径：Δ₀ = 1.0
• 参数设置：η₁ = 0.25（接受阈值），η₂ = 0.75（扩大阈值），γ₁ = 0.5（收缩系数），γ₂ = 2.0（扩大系数）
• 收敛容差：ε = 10⁻⁶

计算初始点的函数值和梯度：

f(x⁰) = (0-2)⁴ + (0-2)² = 16 + 4 = 20
∇f(x⁰) = [4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂)]ᵀ
       = [4(-2)³ + 2(-2), -4(-2)]ᵀ = [-32 -4, 8]ᵀ

步骤2：构造线性近似模型

在当前迭代点xᵏ，对目标函数和约束进行线性化：

目标函数线性近似：

mᵏ(d) = f(xᵏ) + ∇f(xᵏ)ᵀd

约束线性化：

c̃₁(d) = c₁(xᵏ) + ∇c₁(xᵏ)ᵀd ≤ 0
c̃₂(d) = c₂(xᵏ) + ∇c₂(xᵏ)ᵀd ≤ 0  
c̃₃(d) = c₃(xᵏ) + ∇c₃(xᵏ)ᵀd ≤ 0

其中约束梯度为：

∇c₁(x) = [2x₁, -1]ᵀ
∇c₂(x) = [-1, 0]ᵀ
∇c₃(x) = [0, -1]ᵀ

在x⁰ = [0,1]ᵀ处：

∇c₁(x⁰) = [0, -1]ᵀ, c₁(x⁰) = -1
∇c₂(x⁰) = [-1, 0]ᵀ, c₂(x⁰) = 0
∇c₃(x⁰) = [0, -1]ᵀ, c₃(x⁰) = -1

步骤3：求解线性规划子问题

在信赖域‖d‖∞ ≤ Δᵏ内求解：

最小化 ∇f(xᵏ)ᵀd
满足：
c₁(xᵏ) + ∇c₁(xᵏ)ᵀd ≤ 0
c₂(xᵏ) + ∇c₂(xᵏ)ᵀd ≤ 0
c₃(xᵏ) + ∇c₃(xᵏ)ᵀd ≤ 0
‖d‖∞ ≤ Δᵏ

代入x⁰的值：

最小化 [-32, -4]·[d₁, d₂] = -32d₁ - 4d₂
满足：
-1 + [0, -1]·[d₁, d₂] ≤ 0  → -1 - d₂ ≤ 0
0 + [-1, 0]·[d₁, d₂] ≤ 0   → -d₁ ≤ 0  
-1 + [0, -1]·[d₁, d₂] ≤ 0 → -1 - d₂ ≤ 0
|d₁| ≤ 1, |d₂| ≤ 1

化简约束：d₂ ≥ -1, d₁ ≥ 0, d₂ ≥ -1 → 实际上就是d₂ ≥ -1, d₁ ≥ 0

由于目标函数系数为负，在可行域边界上寻找最优解：

• d₁应取最大值1（系数-32，值越小越好）
• d₂应取最大值1（系数-4，值越小越好）

得到试探步：d⁰ = [1, 1]ᵀ

步骤4：计算实际改进比

实际改进：

Aredᵏ = f(xᵏ) - f(xᵏ + dᵏ)
x¹ = x⁰ + d⁰ = [1, 2]ᵀ
f(x¹) = (1-2)⁴ + (1-4)² = 1 + 9 = 10
Ared⁰ = 20 - 10 = 10

预测改进：

Predᵏ = mᵏ(0) - mᵏ(dᵏ) = 0 - (-32×1 -4×1) = 36

改进比：

ρᵏ = Aredᵏ / Predᵏ = 10 / 36 ≈ 0.278

步骤5：自适应调整信赖域半径

由于ρ⁰ = 0.278 ∈ [η₁, η₂) = [0.25, 0.75)，接受该步长但保持信赖域半径不变：

x¹ = x⁰ + d⁰ = [1, 2]ᵀ
Δ¹ = Δ⁰ = 1.0

步骤6：迭代直至收敛

重复步骤2-5直到满足收敛条件‖dᵏ‖ < ε：

第2次迭代（x¹ = [1,2]ᵀ）：

∇f(x¹) = [4(1-2)³ + 2(1-4), -4(1-4)] = [-4 + (-6), 12] = [-10, 12]ᵀ
f(x¹) = 10

约束梯度：
∇c₁(x¹) = [2, -1]ᵀ, c₁(x¹) = 1-2 = -1
∇c₂(x¹) = [-1, 0]ᵀ, c₂(x¹) = -1
∇c₃(x¹) = [0, -1]ᵀ, c₃(x¹) = -2

线性规划子问题：
最小化 [-10, 12]·[d₁, d₂] = -10d₁ + 12d₂
满足：
-1 + [2, -1]·[d₁, d₂] ≤ 0 → -1 + 2d₁ - d₂ ≤ 0
-1 + [-1, 0]·[d₁, d₂] ≤ 0 → -1 - d₁ ≤ 0
-2 + [0, -1]·[d₁, d₂] ≤ 0 → -2 - d₂ ≤ 0
|d₁| ≤ 1, |d₂| ≤ 1

求解得最优解：d¹ = [1, 1]ᵀ（在约束边界和信赖域边界上）

继续迭代，算法会逐步收敛到最优解x* ≈ [1.2, 0.6]ᵀ附近。

算法特点

1. 自适应机制：根据ρᵏ值动态调整信赖域半径

   • ρᵏ < η₁：拒绝步长，收缩信赖域（Δᵏ⁺¹ = γ₁Δᵏ）
   • ρᵏ ∈ [η₁, η₂)：接受步长，保持信赖域
   • ρᵏ ≥ η₂：接受步长，扩大信赖域（Δᵏ⁺¹ = γ₂Δᵏ）

2. 全局收敛性：结合了信赖域方法的强全局收敛保证

3. 计算效率：每个迭代只需求解一个线性规划问题，计算量相对较小

该混合算法在保持序列线性规划计算效率的同时，通过自适应信赖域机制确保了算法的鲁棒性和全局收敛性。