欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

「最优化」一维搜索方法

本文讨论的是一元单值函数 \(f:R \rightarrow R\) 时的最小化优化问题的迭代求解方法。这些方法统称为一维搜索法。一维搜索法普遍重视的原因有两个:

  1. 一维搜索法是多变量问题求解法的一个特例
  2. 一维搜索法是多变量问题求解算法的一部分

黄金分割法

黄金分割法是求解一元单值函数 \(f:R\rightarrow R\) 在闭区间 \([a_0,b_0]\) 上的极小点。后面讨论的斐波那契数列法和二分法都是针对这一问题的。该方法的唯一前提是目标函数f在区间上是单峰的。

其实介绍「黄金分割法」之前应该介绍一下「比例切割法」(我自己造的名字),「比例分割法」非常直观,如果已知极小值在一个区间内部,可以通过在区间内部取两个点 \(a_1,b_1\) 分别计算 \(f(a_1)\)\(f(b_1)\) ,四个点的函数值 \(f(a_0)\)\(f(a_1)\)\(f(b_1)\)\(f(b_0)\) 都计算出来了,通过比较 \(f(a_1)\)\(f(b_1)\) 的大小决定极小值落在哪个子区间。

「黄金分割法」巧妙的地方在于,无论子区间是 \([a_1,b_0]\) 还是 \([a_0,b_1]\) ,上一步计算的函数值的结果可以作为下一次使用。

斐波那契数列法

利用「黄金分割法」进行迭代的过程中,每一步的压缩比例 \(p\) 是确定的,如果允许压缩比例 \(p\) 每一步动态调整,比如,第k次使用参数 \(p_k\) ;第k+1次使用参数 \(p_{k+1}\) ,这就产生了一种新的搜索方法。

两次迭代中如果想要实现上一步的计算结果可以被下一步使用,需要满足下面公式:

\(p_{k+1}(1-p_k) = 1-2p_k\)

整理之后可以得到:

\(p_{k+1} = 1- \frac{p_k}{1- p_k}\)

上面介绍的「黄金分割法」只是上式的特例 \(p_k=p_{k+1}\) 时候的情形。

迭代N次的压缩比为:

\((1-p_1)(1-p_2)...(1-p_N)\)

所以这个问题可以通过最优化问题描述为:

\(\begin{matrix}minimize \ &(1-p_1)(1-p_2)...(1-p_N)\\subject \ to \ &p_{k+1} =1-\frac{p_k}{1-p_k}\\& 0 \le p_k \le \frac{1}{2}\end{matrix}\)

上面优化问题的最优解可用斐波那契数列表示:

\(\begin{matrix}p_1=1-\frac{F_N}{F_{N+1}}\\ p_2=1-\frac{F_{N-1}}{F_{N}}\\ \vdots \\ p_k=1-\frac{F_{N-k+1}}{F_{N-k+2}}\\\vdots\\p_n = 1-\frac{F_1}{F_3} \end{matrix}\)

证明过程就不写了(关键是我也没看懂)。

二分法

在前面的假设基础上,如果限制函数f一阶可导,就可以使用二分法进行求解。 具体的,每次确定中间点 \(x^0 = (a_0 + b_0)/2\) ,然后计算此位置的一阶导数 \(f'(x^0)\) ,如果一阶导数大于0说为位于右侧,如果小于0说明位于左侧。每次压缩比1/2,N次迭代之后压缩比要好于「黄金分割法」和「斐波那契法」。

牛顿法

如果函数二阶可微,可用牛顿法求解极小值。核心思想就是在当前点构造一个二次函数(其实就是泰勒展开),通过求解这个二次函数的极小值点,间接求得原始函数的极小值点。构造函数为:

\(q(x)=f(x^k)+f'(x^k)(x-x^k)+\frac{1}{2}f''(x^k)(x-x^k)^2\)

求上面式子的极小值,可以通过一阶必要条件得到:

\(f'(x)=0=f'(x^k)+f''(x^k)(x-x^k)\)

解得:

\(x=x^k -\frac{f'(x^k)}{f''(x^k)}\)

求方程的根

牛顿法可以通过不断的迭代迫使目标函数f的一阶导数函数趋于0,所以牛顿迭代可以用于求方程的根,不知道是不是因为牛顿迭代名气太大,其实这个方法和将方程一阶泰勒展开后求根是一样的,展开公式为:

\(q(x)=f(x^k)+f'(x^k)(x-x^k)\)

令上式为0,解得:

\(x=x^k-\frac{f(x^k)}{f'(x^k)}\)

割线法

通俗的说,牛顿法构造二次函数是对当前点进行拟合,拟合条件是一阶导数和二阶导数相等。「割线法」是构造函数二次对当前点和前一个点进行拟合,拟合条件是一阶导数相等。例如下面函数就是对 \(x^k\)\(x^{k-1}\) 一阶导数相等的拟合:

\(q(x)=f(x^k)+f'(x^k)(x-x^k) + \frac{1}{2}\frac{f'(x^k)-f'(x^{k-1})}{x^k -x^{k-1}}(x-x^k)^2\)

其实很简单,只是使用一阶导数模拟了二阶导数而已。

所以迭代公式可以修改为:

\(x^{k+1} = x^k-\frac{x^k-x^{k-1}}{f'(x^k)-f'(x^{k-1})}f'(x^k)\)

求方程的根

类似牛顿法求方程的根,「割线法」也是每一步都是在寻找一阶导数等于0的点,构造函数并用「割线法」替换一阶导数得到:

\(q(x)=f(x^k)+\frac{f(x^k)-f(x^{k-1})}{x^k-x^{k-1}}(x-x^k)\)

令其为0,解得:

\(x=x^k-\frac{x^k-x^{k-1}}{f(x^k)-f(x^{k-1})}f(x^k)\)

顺着「割线法」的思想,其实可以构造更加复杂一些的函数,拟合更多点的一阶导数。拟合多个点(吵过2)的想法,和多级「泰勒级数」展开有异曲同工之妙。

划界法

划界法并不是一种求解极值点的方法,它是一种确定极值点区间的方法,因为前面介绍的方法中,都依赖一个前提,就是需要已知极值点一定落在了某个区间[a,b]中。

划界法的想法很简单,就是找到三个点a、b、c使得f(a)>f(b)<f(c),这样就可以保证极值点一定是落在了a和c之间。所以当发现f(a)>f(b>)>f(c)或者f(a)<f(b)<f(c)的之后,就要确定探测的方向,重新选择一个点进行探测。如果想要减少探测过程中计算函数值的次数,可以考虑使用类似黄金分割的思想。

多维优化中的一维搜索法

终于到重点部分了,因为工业界都是「多维优化」的场景。

一维搜索的方法在多维搜索的优化问题中发挥着重要的作用,特别是对多为优化问题的迭代求解算法而言,通常每次迭代都包含一维搜索过程。通常极小点的迭代公式为:

\(x^{k+1} = x^k + \alpha_{k} \mathbf{d}^k\)

通常可去d为梯度的反方向, \(\alpha_k \ge 0\) 为步长,确定方式是使函数:

\(\phi(\alpha)=f(x^k +\alpha \mathbf{d}^k)\)

达到最小。这个时候问题就变为了一个一维优化问题,前面列举的优化算法都可以使用了。需要注意的是 \(\phi'(\alpha)\) 的一阶导数是小于0的,具体的:

\(\phi'_k(\alpha)=\mathbf{d}^{(k)T}f'(x^k+\alpha \mathbf{d^k})\)

所以如果d选取为梯度的负方向的话,就有:

\(\phi'(0)=d^{(k)T}f'(x^k)=-f'(x^k)^Tf'(x^k)<0\\)

一维搜索在实际应用中存在一些问题,首先,精确地求解 \(\alpha_k\) 的极小值点 \(\phi_k\) 可能需要非常大的代价;在某些极端的情况下 \(\phi_k\) 甚至是不存在的。其次,实际应用经验表明,应该讲更多的计算资源配置到多维优化算法而不是追求高精度的一维搜索上。这就意味着应该为一维搜索设计合理的停止条件。条件一般包含下面两方面:

  1. 目标函数要有足够程度的下降
  2. \(\alpha\) 不要太大或太小

Armijo条件

Armijo条件(1),保证第k次迭代 \(\alpha_k\) 不会太大并且有一定程度的下降( \(\varepsilon \in (0,1)\) ):

\(\phi_k{\alpha_k} \le \phi_k(0)+\varepsilon \alpha_k \phi'_k(0)\)

Armijo条件(2),保证第k次迭代 \(\alpha_k\) 不会太小(然而这个并不常用,其中 \(\gamma >1\) ):

\(\phi_k(\gamma \alpha_k) \ge \phi_k(0)+\varepsilon \gamma \alpha_k \phi'_k(0)\)

GoldStein条件

GoldStein条件就是在Armijo条件(2)条件上稍作修改:

\(\phi_k(\alpha_k) \ge \phi_k(0)+\eta \alpha_k \phi'_k(0)\)

其中 \(\varepsilon<\eta<1\\)

Armijo条件(1)和GoldStein条件联合称为Armijo-GoldStein条件。

Wolfe条件

前面三个条件是通过函数值做限制,Wolfe条件是通过一阶导数限制,Wolfe条件为:

\(\phi'_k(\alpha_k)\ge \eta \phi'_k(0)\)

Worfe条件的一个变种,强Wolfe条件(通过绝对值限制):

\(\begin{vmatrix} \phi'_k(\alpha_k)\end{vmatrix} \le\begin{vmatrix}\eta \phi'_k(0)\end{vmatrix}\)

参考资料

《最优化导论》Edwin K.P.Chong Stanislaw H. Zak

 

未经允许不得转载:大数据算法 » 「最优化」一维搜索方法

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站