转载请注明出处:http://www.codelast.com/

对精确的line search(线搜索),有一个重要的定理:

这个定理表明,当前点在 {d_k} 方向上移动到的那一点( {x_k} + {\alpha _k}{d_k} )处的梯度,与当前点的搜索方向 {d_k} 的点积为零。

其中, {\alpha _k} 是称之为“步长”的一个实数,它是通过line search算法求出来的。

为什么会有这样的结论?我们来看看。
对每一个line search过程来说,搜索方向 {d_k} 已经已经是确定的了(在最优化算法中,如何找出一个合适的 {d_k} 不是line search干的事情)。所以,在一个确定的 {d_k} 上,要找到一个合适的 {\alpha _k} ,使得 \phi (\alpha ) = f({x_k} + \alpha {d_k}) 这个函数满足 f({x_k} + {\alpha _k}{d_k}) < f({x_k}) ,这就是line search的目的。说白了,就是要找到 {\alpha _k} 使 \phi (\alpha ) 的函数函数值变小。
文章来源:http://www.codelast.com/
但是,要小到什么程度呢?假设小到有可能的“最小”,即:
\phi ({\alpha _k}) = f({x_k} + {\alpha _k}{d_k}) = \mathop {\min }\limits_{\alpha > 0} f({x_k} + \alpha {d_k}) = \mathop {\min }\limits_{\alpha > 0} \phi (\alpha )
那么,我们称这样的line search为“精确的line search”——你看,这名字好贴切:我们精确地找到了函数值最小的那个点。

既然 {x_k} + {\alpha _k}{d_k} 是函数值最小的那个点,那么,在该点处的一阶导数(即梯度)为零,所以我们对上式求导( \alpha 是自变量, {x_k}{d_k} 为常量):
\phi '({\alpha _k}) = {\left[ {f({x_k} + {\alpha _k}{d_k})} \right]^\prime } \cdot (0 + 1 \cdot {d_k}) = {\left[ {f({x_k} + {\alpha _k}{d_k})} \right]^\prime }{d_k} = \nabla f{({x_k} + {\alpha _k}{d_k})^T}{d_k} = 0
文章来源:http://www.codelast.com/
这就是我们前面说的定理了。

[原创] line search中的重要定理 - 梯度与方向的点积为零

发表评论

电子邮件地址不会被公开。 必填项已用*标注