line search中的重要定理

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

对精确的line search（线搜索），有一个重要的定理：

这个定理表明，当前点在dk方向上移动到的那一点（xk+αkdk）处的梯度，与当前点的搜索方向dk的点积为零。其中，αk是称之为“步长”的一个实数，它是通过line search算法求出来的。

为什么会有这样的结论？我们来看看。对每一个line search过程来说，搜索方向dk已经已经是确定的了（在最优化算法中，如何找出一个合适的dk不是line search干的事情）。所以，在一个确定的dk上，要找到一个合适的αk，使得ϕ(α)=f(xk+αdk)这个函数满足f(xk+αkdk)0f(xk+αdk)=minα>0ϕ(α)那么，我们称这样的line search为“精确的line search”——你看，这名字好贴切：我们精确地找到了函数值最小的那个点。

既然xk+αkdk是函数值最小的那个点，那么，在该点处的一阶导数（即梯度）为零，所以我们对上式求导（α是自变量，xk和dk为常量）：ϕ′(αk)=[f(xk+αkdk)]′⋅(0+1⋅dk)=[f(xk+αkdk)]′dk=∇f(xk+αkdk)Tdk=0文章来源：http://www.codelast.com/这就是我们前面说的定理了。