一维搜索问题基本数学原理

一维搜索的数学模型为:

\[min f\mathrm{(}x\mathrm{)}\mathrm{  }\mathrm{,}{x}_{1}\lt x\lt{x}_{2}\]

式中,x, x1, 和x2为标量,f (x)为函数,返回标量。

该问题的搜索过程可用下式表达:

\[{x}_{k+1}={x}_{k}+\alpha\times d\]

在上式中,xk为本次迭代的值,d为搜索方向, 为搜索方向上的步长参数。所以,一维搜索就是要利用本次迭代的信息来构造下次迭代的条件。

求解单变量最优化问题的方法有很多种。根据目标函数是否需要求导,可以分为两类,即直接法和间接法。直接法不需要用到目标函数的导数,而间接法则需要用到目标函数的导数。

1.直接法

常用的一维直接法主要有消去法和多项式近似法两种。

(1)消去法。该方法利用单峰函数具有的消去性质进行反复迭代,逐渐消去不包含极小点的区间,缩小搜索区间,直到搜索区间缩小到给定的允许精度为止。一种典型的消去法为黄金分割搜索法(Golden Section Search)。黄金分割搜索法的基本思想是在单峰区间内适当插入两点,将区间分为3段,然后通过比较这两点函数值的大小来确定是删去最左段区间还是最右段区间,或同时删去左、右两段区间保留中间段区间。重复该过程使区间无限缩小。插入点的位置位于区间的黄金分割点及其对称点上,所以该法被称为黄金分割搜索法。该方法的优点是算法简单,效率较高,稳定性好。

(2)多项式近似法。该方法用于目标函数比较复杂的情况。此时寻找一个与目标函数近似的函数来代替它,并用近似函数的极小点作为原函数极小点的近似。常用的近似函数有二次插值多项式近似法和三次插值多项式近似法(以下简称二次插值法和三次插值法)。

二次内插涉及形如下式的二次函数数据拟合问题:

\[{m}_{q}(\alpha)=a{\alpha}^{2}+b\alpha+c\]

其中步长极值为

\[{\alpha}^{*}=\frac{-b}{2a}\]

然后只要利用3个梯度或函数方程组就可以确定系数a和b,从而可以确定 *。得到该值以后,进行搜索区间的收缩。在缩短的新区间中,重新设置3个点求出下一次的近似极小点*,如此迭代下去,直到满足终止准则为止。其迭代公式为

\[{x}_{k+1}=\frac{1}{2}\frac{{\beta}_{23}f({x}_{1})+{{\beta}_{31}}_{}f({x}_{2})+{\beta}_{12}f({x}_{3})}{{\gamma}_{23}f({x}_{1})+{\gamma}_{31}f({x}_{2})+{\gamma}_{12}f({x}_{3})}\]

在上式中

\({\beta}_{ij}={x}_{i}^{2}-{x}_{j}^{2}\)\({\gamma}_{ij}={x}_{i}-{x}_{j}\)

二次插值法的计算速度比黄金分割搜索法的快,但是对于一些强烈扭曲或者可能多峰的函数,该方法的收敛速度会变得很慢,甚至会收敛失败。

2.间接法

使用间接法需要计算目标函数的导数,其优点是计算速度很快。常见的间接法包括Newton切线法、对分法、割线法和三次插值法等。MATLAB优化工具箱中被用得较多的是三次插值法。

三次插值法的基本思想与二次插值法的一致,它是用4个已知点构造一个三次多项式P3(x),用它逼近函数f(x),以P3(x)的极小点作为f(x)的近似极小点。一般三次插值法比二次插值法的收敛速度要快一些,但在每次迭代时需要计算两个导数值。

三次插值法的迭代公式为

\[{x}_{k+1}={x}_{2}-({x}_{2}-{x}_{1})\frac{\nabla f({x}_{2})+{\beta}_{2}-{\beta}_{1}}{\nabla f({x}_{2})-\nabla f({x}_{1})+2{\beta}_{2}}\]

在上式中

\[{\beta}_{1}=\nabla f({x}_{1})+\nabla f({x}_{2})-3\frac{f({x}_{1})-f({x}_{2})}{{x}_{1}-{x}_{2}}\]
\[{\beta}_{2}=({\beta}_{1}^{2}-\nabla f({x}_{1})\nabla f({x}_{2}){)}^{1/2}\]

如果函数的导数容易求得,则一般首先考虑使用三次插值法,因为它具有较高的效率。对于只需要计算函数值的方法,二次插值法是一个很好的方法,它的收敛速度较快,在极小点所在的区间较小时尤其如此。黄金分割搜索法则是一种十分稳定的方法,并且计算简单。由于以上因素,MATLAB优化工具箱中用得较多的是二次插值法、三次插值法及二次混合插值法、三次混合插值法和黄金分割搜索法。