最速下降法(一)

以最速下降法求解无约束非线性规划问题 可解决的问题(应用):
    找最值(最优化) 线性拟合(找一线尽量过所有点/差最小)
最小二乘法 只能用作 线性拟合 解决的问题: ​ 最速下降法解决的是无约束优化问题,而所谓无约束优化问题就是对目标函数的求解,没有任何的约束限制的优化问题, 比如求最小值: \(\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