4.2 梯度法在线视频

今天我们来讲解梯度法

也称为最速下降法

这里边我们梯度法呢是我们讲的

无约束优化方法里边的一种间接方法

基本思想

由迭代公式

我们同样是使用迭代公式

Xk+1等于Xk+αkSk

我们说了对于迭代来说两步关键

第一步是找合适的方向Sk

第二步找到合适的步长αk

那我们对于方向呢选用搜索方向

就是负梯度

最速下降方向

Sk等于-∇f(Xk)就是我们的最速下降方向

基于这个方向

选择合适的步长来进行求解

那我们看看步骤和框图

输入X0 k是第k轮

然后呢ε是我的收敛精度

计算梯度∇f(X)然后呢

选择Sk就是我负梯度的方向

Sk等于-∇f(X)

然后呢判断∇f(Xk)的摩是不小于ε

小于了

就终止了

就输出了

X*等于Xk然后f(X*)就输出了

如果不小于的话

再去迭代

再去做什么

做一维搜索求最优步长αk

然后呢

进行X(k+1)等于Xk+αkSk k等于k+1

然后计算新的节点

很简单 梯度法的框图非常简单

思路也很清楚

举一个例子

我们看一看

用梯度法来求什么呢

minf(X)等于X1的平方加四倍X2平方

初始点告诉你的 X是等于2,2这一点

然后呢ε是0.01

求解呢我们看一看

首先你既然是梯度法求梯度先把梯度写出来

∇f(X)等于X1平方是两倍X1

4倍X2平方是八倍的X2

把0,0点代进去变成了46

把4提出来

1,4可以做的更简单一点

所以我可以选择S0的方向是负的梯度方向

就是负的1,4

X1等于X0加上α0S0

整理一下

2-α0 2-4α0

是不变成了关于α0的什么

这一个一维的问题了是不是

就是我说的把高维的n维问题变成了一维问题求解

这是我新的X1X21让fX1取到min时候的α0取几

那么这怎么求

就是一个很标准的二次型

我可以做什么

我可以求导来求解

然后令df比dα等于0

α0等于34 65

你看把这个值带进去以后

X11X21就可以求出来这两个值了

X1等于1.477

X2等于-0.0923

∇f(X1)等于2.954

-0.7384

求出来以后呢我算算梯度的摩

∇f(X1)呢等于3.0449

ε是0.01 3.0449远远大于0.01的

所以你这个做一步还早着 还再继续往下进行求解

这是一步迭代

那么继续往下进行求解

那么我可以取什么

S1等于下一次的梯度的方向

取这个方向负的方向继续求解来求X2

那我们看看

梯度法的一个特点

第一几何概念直观

方法程序简单

存储量较小

这是它的第一个

那么第二个

我们说相邻两个搜索方向呢是相互垂直的

搜索路径呢曲折

越接近极值点

搜索速度是越慢的

我们看一个图

是一个带曲率的这样的一个同心椭圆簇

因此说呢这个点

我要去搜索第一步

找到合适的点

然后呢做它的切线做法线

就它的负梯度方向

你看每一次的方向下一个方向跟上一方向是垂直的

但是呢我每一次呢我会很靠近这个极值点

但是我总是很难去达到它

因为什么

沿着折线去做很难靠近它

因此说目标函数的本身性态

初始点的位置对搜索速度影响较大

第四 梯度法属于线性收敛

一般不单独使用

开始使用梯度法

然后改用其他方法

什么意思

最开始的时候梯度法的效果是非常好的

就是在函数的外围效果非常好

几步就能接近于极致点

但是越是接近极值点

就我们说的越接近于极值点

搜索速度越慢

那么鉴于梯度法在远离极值点处的效果很好

而搜索到极值点附近

搜索速度变的越慢

而共轭方向法具有二次收敛的优点

两者可以结合形成共轭梯度法

找任意一点

首先做梯度方向

Sk等于负的f(Xk)我们设它为负的gK

找到合适的这个点Sk+1

然后做负梯度

你看这样子的话

我这两个点的话

实际上这条线和这个点的话也实际上是共轭的

那么我们看

实际上从这一点处连着Sk+1

就是我们这里边的共轭方向

那我们实际上Sk+1变成了什么

负梯度方向和我第一个-gk的方向的线性表示

变成βk倍的Sk

所以说呢Sk+1这个优秀这个方向

不是我们这样总是折线方向

我不用这个梯度方向我进行一个修正

你看我原来这个方向

我进行一个偏转到这个方向

能够指向X*

所以Sk+1呢是-∇f(Xk)与-∇f(X(k+1))的一个线性组合

那么基本思想呢初始方向采用负梯度的方向

从第二次开始搜索方向

根据共轭条件对负梯度进行修正

沿修正后的共轭方向

逐次迭代逼近X*

就是共轭梯度法

特点使原来的具有线性性的梯度法

变成了具有二次收敛性

方法原则 设正定二次函数f(X)等于1/2的XkAX

加上B的转置X加C

然后呢我Xk呢首先是用梯度的方向

去寻找到Xk+1

然后呢Xk+1

用Sk+1的方向去寻找到X*

实际上就是一个修正

那么这里具体的Sk+1就变成关键了

那么Sk+1呢就是什么

就是我的负梯度的方向和什么

一个上一个点的这个Sk的这个修正这个方向

因为它们也是个迭代的关系

那么βk呢称为是共轭系数

那βk的选择呢

应使得Sk与Sk+1呢关于A矩阵是共轭的

那么也就是说呢Sk+1转置ASK等于0

然后呢我们让它等于0以后

gk gk+1等于∇f(Xk)与∇f(X(k+1))

然后两式相减以后呢就变成了

gk+1-gk等于A的Xk+1-Xk

因为Sk+1=Xk+αkSk代入上式

我们可以有gk+1-gk等于αk A的sk

然后我左边都乘以一个上式

变成αkSk+1转至ASk等于它

由一式等于0

我们可以把它写出来

变成了gk+1减去βkSk的转置乘以gk+1减gk等于0

然后呢讨论一下

因为gk+1的转置乘以gk是等于0的

因为两个矢量是正交的

那么则gk+1转置乘以gk+1减去βkgk转置乘以gk是等于0

那么共轭系数呢β就可以解出来了

β可以让这两个函数呈共轭的

那么通过这样的计算

可以β就等于什么

等于这个公式

实际上就是什么

下一个点的梯度的摩的平方比上

上一个点的梯度的摩的平方 βK对吧

共轭系数求出来了

那么有了共轭系数以后

你这样算以后呢

你的共轭方向共轭梯度方向就可以有了

就可以进行计算了

框图 输入X01 ε n

然后呢g0等于∇f(X0) S0等于负的g0

k是等于0的

然后一维搜索求αkXk+1等于Xk加上αkSk

gk+1等于∇f(Xk)

它的摩是小于 ε

如果是对的话那你就输出了呗

就是X*等于Sk+1fX*就输出来就是结束了

如果不是小于0继续迭代

那就k+1等于n然后呢继续迭代

X0等于Sk+1

完成一轮迭代

然后呢继续去做

如果k+1不等于n呢那么你就可以做什么

把β求出来

β求出完以后

新的gk+1不再用什么梯度方向了

对梯度方向进行一个偏转用共轭的修正

然后呢来进行回来

好 这一节我们就讲到这里