漫步最优化二十七——二次插值法

$\textbf{陪着你，仿佛面朝阳光，}$
$\textbf{不管走到哪里都是晴天。}$
$\textbf{在蝴蝶飞舞的百花丛中，}$
$\textbf{一朵一朵的鲜花因你而香。}$
$\textbf{一片云掉在我眼前，}$
$\textbf{我捏成你的形状，}$
$\textbf{一口一口的吃掉了忧愁。}$
$\textbf{我们手牵着手，}$
$\textbf{一步两步三步四步，}$
$\textbf{看着对方深情的眼眸，}$
$\textbf{心照不宣的许下了誓言。}$
$\quad\textbf{——畅宝宝的傻逼哥哥}$

在一维优化的近似法中，我们先假定目标函数的近似表达式，通常用低阶多项式。如果我们假定二阶多项式为

$$p(x)=a_0+a_1x+a_2x^2$$

其中$a_0,a_1,a_2$是常数，那么我们就得到二次插值法。

令

$$p(x_i)=a_0+a_1x_i+a_2x_i^2=f(x_i)=f_i$$

其中$i=1,2,3,[x_1,x_3]$包含$f(x)$的最小值$x^*$。假设$f_i$的值是已知的，那么通过同时求解三个等式可得$a_0,a_1,a_2$，推到出的多项式$p(x)$就是$f(x)$的近似。基于这样的场景，假设$p(x),f(x)$的图像如图1所示，显然，$p(x)$的最小值$\bar{x}$很靠近$x^*$，如果$f(x)$可以用二阶多项式表示，那么$\bar{x}\approx x^*$，如果$f(x)$就是二次函数，那么$p(x)$就是$f(x)$的准确表示且$\bar{x}=x^*$。

$p(x)$对$x$的一阶导为

$$p^\prime(x)=a_1+2a_2x$$

如果

$$p^\prime(x)=0$$

且$a_2\neq0$，那么$p(x)$的最小值为

$$\bar{x}=-\frac{a_1}{2a_2}$$

通过求解上面的等式组可得

$$\begin{align*} a_1&=-\frac{(x_2^2-x_3^2)f_1+(x_3^2-x_1^2)f_2+(x_1^2-x_2^2)f_3}{(x_1-x_2)(x_1-x_3)(x_2-x_3)}\\ a_2&=\frac{(x_2-x_3)f_1+(x_3-x_1)f_2+(x_1-x_2)f_3}{(x_1-x_2)(x_1-x_3)(x_2-x_3)} \end{align*}$$

所以

$$\bar{x}=\frac{(x_2^2-x_3^2)f_1+(x_3^2-x_1^2)f_2+(x_1^2-x_2^2)f_3}{2[(x_2-x_3)f_1+(x_3-x_1)f_2+(x_1-x_2)f_3]}$$

图1

上面的过程是二次插值法的一次迭代。如果$f(x)$不能用二阶多项式表示，那么需要多执行几次这样的迭代。比较合适的策略是每次迭代的时候缩小不确定区间，可以舍弃$x_1$或$x_3$来实现该目的，然后用保留下来的两点以及$\bar{x}$进行新的迭代。

几次迭代后，三个点将会在$x^*$的邻域内，因此$p(x)$的二阶多项式将会是$f(x)$的精确表示，且可以确定任意精度范围内的$x^*$。