最速下降法(一)

以最速下降法求解无约束非线性规划问题

解决的问题:

​ 最速下降法解决的是无约束优化问题,而所谓无约束优化问题就是对目标函数的求解,没有任何的约束限制的优化问题,

比如求最小值: \(\min f(x)\) ,其中 : \(f: R^n \rightarrow R\)

求解这类问题: (1)最优条件法 (2)迭代法

最优条件法:

​ 指当函数存在解析形式,能够通过最优性条件求解出显式最优解。

对于无约束最优化问题,如果 \(f(x)\) 在最优点 \(x^*\) 附近可微,那么 \(x^*\) 是局部极小点的必要条件为: \[ df(x^*) = 0 \] 我们常常通过这个必要条件求极小值点,再验证是否是极小值点,当上述方程可以求解时,无约束优化问题基本就解决了

实际中,此方程往往难于求解,这就引出了第二类方法:迭代法

迭代方法的基本思想是:

从一个选定的初始点 \(x_0 \in R^n\) 出发,

按照某一特定的迭代规则产生一个点列 \(\{ x_k \}\) ,使得当 \(\{ x_k \}\) 是有穷点列时,其最后一个点是(NP)的最优解;

\(\{ x_k \}\) 是无穷点列时,它有极限点,并且其极限点是(NP)的最优解

当到达最小值点时,梯度 $f(x_k) $ 接近于0(可以设定目标容许值),此时完成,退出迭代

最速下降法迭代终止时,求得的是目标函数驻点的一个近似点

梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,

因为该方向为当前位置的最快下降方向,所以也被称为是”最速下降法“。

最速下降法越接近目标值,步长越小,前进越慢。

补充:最速下降法适用于凸函数,若存在多个最小值,可能找到局部最优解,而不是全局最优解(最小值)

最速下降法,又称梯度法

\[ \min f(x) = x_1 ^2 + 25x_2 ^2 \]

选一个初始点:

分别对 \(x_1, \ x_2\) 求偏导:

梯度就是用这两个偏导计算得来:

注意: 这里的 \(x_1, \ x_2\) 并不是 \(x_k\) 其中的k,而仅仅代表区别x变量

通常,将基本迭代格式(1)中的 \(d_k\) 称为第k 轮搜索方向, \(\lambda_k\) 为沿 \(d_k\) 方向的步长,

使用迭代方法求解(NP)的关键在于:如何构造每一轮的搜索方向和确定适当的步长。

负梯度方向 $- f(x_k) $ 为 \(f\) 在点 \(x_k\) 处的最速下降方向。

搜索/下降方向: \[ d_k = - \bigtriangledown f(x_k) \] \(\lambda\) 为步长(也称学习率) \[ x_{k+1} = x_k + \lambda d_k \ \ \ (1) \]

以基本迭代格式(1),每一轮从点 \(x_k\) 出发沿最速下降方向 \(d_k\) 作一维搜索,

来建立求解无约束极值问题的方法,称为 最速下降法。

这个方法的特点是,每轮的搜索方向都是目标函数在当前点下降最快的方向。

同时,用 \(\bigtriangledown f(x_k) = 0\)

作为停止条件。

\(|| \bigtriangledown f(x_k) ||\) 双竖线为为取向量模长

这里简单起见,固定步长为 0.01

第一次迭代

第二次迭代

最后将终止时的

代入 \(f(x) = x_1 ^2 + 25x_2 ^2\) 即找到最小值点 \((m, \ n, \ f(x_k))\)

变化步长 - 一维搜索

参考

感谢帮助!

  • https://zhuanlan.zhihu.com/p/32709034
  • http://sofasofa.io/tutorials/python_gradient_descent/
  • https://www.jianshu.com/p/7ffeafd19834
  • https://zhuanlan.zhihu.com/p/78185057
  • https://www.cnblogs.com/shixiangwan/p/7532830.html
  • https://zhuanlan.zhihu.com/p/104947883