一维搜索：黄金分割、Newton 与三次插值

多维迭代先选方向 $d_k$，再把问题压到一条直线上：

$$\phi(\alpha)=f(x_k+\alpha d_k),\qquad \alpha\ge0.$$

一维搜索就是为这条曲线选步长。

精确与非精确搜索

精确搜索求

$$\alpha_k\in\arg\min_{\alpha\ge0}\phi(\alpha).$$

若 $f$ 可微且最优步长位于内部，则

$$\phi'(\alpha_k)=\nabla f(x_{k+1})^Td_k=0.$$

这条正交关系在最速下降、共轭梯度的证明和计算中频繁出现。

实际算法常用非精确搜索，只要求有充分下降。精确搜索本身也要花计算，方向若只是局部近似，没必要把步长算到过高精度。

先找单峰区间

试探法从 $\alpha=0$ 开始，以步长 $h$ 向下降方向采样。如果函数继续下降就逐步放大 $h$；一旦出现“先降后升”的三个点，就得到包含局部极小点的区间 $[a,b]$。

区间搜索通常假设 $\phi$ 在区间上单峰：先严格下降，再严格上升。没有单峰性，黄金分割可能保留错误的谷底。

黄金分割法

取

$$\tau=\frac{\sqrt5-1}{2}\approx0.618,$$

在 $[a,b]$ 内选

$$\alpha_1=a+(1-\tau)(b-a),\qquad \alpha_2=a+\tau(b-a).$$

比较 $\phi(\alpha_1),\phi(\alpha_2)$，删掉不可能含极小点的一侧。黄金比例使缩短区间后能复用一个旧函数值，每轮只需一次新计算。迭代 $k$ 次后区间长度约为 $\tau^k(b-a)$。

一维 Newton 法

若能算导数，解 $\phi'(\alpha)=0$：

$$\alpha_{t+1}=\alpha_t-\frac{\phi'(\alpha_t)}{\phi''(\alpha_t)}.$$

初值足够近且 $\phi''>0$ 时收敛快，但远离极小点时可能跳出区间；工程上常与区间保护结合。

二次与三次插值

二次插值用三个函数值拟合抛物线，取抛物线极小点作为新试探点。三次插值通常使用两个端点的函数值和导数，拟合三次多项式，再取其极小点。

插值点必须落在保护区间内；若拟合曲线曲率异常或给出区间外点，应退回二分/黄金分割，而不是盲信模型。

一个精确搜索例子

对

$$f(x)=\frac12x^TQx-b^Tx,\qquad Q\succ0,$$

沿方向 $d$：

$$\phi'(\alpha)=d^T(Qx-b)+\alpha d^TQd.$$

所以

$$\boxed{\alpha^*=-\frac{d^T\nabla f(x)}{d^TQd}}.$$

若 $d$ 是下降方向，分子为负、分母为正，故步长为正。

考试要点

• 先验证给定方向确实下降，否则 $\alpha\ge0$ 上的极小点可能就在零或根本不存在。
• 解 $\phi'=0$ 后还要看 $\phi''$ 或端点，驻点可能是极大点。
• 黄金分割只用函数值；Newton/插值会用导数或拟合信息。
• 精确搜索的正交关系只对真正的内部最优步长成立。