假设$f\left(x\right)$是$R^{n}$上具有一阶连续偏导数的函数。求解
\begin{align*} \\ & \min_{x \in R^{n}} f \left( x \right) \end{align*}
无约束最优化问题。$f^{*}$表示目标函数$f\left(x\right)$的极小点。
由于$f\left(x\right)$具有一阶连续偏导数,若第$k$次迭代值为$x^{\left(k\right)}$,则可将$f\left(x\right)$在$x^{\left(k\right)}$附近进行一阶泰勒展开 \begin{align*} \\ & f\left(x\right) = f\left(x^{\left(k\right)}\right) + g_{k}^{T} \left(x-x^{\left(k\right)}\right)\end{align*} 其中,$g_{k}=g\left( x^{\left(k\right)} \right)=\nabla f \left( x^{\left(k\right)}\right)$是$f\left(x\right)$在$x^{\left(k\right)}$的梯度。
第$k+1$次迭代值 \begin{align*} \\ & x^{\left( k+1 \right)} \leftarrow x^{\left( k \right)} + \lambda_{k} p_{k} \end{align*} 其中,$p_{k}$是搜索方向,取负梯度方向$p_{k}= - \nabla f \left( x^{\left(k\right)} \right)$,$\lambda_{k}$是步长,由一维搜索确定,即$\lambda_{k}$使得 \begin{align*} \\ & f \left( x^{\left(k\right)}+\lambda_{k}p_{k} \right)=\min_{\lambda \geq 0} f \left( x^{\left(k\right)}+\lambda p_{k} \right) \end{align*}
梯度下降算法:
输入:目标函数$f \left( x \right) $,梯度函数$g\left( x^{\left(k\right)} \right)=\nabla f \left( x^{\left(k\right)}\right)$,计算精度$\varepsilon$
输出:$f \left( x \right) $的极小点$x^{*}$
4. 置$x^{\left(k+1\right)}= x^{\left(k\right)}+\lambda_{k}p_{k}$,计算$f \left( x^{\left(k+1\right)} \right)$
当$\| f \left( x^{\left(k+1\right)} \right) - f \left( x^{\left(k\right)} \right) \| < \varepsilon $或$\| x^{\left(k+1\right)} - x^{\left(k\right)} \| < \varepsilon $时,停止迭代,令$x^{*}=x^{k+1}$
5. 否则,置$k=k+1$,转3.