最速下降法

算法

注意

• 先确定搜索方向：负梯度方向；
• 然后确定步长：步长 λ \lambda λ选择的是关于 λ \lambda λ的一元函数 f ( x k + λ d k ) f(x_k+\lambda d_k) f(xk​+λdk​)的最优解。

原理介绍：为什么负梯度方向是下降方向

证明：
f f f在点 x x x沿方向 d d d的导数为 f ′ ( x ; d ) = lim ⁡ λ → 0 + f ( x + λ d ) − f ( x ) λ f'(x;d)=\lim\limits_{\lambda\rightarrow0^+}\frac{f(x+\lambda d)-f(x)}{\lambda} f′(x;d)=λ→0+lim​λf(x+λd)−f(x)​，而等式右端又是关于 λ \lambda λ的一次函数 θ ( λ ) = f ( x + λ d ) \theta(\lambda)=f(x+\lambda d) θ(λ)=f(x+λd)在 0 0 0的导数，所以 lim ⁡ λ → 0 + f ( x + λ d ) − f ( x ) λ = θ ′ ( λ ) = lim ⁡ λ → 0 + ∇ f ( x + λ d ) T d = ∇ f ( x ) T d \lim\limits_{\lambda\rightarrow0^+}\frac{f(x+\lambda d)-f(x)}{\lambda}=\theta'(\lambda)=\lim\limits_{\lambda\rightarrow0^+}\nabla f(x+\lambda d)^Td=\nabla f(x)^Td λ→0+lim​λf(x+λd)−f(x)​=θ′(λ)=λ→0+lim​∇f(x+λd)Td=∇f(x)Td。
于是，题目中的优化问题就变为 min ⁡ { ∇ f ( x ) T d : ∣ ∣ d ∣ ∣ ≤ 1 } \min\{\nabla f(x)^Td:||d||\leq 1\} min{∇f(x)Td:∣∣d∣∣≤1}.
由于 ∇ f ( x ) T d = ∣ ∣ ∇ f ( x ) ∣ ∣ ⋅ ∣ ∣ d ∣ ∣ ⋅ cos ⁡ ( α ) ≥ − ∣ ∣ ∇ f ( x ) ∣ ∣ ⋅ ∣ ∣ d ∣ ∣ ≥ − ∣ ∣ ∇ f ( x ) ∣ ∣ . \nabla f(x)^Td=||\nabla f(x)||\cdot||d||\cdot \cos(\alpha)\geq-||\nabla f(x)||\cdot||d||\geq -||\nabla f(x)||. ∇f(x)Td=∣∣∇f(x)∣∣⋅∣∣d∣∣⋅cos(α)≥−∣∣∇f(x)∣∣⋅∣∣d∣∣≥−∣∣∇f(x)∣∣.
当 d = − ∇ f ( x ) / ∣ ∣ ∇ f ( x ) ∣ ∣ d=-\nabla f(x)/||\nabla f(x)|| d=−∇f(x)/∣∣∇f(x)∣∣时， ∇ f ( x ) T d = − ∣ ∣ ∇ f ( x ) ∣ ∣ \nabla f(x)^Td=-||\nabla f(x)|| ∇f(x)Td=−∣∣∇f(x)∣∣。所以， d = − ∇ f ( x ) / ∣ ∣ ∇ f ( x ) ∣ ∣ d=-\nabla f(x)/||\nabla f(x)|| d=−∇f(x)/∣∣∇f(x)∣∣是原问题的最优解。

为什么负梯度方向是下降方向呢？

首先来看看下降方向的定义：
如果存在 δ > 0 \delta>0 δ>0，s.t. ∀ λ ∈ ( 0 , δ ) , \forall \lambda\in(0,\delta), ∀λ∈(0,δ), 都有 f ( x + λ d ) < f ( x ) f(x+\lambda d)<f(x) f(x+λd)<f(x)，则称方向 d d d是 f f f在点 x x x的下降方向。

若是 d = − ∇ f ( x ) d=-\nabla f(x) d=−∇f(x), 那么 lim ⁡ λ → 0 + f ( x + λ d ) − f ( x ) λ = ∇ f ( x ) T d = − ∣ ∣ ∇ f ( x ) ∣ ∣ 2 < 0 \lim\limits_{\lambda\rightarrow0^+}\frac{f(x+\lambda d)-f(x)}{\lambda}=\nabla f(x)^Td=-||\nabla f(x)||^2<0 λ→0+lim​λf(x+λd)−f(x)​=∇f(x)Td=−∣∣∇f(x)∣∣2<0，所以负梯度方向是下降方向，而由上面的引理，单位负梯度方向是最速下降方向。