优化理论之一维精确优化（下）

一维精确优化

注1：本文讨论需要优化的函数都是单峰函数（或单谷函数）。

• 一维优化方法
• 搜索法
• 二分搜索
• 黄金分割搜索
• 斐波那契搜索
• 近似法
• 二次插值法
  • 一点二次插值（即牛顿法）
  • 二点二次插值
  • 三点二次插值
• 三次插值法
  • 二点三次插值法（Cubic Interpolation Method with Two-Points）
• 综合方法
• D.S.C.法

一维优化方法

搜索法

二分搜索

黄金分割搜索

斐波那契搜索

近似法

插值法是一类重要的一维搜索方法。其基本思想是在搜索区间中不断用低次多项式来近似目标函数，并逐步用插值多项式的极小点来逼近一维搜索问题的极小点。当函数具有较好的解析性质时，插值法比搜索法效果更好。伟大的泰勒！泰勒展开，多项式！

常见的插值方法有一点二次插值法、二点二次插值法、三点二次插值法和二点三次插值法。其中一点二次插值法就是牛顿法，二点二次插值法中的一种就是割线法。

几次插值法就是插值多项式的最高阶数，几点就是选用几个点。比如二次插值法，插值多项式为\(q(x)=ax^2+bx+c\)有3个待定系数，可以从两个方面来确定系数，一是用点的值，二是用点的导数。

二次插值法

二次插值法就是不断构造二次插值多项式\(q(x)=ax^2+bx+c\)来近似目标函数\(f(x)\)并将最后一步构造的二次插值多项式的极小值点作为目标函数极小值点的方法，不同二次插值法的区别在于构造二次插值多项式时使用的信息不同。（注：以下介绍各方法基本原理时，\(x_k\)均指第\(k\)步迭代中构造的插值多项式的极小值点）

一点二次插值（即牛顿法）

一点二次插值在第\((k+1)\)步构造二次插值多项式时使用 1 个函数、1 个一阶导数和 1 个二阶导数信息。一点，最高阶为2次，名字由来。 \[\begin{aligned} q(x_k)=&ax_k^2+bx_k+c&=f(x_k)\\ q'(x_k)=&2ax_k+b&=f'(x_k)\\ q''(x_k)=&2a&=f''(x_k) \end{aligned}\] 求关于\(a,b,c\)的解方程组： \[a=\frac{\begin{vmatrix}f(x_k)&x_k&1\\f'(x_k)&1&0\\f''(x_k)&0&0\end{vmatrix}} {\begin{vmatrix}x_k^2&x_k&1\\2x_k&1&0\\2&0&0\end{vmatrix}}=\frac{f''(x_k)}{2}\] \[b=\frac{\begin{vmatrix}x_k^2&f(x_k)&1\\2x_k&f'(x_k)&0\\2&f''(x_k)&0\end{vmatrix}} {\begin{vmatrix}x_k^2&x_k&1\\2x_k&1&0\\2&0&0\end{vmatrix}}=f'(x_k)-x_kf''(x_k)\] 要求\(q'(x)=f'(x)=0\)，所以此时\(x_{k+1}=x_k-\frac{f'(x)}{f''(x)}\)。从原理上来看，牛顿法只是求导数为0的点，这个点可能是极大值也可能是极小值。

二点二次插值

二点二次插值法（割线法, Secant Method）在第\(\left(k+1 \right )\)步构造二次插值多项式时使用 1 个函数和 2 个一阶导数信息 \[q\left(x_{k-1} \right ) = f \left(x_{k-1} \right ),\ q'\left(x_{k-1} \right ) = f' \left(x_{k-1} \right ),\ q'\left(x_k \right ) = f' \left(x_k \right )\] 由此导出二点二次插值法（割线法）的迭代公式为： \[x_{k+1} = x_k - \frac{f' \left(x_k \right )}{\frac{f' \left(x_k \right ) - f' \left(x_{k-1} \right )}{x_k - x_{k-1}}} = x_k - \frac{x_k - x_{k-1}}{f'\left(x_k \right )-f'\left(x_{k-1} \right )}f'\left(x_k \right )\] 而二点二次插值法（非割线法, Quadratic Interpolation Method with Two-Points）则使用 2 个函数和 1 个一阶导数信息 \[q\left(x_{k-1} \right ) = f \left(x_{k-1} \right ),\ q'\left(x_{k-1} \right ) = f' \left(x_{k-1} \right ),\ q\left(x_k \right ) = f \left(x_k \right )\] 由此导出二点二次插值法（非割线法）的迭代公式为： \[x_{k+1} = x_k + \frac{1}{2}\frac{x_k - x_{k-1}}{\frac{f \left(x_k \right ) - f \left(x_{k-1} \right )}{f'\left(x_k \right )\left(x_k - x_{k-1} \right )} - 1} = x_k - \frac{1}{2}\frac{x_k-x_{k-1}}{f'\left(x_k \right )-\frac{f\left(x_k \right )-f\left(x_{k-1} \right )}{x_k - x_{k-1}}}f'\left(x_k \right )\]

二点二次插值法具有1.618斐波那契的超线性收敛速度。

三点二次插值

三次插值法

类似地，三次插值法就是不断构造三次插值多项式\(p \left(x \right ) = ax^3 + bx^2 + cx + d\)来近似目标函数 \(f \left(x \right )\) 并将最后构造的三次插值多项式的极小值点作为目标函数极小值点的方法。

二点三次插值法（Cubic Interpolation Method with Two-Points）

在第 \(k\) 步构造三次插值多项式时使用 2 个函数和 2 个一阶导数信息 \[p \left(a_k \right ) = f \left(a_k \right ), p'\left(a_k \right ) = f'\left(a_k \right ), p \left(b_k \right ) = f \left(b_k \right ), p'\left(b_k \right ) = f'\left(b_k \right )\] \(a_k < b_k\) 的值根据 \(f' \left(x_k \right )\) 与 \(0\) 的大小关系，从 \(a_{k-1},\ b_{k-1},\ x_k\) 中选取。由上述信息得到的第 \(\left(k+1 \right )\) 步迭代中构造的三次插值多项式的极小值点公式为： \[\begin{aligned} &x_{k+1} = a_k + \frac{\eta_k-f'\left(a_k \right )-\omega_k}{2\eta_k-f'\left(a_k \right )+f'\left(b_k \right )}\left(b_k-a_k \right ) \\ &\eta_k = \sqrt{\omega_k^2-f'\left(a_k \right )f'\left(b_k \right )} \\ &\omega_k = \frac{3\left[f\left(b_k \right )-f\left(a_k \right ) \right ]}{b_k-a_k}-f'\left(a_k \right )f'\left(b_k \right ) \end{aligned}\]

二点三次插值法的收敛速度为2阶。

综合方法

D.S.C.法