无导数局部优化

1. Nelder–Mead 是什么

Nelder–Mead（单纯形法）是一种 基于函数值比较的局部搜索方法。
它不看梯度，只看：

• 哪些点函数值更好
• 然后根据这些点的几何位置，生成新点

它最经典地用于 连续变量、低维、中小规模 问题。

它的核心对象：单纯形

在 $n$ 维空间里，Nelder–Mead 维护的是 $n+1$ 个点。

• 1 维：2 个点，像一条线段
• 2 维：3 个点，像一个三角形
• 3 维：4 个点，像一个四面体

这个由 $n+1$ 个点组成的几何体叫 单纯形（simplex）。

注意这里的 simplex 和线性规划里的“单纯形法”不是一回事，名字一样，算法不同。

它在干什么

假设当前有 $n+1$ 个点，算法会：

1. 计算每个点的函数值
2. 找出其中最好的点、最差的点
3. 把最差的点往更有希望的方向“挪动”
4. 让整个单纯形逐渐朝低函数值区域移动、收缩

所以它本质上是：

拿一个小几何形状在地形上试探，让它慢慢滑向低谷。

它的几个典型操作

这是 Nelder–Mead 的核心。

反射（reflection）

把最差点关于其余点的中心“弹出去”。

直觉上就是：

这边太差，那就往对面试试。

扩张（expansion）

如果反射后发现很好，那就沿这个方向再多走一点。

意思是：

这个方向看起来对，那就再冲一下。

收缩（contraction）

如果反射后不太理想，就别走太远，往中间缩一点。

意思是：

方向可能没错，但步子太大了。

缩小（shrink）

如果整个单纯形都不太行，就把所有点朝当前最好点收拢。

意思是：

重新在当前最好点附近仔细摸。

2. Nelder–Mead 的直观图像

你可以把它想成一个三角形在二维山谷中移动。

• 三角形的三个顶点是三个试探点
• 哪个点高、哪个点低，函数值会告诉你
• 算法不断把最差顶点替换掉
• 三角形就会慢慢转向、平移、变形
• 最后缩到某个局部低谷附近

所以它很像一种“纯靠试点比较”的局部几何搜索。

3. Nelder–Mead 的优点和缺点

优点

• 不需要梯度
• 实现简单
• 低维连续问题常很好用
• 对“还算平滑”的目标函数效果常不错

缺点

• 本质上是局部法，不能保全局最优
• 高维时效果明显变差
• 对噪声敏感
• 理论收敛性质不如梯度法、信赖域法那么硬

所以它常见的定位是：

低维无导数局部优化器。

4. Pattern Search 是什么

pattern search 一般翻成 模式搜索，也叫 方向搜索 的一类。

它的想法更朴素：

不靠梯度，而是在当前点周围按若干固定方向试探，只要发现改进就移动。

它不像 Nelder–Mead 那样维护一个几何单纯形。
它更像：

拿着一组方向模板，沿着这些方向挨个试。

最简单的一维理解

当前点是 $x$，步长是 $\Delta$。

就去试：

$$x+\Delta ,x-\Delta$$

• 如果有更好的，就走过去
• 如果都不好，就把步长缩小

这其实已经是 pattern search 的最原始形式。

二维时怎么做

当前点 $(x,y)$，步长 $\Delta$。

你可以试这些方向：

• $(x+\Delta ,y)$
• $(x-\Delta ,y)$
• $(x,y+\Delta )$
• $(x,y-\Delta )$

也可以再加斜方向。

如果某个方向函数值更低，就更新到那个点。
如果都没有改进，就减小 $\Delta$。

所以它很像：

站在当前位置，朝东南西北试几步，看哪边下坡。

5. Pattern Search 的核心机制

它通常有两个元素。

探测方向集

例如坐标方向：

$$\pm e_1,\pm e_2,\dots ,\pm e_n$$

也可以是其他一组张成空间的方向。

步长控制

设当前步长为 ${\Delta }_k$。

• 找到更优点：接受并可能保持/增大步长
• 找不到更优点：减小步长

所以它的搜索逻辑是：

• 先用较大步长粗试
• 后面逐渐缩小步长细调

这个思路和数值方法里“粗到细”的思想很一致。

6. Pattern Search 的直观图像

你可以把它想成一个盲人在山地上找低处：

• 不知道梯度
• 只能朝几个固定方向摸一摸
• 发现哪边更低，就往那边走
• 如果周围都没更低的，就缩小步子继续摸

所以它比 Nelder–Mead 更“朴素”、更规则。

7. Pattern Search 的优点和缺点

优点

• 不需要梯度
• 对不可微问题更自然
• 思路简单
• 可以较稳定地处理一些非光滑目标
• 某些变体理论性质还不错

缺点

• 可能比较慢
• 高维时试探方向会很多
• 仍然只是局部法
• 如果函数评估很贵，也会肉疼

所以 pattern search 常被认为比 Nelder–Mead 更朴素、更稳一点，但有时也更慢一点。