非线性规划中的Nelder-Mead单纯形法进阶题
题目描述
考虑无约束非线性规划问题：
\[\min f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2 \]
其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。目标函数非凸且不可微点较少，但存在多个局部极小点。要求使用Nelder-Mead单纯形法求解该问题，从初始点 \(x^{(0)} = (0, 3)\) 出发，构建初始单纯形并迭代至收敛。
解题过程
1. 算法原理
Nelder-Mead法是一种直接搜索算法，通过构造单纯形（n维空间中的n+1个点）并迭代调整其形状来逼近最优解。核心操作包括：
- 反射：将最差点反射到期望区域。
- 扩展：若反射点表现优，进一步延伸搜索。
- 收缩：若反射点较差，向单纯形内部收缩。
- 缩减：当其他操作无效时，缩小整个单纯形。
2. 初始单纯形构建
从初始点 \(x^{(0)} = (0, 3)\) 出发，构造边长为1的初始单纯形。常用方法为：
\[x^{(1)} = (0, 3), \quad x^{(2)} = (0+1, 3), \quad x^{(3)} = (0, 3+1) \]
即顶点为：
\[x^{(1)} = (0, 3), \quad x^{(2)} = (1, 3), \quad x^{(3)} = (0, 4) \]
计算各顶点函数值：
\[f(x^{(1)}) = (0-2)^4 + (0-6)^2 = 16 + 36 = 52 \]
\[f(x^{(2)}) = (1-2)^4 + (1-6)^2 = 1 + 25 = 26 \]
\[f(x^{(3)}) = (0-2)^4 + (0-8)^2 = 16 + 64 = 80 \]
排序确定最差点 \(x_h = (0,4)\)（值80），次差点 \(x_g = (0,3)\)（值52），最优点 \(x_l = (1,3)\)（值26）。
3. 第一次迭代
步骤1：计算重心点
排除最差点 \(x_h\)，计算 \(x_l\) 与 \(x_g\) 的重心：
\[x_c = \frac{(0,3) + (1,3)}{2} = (0.5, 3) \]
步骤2：反射操作
反射系数 \(\alpha = 1\)，反射点：
\[x_r = x_c + \alpha (x_c - x_h) = (0.5, 3) + 1 \cdot ((0.5,3) - (0,4)) = (1, 2) \]
计算 \(f(x_r) = (1-2)^4 + (1-4)^2 = 1 + 9 = 10\)。
比较：\(f(x_r) = 10 < f(x_l) = 26\)，进入扩展。
步骤3：扩展操作
扩展系数 \(\gamma = 2\)，扩展点：
\[x_e = x_c + \gamma (x_r - x_c) = (0.5, 3) + 2 \cdot ((1,2) - (0.5,3)) = (1.5, 1) \]
计算 \(f(x_e) = (1.5-2)^4 + (1.5-2)^2 = 0.0625 + 0.25 = 0.3125\)。
由于 \(f(x_e) < f(x_r)\)，用 \(x_e\) 替换 \(x_h\)，新单纯形：
\[x^{(1)} = (1,3),\quad x^{(2)} = (0,3),\quad x^{(3)} = (1.5,1) \]
重新排序：\(x_l = (1.5,1)\)（值0.3125），\(x_g = (1,3)\)（值26），\(x_h = (0,3)\)（值52）。
4. 第二次迭代
步骤1：重心点
排除 \(x_h = (0,3)\)，计算：
\[x_c = \frac{(1,3) + (1.5,1)}{2} = (1.25, 2) \]
步骤2：反射
\[x_r = x_c + 1 \cdot (x_c - x_h) = (1.25, 2) + ((1.25,2) - (0,3)) = (2.5, 1) \]
计算 \(f(x_r) = (2.5-2)^4 + (2.5-2)^2 = 0.0625 + 0.25 = 0.3125\)。
比较：\(f(x_r) = 0.3125 > f(x_l) = 0.3125\)（相等），但小于 \(f(x_g) = 26\)，进入收缩。
步骤3：收缩操作
收缩系数 \(\beta = 0.5\):
\[x_s = x_c + \beta (x_r - x_c) = (1.25, 2) + 0.5 \cdot ((2.5,1) - (1.25,2)) = (1.875, 1.5) \]
计算 \(f(x_s) = (1.875-2)^4 + (1.875-3)^2 \approx 0.00024 + 1.2656 = 1.2658\)。
由于 \(f(x_s) < f(x_h) = 52\)，用 \(x_s\) 替换 \(x_h\)，新单纯形：
\[x^{(1)} = (1.5,1),\quad x^{(2)} = (1,3),\quad x^{(3)} = (1.875,1.5) \]
排序：\(x_l = (1.5,1)\)，\(x_g = (1.875,1.5)\)，\(x_h = (1,3)\)。
5. 收敛判断
继续迭代直至单纯形大小小于容差（如 \(\epsilon = 10^{-6}\)）。最终单纯形收敛至全局极小点 \(x^* \approx (2,1)\)，验证：
\[f(2,1) = (2-2)^4 + (2-2)^2 = 0 \]
实际解为 \(x^* = (2,1)\)，与理论一致。
关键点总结
- Nelder-Mead法无需梯度信息，适用于不可微问题。
- 初始单纯形应避免退化（如共线点）。
- 扩展和收缩系数通常取 \(\gamma=2, \beta=0.5\)，可根据问题调整。
- 收敛慢于梯度法，但鲁棒性强，尤其适合低维问题。