Powell 直接方法

Powell 方法只调用函数值。它沿一组方向逐个做一维搜索，再用整轮的净位移更新方向组，试图自动学出类似共轭方向的结构。

为什么需要直接法

有些目标来自仿真、实验或黑盒程序，导数难以获得；有些函数虽可微，但导数噪声大。直接法用更多函数评估换取更少的微分信息要求。

“不使用导数”不等于可以处理任意不连续函数。Powell 方法仍依赖一维搜索的可解释局部形状，通常用于连续、相对平滑问题。

初始给 $n$ 个线性无关方向，常取坐标方向

d_1=e_1,\ldots,d_n=e_n.

从 $x_0$ 开始依次作精确或较准确的一维搜索：

x_i=x_{i-1}+\alpha_i d_i,\qquad \alpha_i\in\arg\min_\alpha f(x_{i-1}+\alpha d_i).

一轮结束的净位移

d_{\text{new}}=x_n-x_0

浓缩了这一轮真正前进的方向。再从 $x_n$ 沿 $d_{\text{new}}$ 做一次搜索，并用它替换旧方向组中的一个方向。

对正定二次函数，若每次一维搜索精确，某种适当的方向替换策略能逐轮构造 $Q$ -共轭方向。因此 Powell 法可看作“不计算梯度的共轭方向法”。

直觉上，连续沿坐标轴搜索后的总位移包含变量耦合信息。把这个总位移保留下来，下一轮就不必重复抵消同一耦合。

简单地每轮丢弃最旧方向，方向组可能逐渐线性相关，降低搜索空间维度。改进 Powell 法先记录每个旧方向带来的下降量

\Delta_j=f(x^{(k,j-1)})-f(x^{(k,j)}),

并取

m\in\arg\max_j\Delta_j.

令整轮净位移为

d^{(k,n+1)}=x^{(k,n)}-x^{(k,0)},

再沿这条直线搜索：

x^{(k+1,0)} =x^{(k,0)}+\lambda_{n+1}d^{(k,n+1)}.

课件给出的替换判据是

\lambda_{n+1}> \sqrt{ \frac{f(x^{(k,0)})-f(x^{(k+1,0)})} {f(x^{(k,m-1)})-f(x^{(k,m)})} }.

若判据成立，就删除下降最多的旧方向 $d^{(k,m)}$ ：保留它之前的方向，把后续方向依次前移，并把净位移方向放到末尾；若不成立，则整组旧方向保留。分母为零时没有“下降最多且值得替换”的方向，不能直接套这个比值。

这个判据同时比较“沿净位移还走了多远”和“整轮下降相对最大单方向下降有多大”，目的是避免把一个贡献显著的独立方向轻率替换掉。

若

\lVert x_n-x_0\rVert

很小，也不一定已最优，可能只是各次一维搜索精度不足或方向退化。应同时检查目标变化与方向组质量。

坐标下降始终沿固定坐标轴；Powell 方法会更新方向，从而适应旋转的椭圆等高线。对变量耦合强的问题，这个区别很重要。