非线性规划中的Nelder-Mead单纯形法基础题
题目描述：考虑无约束非线性规划问题 min f(x) = (x₁-2)⁴ + (x₁-2x₂)²，其中 x = (x₁, x₂) ∈ R²。使用Nelder-Mead单纯形法求解该问题，初始单纯形由三个顶点构成：x⁰=(0,0), x¹=(1,0), x²=(0,1)。
解题过程：
-
算法原理介绍
Nelder-Mead法是一种直接搜索算法，通过构造n维空间中的单纯形（n+1个顶点）并迭代更新顶点位置来寻找最优解。基本操作包括反射、扩张、收缩和缩边。 -
初始化步骤
初始单纯形顶点：
- x⁰ = (0,0), f(x⁰) = (0-2)⁴ + (0-0)² = 16
- x¹ = (1,0), f(x¹) = (1-2)⁴ + (1-0)² = 1 + 1 = 2
- x² = (0,1), f(x²) = (0-2)⁴ + (0-2)² = 16 + 4 = 20
- 第一次迭代
(1) 排序顶点：
最佳点 x_b = (1,0), f_b=2
次优点 x_g = (0,0), f_g=16
最差点 x_w = (0,1), f_w=20
(2) 计算重心点（排除最差点）：
x_c = (x_b + x_g)/2 = ((1+0)/2, (0+0)/2) = (0.5, 0)
(3) 反射操作（反射系数α=1）：
x_r = x_c + α(x_c - x_w) = (0.5,0) + 1×((0.5,0)-(0,1)) = (1.0, -1.0)
f(x_r) = (1-2)⁴ + (1-2×(-1))² = 1 + (1+2)² = 1 + 9 = 10
(4) 比较反射点质量：
f_b=2 < f_r=10 < f_w=20 → 用x_r替换x_w
新单纯形：{(1,0), (0,0), (1,-1)}
- 第二次迭代
(1) 排序：
x_b=(1,0), f_b=2
x_g=(0,0), f_g=16
x_w=(1,-1), f_w=10
(2) 重心点：
x_c = ((1+0)/2, (0+0)/2) = (0.5, 0)
(3) 反射：
x_r = (0.5,0) + 1×((0.5,0)-(1,-1)) = (0.5,0) + (-0.5,1) = (0,1)
f(x_r)=20（与之前相同）
(4) 反射点较差但非最差，进行收缩（μ=0.5）：
x_s = x_c + μ(x_w - x_c) = (0.5,0) + 0.5×((1,-1)-(0.5,0)) = (0.75, -0.5)
f(x_s) = (0.75-2)⁴ + (0.75-2×(-0.5))² = (-1.25)⁴ + (0.75+1)² ≈ 2.44 + 3.06 = 5.50
(5) 收缩点改善明显，替换最差点
新单纯形：{(1,0), (0,0), (0.75,-0.5)}
- 收敛判断
继续迭代直到单纯形大小小于容差（如10⁻³）。经过约20次迭代后，单纯形将收缩到最优解(2,1)附近，f(2,1)=0。
关键点：通过比较函数值动态调整单纯形形状，适应函数地形，无需梯度信息。