非线性规划中的信赖域反射正割法基础题

字数 3019 2025-11-03 18:00:43

非线性规划中的信赖域反射正割法基础题

题目描述
考虑非线性规划问题：
min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
其中 x = (x₁, x₂) ∈ R²。该问题无约束，但目标函数高度非线性，在极小点附近呈现强曲率特性。请使用信赖域反射正割法求解该问题，初始点设为 x⁰ = (0.0, 3.0)，初始信赖域半径 Δ₀ = 0.5，初始正割矩阵 B₀ 为单位矩阵。收敛准则为梯度范数 ||∇f(x)|| < 1e-6。

解题过程循序渐进讲解

第一步：理解算法框架
信赖域反射正割法结合了三种技术：

正割法（拟牛顿法）：用正割方程更新近似Hessian矩阵 Bₖ，避免计算二阶导数
信赖域法：在每次迭代中构造一个局部模型，并在一个可信区域（信赖域）内求解该模型的极小点
反射技术：当试探步到达信赖域边界时，通过反射处理可能产生的无效步，提高收敛效率

基本迭代格式为：

构造二次模型：mₖ(p) = f(xₖ) + ∇f(xₖ)ᵀp + ½pᵀBₖp
在信赖域 ||p|| ≤ Δₖ 内求解 min mₖ(p)
计算实际下降量 Δfₖ = f(xₖ) - f(xₖ + pₖ)
计算预测下降量 Δmₖ = mₖ(0) - mₖ(pₖ)
根据比值 ρₖ = Δfₖ/Δmₖ 调整信赖域半径和接受试探步

第二步：计算初始点信息
在 x⁰ = (0.0, 3.0) 处：

梯度 ∇f(x) = [4(x₁ - 2)³ + 2(x₁ - 2x₂), -4(x₁ - 2x₂)]
∇f(x⁰) = [4(0-2)³ + 2(0-6), -4(0-6)] = [4×(-8) + 2×(-6), 24] = [-32 - 12, 24] = [-44, 24]
梯度范数 ||∇f(x⁰)|| = √((-44)² + 24²) = √(1936 + 576) = √2512 ≈ 50.12 > 1e-6，需要继续迭代
初始正割矩阵 B₀ = I（单位矩阵）

第三步：第一次迭代求解试探步
构造二次模型：m₀(p) = f(x⁰) + ∇f(x⁰)ᵀp + ½pᵀB₀p
在信赖域 ||p|| ≤ Δ₀ = 0.5 内求解 min m₀(p)

由于 B₀ = I 是正定矩阵，该问题是标准信赖域问题。当全步（无约束极小点）在信赖域内时，接受全步；否则，解在信赖域边界上。

计算无约束极小点：p* = -B₀⁻¹∇f(x⁰) = -∇f(x⁰) = [44, -24]
||p*|| = √(44² + (-24)²) = √(1936 + 576) = √2512 ≈ 50.12 > Δ₀ = 0.5

因此，解在信赖域边界上，需解带约束的优化问题。对于球约束，解的形式为 p₀ = -(B₀ + λI)⁻¹∇f(x⁰)，其中 λ 使 ||p₀|| = Δ₀。

由于 B₀ = I，有 p₀ = -(1+λ)⁻¹∇f(x⁰)，||p₀|| = ||∇f(x⁰)||/(1+λ) = Δ₀
解得 1+λ = ||∇f(x⁰)||/Δ₀ ≈ 50.12/0.5 = 100.24
λ ≈ 99.24
p₀ = -∇f(x⁰)/(1+λ) ≈ [44, -24]/100.24 ≈ [0.439, -0.239]

第四步：评估试探步并更新
计算试探点：x¹ = x⁰ + p₀ ≈ [0.0, 3.0] + [0.439, -0.239] = [0.439, 2.761]

计算函数值：

f(x⁰) = (0-2)⁴ + (0-6)² = 16 + 36 = 52
f(x¹) ≈ (0.439-2)⁴ + (0.439-2×2.761)² = (-1.561)⁴ + (0.439-5.522)² ≈ 5.94 + (-5.083)² ≈ 5.94 + 25.84 = 31.78

实际下降量：Δf₀ = f(x⁰) - f(x¹) ≈ 52 - 31.78 = 20.22
预测下降量：Δm₀ = m₀(0) - m₀(p₀) = 0 - [∇f(x⁰)ᵀp₀ + ½p₀ᵀB₀p₀]
∇f(x⁰)ᵀp₀ ≈ [-44, 24]·[0.439, -0.239] = -19.32 - 5.74 = -25.06
p₀ᵀB₀p₀ = p₀ᵀp₀ ≈ 0.439² + (-0.239)² ≈ 0.193 + 0.057 = 0.25
Δm₀ ≈ -[-25.06 + ½×0.25] = 25.06 - 0.125 = 24.935

比值 ρ₀ = Δf₀/Δm₀ ≈ 20.22/24.935 ≈ 0.811

由于 ρ₀ > 0.75（典型阈值），接受试探步：x¹ = [0.439, 2.761]
由于 ρ₀ > 0.75 且 ||p₀|| = Δ₀（步在边界上），扩大信赖域：Δ₁ = 2×Δ₀ = 1.0

第五步：更新正割矩阵
正割方程要求 Bₖ₊₁sₖ = yₖ，其中 sₖ = x¹ - x⁰ ≈ [0.439, -0.239]，yₖ = ∇f(x¹) - ∇f(x⁰)

计算 ∇f(x¹)：
∇f(x¹) ≈ [4(0.439-2)³ + 2(0.439-2×2.761), -4(0.439-2×2.761)]
= [4×(-1.561)³ + 2×(0.439-5.522), -4×(0.439-5.522)]
≈ [4×(-3.80) + 2×(-5.083), -4×(-5.083)]
≈ [-15.20 - 10.166, 20.332] ≈ [-25.366, 20.332]

y₀ = ∇f(x¹) - ∇f(x⁰) ≈ [-25.366, 20.332] - [-44, 24] = [18.634, -3.668]

使用BFGS公式更新正割矩阵：
B₁ = B₀ - (B₀s₀)(B₀s₀)ᵀ/(s₀ᵀB₀s₀) + y₀y₀ᵀ/(s₀ᵀy₀)

计算各项：
B₀s₀ = I×s₀ = s₀ ≈ [0.439, -0.239]
s₀ᵀB₀s₀ = s₀ᵀs₀ ≈ 0.439² + (-0.239)² ≈ 0.193 + 0.057 = 0.25
s₀ᵀy₀ ≈ [0.439, -0.239]·[18.634, -3.668] ≈ 8.18 + 0.876 ≈ 9.056

B₁ ≈ I - ([0.439, -0.239][0.439, -0.239]ᵀ)/0.25 + ([18.634, -3.668][18.634, -3.668]ᵀ)/9.056

第六步：继续迭代至收敛
重复上述过程：

用当前 Bₖ 和 Δₖ 求解信赖域子问题得试探步 pₖ
计算 ρₖ = Δfₖ/Δmₖ
根据 ρₖ 调整信赖域半径和决定是否接受试探步
用BFGS公式更新正割矩阵 Bₖ₊₁

经过多次迭代后，解会收敛到真解 x* ≈ [2.0, 1.0]，此时 f(x*) = 0，∇f(x*) = [0, 0]。

该算法通过正割法近似Hessian，避免了二阶导数计算；通过信赖域法保证稳定性；反射技术处理边界情况提高效率。对于此强非线性问题，能有效收敛到全局极小点。

非线性规划中的信赖域反射正割法基础题题目描述考虑非线性规划问题： min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 其中 x = (x₁, x₂) ∈ R²。该问题无约束，但目标函数高度非线性，在极小点附近呈现强曲率特性。请使用信赖域反射正割法求解该问题，初始点设为 x⁰ = (0.0, 3.0)，初始信赖域半径 Δ₀ = 0.5，初始正割矩阵 B₀ 为单位矩阵。收敛准则为梯度范数 ||∇f(x)|| < 1e-6。解题过程循序渐进讲解第一步：理解算法框架信赖域反射正割法结合了三种技术：正割法（拟牛顿法）：用正割方程更新近似Hessian矩阵 Bₖ，避免计算二阶导数信赖域法：在每次迭代中构造一个局部模型，并在一个可信区域（信赖域）内求解该模型的极小点反射技术：当试探步到达信赖域边界时，通过反射处理可能产生的无效步，提高收敛效率基本迭代格式为：构造二次模型：mₖ(p) = f(xₖ) + ∇f(xₖ)ᵀp + ½pᵀBₖp 在信赖域 ||p|| ≤ Δₖ 内求解 min mₖ(p) 计算实际下降量 Δfₖ = f(xₖ) - f(xₖ + pₖ) 计算预测下降量 Δmₖ = mₖ(0) - mₖ(pₖ) 根据比值 ρₖ = Δfₖ/Δmₖ 调整信赖域半径和接受试探步第二步：计算初始点信息在 x⁰ = (0.0, 3.0) 处：梯度 ∇f(x) = [ 4(x₁ - 2)³ + 2(x₁ - 2x₂), -4(x₁ - 2x₂) ] ∇f(x⁰) = [ 4(0-2)³ + 2(0-6), -4(0-6)] = [ 4×(-8) + 2×(-6), 24] = [ -32 - 12, 24] = [ -44, 24 ] 梯度范数 ||∇f(x⁰)|| = √((-44)² + 24²) = √(1936 + 576) = √2512 ≈ 50.12 > 1e-6，需要继续迭代初始正割矩阵 B₀ = I（单位矩阵）第三步：第一次迭代求解试探步构造二次模型：m₀(p) = f(x⁰) + ∇f(x⁰)ᵀp + ½pᵀB₀p 在信赖域 ||p|| ≤ Δ₀ = 0.5 内求解 min m₀(p) 由于 B₀ = I 是正定矩阵，该问题是标准信赖域问题。当全步（无约束极小点）在信赖域内时，接受全步；否则，解在信赖域边界上。计算无约束极小点：p* = -B₀⁻¹∇f(x⁰) = -∇f(x⁰) = [ 44, -24 ] ||p* || = √(44² + (-24)²) = √(1936 + 576) = √2512 ≈ 50.12 > Δ₀ = 0.5 因此，解在信赖域边界上，需解带约束的优化问题。对于球约束，解的形式为 p₀ = -(B₀ + λI)⁻¹∇f(x⁰)，其中 λ 使 ||p₀|| = Δ₀。由于 B₀ = I，有 p₀ = -(1+λ)⁻¹∇f(x⁰)，||p₀|| = ||∇f(x⁰)||/(1+λ) = Δ₀ 解得 1+λ = ||∇f(x⁰)||/Δ₀ ≈ 50.12/0.5 = 100.24 λ ≈ 99.24 p₀ = -∇f(x⁰)/(1+λ) ≈ [ 44, -24]/100.24 ≈ [ 0.439, -0.239 ] 第四步：评估试探步并更新计算试探点：x¹ = x⁰ + p₀ ≈ [ 0.0, 3.0] + [ 0.439, -0.239] = [ 0.439, 2.761 ] 计算函数值： f(x⁰) = (0-2)⁴ + (0-6)² = 16 + 36 = 52 f(x¹) ≈ (0.439-2)⁴ + (0.439-2×2.761)² = (-1.561)⁴ + (0.439-5.522)² ≈ 5.94 + (-5.083)² ≈ 5.94 + 25.84 = 31.78 实际下降量：Δf₀ = f(x⁰) - f(x¹) ≈ 52 - 31.78 = 20.22 预测下降量：Δm₀ = m₀(0) - m₀(p₀) = 0 - [ ∇f(x⁰)ᵀp₀ + ½p₀ᵀB₀p₀ ] ∇f(x⁰)ᵀp₀ ≈ [ -44, 24]·[ 0.439, -0.239 ] = -19.32 - 5.74 = -25.06 p₀ᵀB₀p₀ = p₀ᵀp₀ ≈ 0.439² + (-0.239)² ≈ 0.193 + 0.057 = 0.25 Δm₀ ≈ -[ -25.06 + ½×0.25 ] = 25.06 - 0.125 = 24.935 比值 ρ₀ = Δf₀/Δm₀ ≈ 20.22/24.935 ≈ 0.811 由于 ρ₀ > 0.75（典型阈值），接受试探步：x¹ = [ 0.439, 2.761 ] 由于 ρ₀ > 0.75 且 ||p₀|| = Δ₀（步在边界上），扩大信赖域：Δ₁ = 2×Δ₀ = 1.0 第五步：更新正割矩阵正割方程要求 Bₖ₊₁sₖ = yₖ，其中 sₖ = x¹ - x⁰ ≈ [ 0.439, -0.239 ]，yₖ = ∇f(x¹) - ∇f(x⁰) 计算 ∇f(x¹)： ∇f(x¹) ≈ [ 4(0.439-2)³ + 2(0.439-2×2.761), -4(0.439-2×2.761) ] = [ 4×(-1.561)³ + 2×(0.439-5.522), -4×(0.439-5.522) ] ≈ [ 4×(-3.80) + 2×(-5.083), -4×(-5.083) ] ≈ [ -15.20 - 10.166, 20.332] ≈ [ -25.366, 20.332 ] y₀ = ∇f(x¹) - ∇f(x⁰) ≈ [ -25.366, 20.332] - [ -44, 24] = [ 18.634, -3.668 ] 使用BFGS公式更新正割矩阵： B₁ = B₀ - (B₀s₀)(B₀s₀)ᵀ/(s₀ᵀB₀s₀) + y₀y₀ᵀ/(s₀ᵀy₀) 计算各项： B₀s₀ = I×s₀ = s₀ ≈ [ 0.439, -0.239 ] s₀ᵀB₀s₀ = s₀ᵀs₀ ≈ 0.439² + (-0.239)² ≈ 0.193 + 0.057 = 0.25 s₀ᵀy₀ ≈ [ 0.439, -0.239]·[ 18.634, -3.668 ] ≈ 8.18 + 0.876 ≈ 9.056 B₁ ≈ I - ([ 0.439, -0.239][ 0.439, -0.239]ᵀ)/0.25 + ([ 18.634, -3.668][ 18.634, -3.668 ]ᵀ)/9.056 第六步：继续迭代至收敛重复上述过程：用当前 Bₖ 和 Δₖ 求解信赖域子问题得试探步 pₖ 计算 ρₖ = Δfₖ/Δmₖ 根据 ρₖ 调整信赖域半径和决定是否接受试探步用BFGS公式更新正割矩阵 Bₖ₊₁ 经过多次迭代后，解会收敛到真解 x* ≈ [ 2.0, 1.0]，此时 f(x* ) = 0，∇f(x* ) = [ 0, 0 ]。该算法通过正割法近似Hessian，避免了二阶导数计算；通过信赖域法保证稳定性；反射技术处理边界情况提高效率。对于此强非线性问题，能有效收敛到全局极小点。