运筹学(1)-最速下降法

运筹学(1)
多维无约束优化算法——梯度法之最速下降法

最近学习运筹学开始学习一些优化的算法,之后的一系列博客我会分享一些我学到的运筹学方法。这次我总结了我学习的最速下降法。

1. 原理
最速下降法是一个优化算法,用于求解多维无约束问题。最速下降法由于只考虑到当前下降最快而不是全局,所以最速下降法又叫做瞎子爬山法。最速下降法属于求解非线性规划问题的迭代法。它的关键是得到每步迭代的方向 p(k) 和步长 t

(1)搜索方向 p(k) 的确定
方向 p 为单位向量, ||p||=1 ,从 x(k) 按方向 p ,步长 t 进行搜索得到下一点 x(k+1)=x(k)+tp 。在这里我们用到泰勒展开式得:

f(x(k)+tp)=f(x(k))+tΔf(x(k))Tp+o(t)

可以得到在

x(k) 处的变化率:


limt0f(x(k)+tp)f(x(k))t=limt0tΔf(x(k))Tp+o(t)t=Δf(x(k))Tp

从上式可以得到要使在

x(k) 下降速度最快就要使在

x(k) 的变化率最小,所以就要使

Δf(x(k))Tp 最小。然而

Δf(x(k))Tp=||Δf(x(k))||||p||cosθ=||Δf(x(k))||cosθ . 要使其最小就要使

cosθ=1 .可以得到

p=f(x(k))||Δf(x(k))|| .

从上述就可以确定最速下降法的搜索方向为

p=f(x(k)) .

(2)求解搜索步长 t
最速下降法所采取的搜索步长的策略有两种:
一种是最优步长搜索法,即 f(x(k)+tp)=minf(x(k)+tp) .通过求最小值求得步长。

另一种是近似最佳步长

f(xktΔf(x(k)))f(x(k))tΔf(x(k))TΔf(x(k))+12tΔf(x(k))TH(x(k))tΔf(x(k)).

对上式求导并等于零,可以得到步长

t=Δf(x(k))TΔf(x(k))Δf(x(k))TH(x(k))Δf(x(k))

2.算法步骤
(1).选取初始点 x(0) ,设置终止误差 ϵ>0 k=0
(2).计算 Δf(x(k)) ,如果 Δf(x(k))<ϵ 搜索迭代终止,否则继续下一步。
(3).计算搜索方向 p
(4).计算搜索步长t,可以得到 x(k+1)=x(k)+tp .接着进行第(2)步。

3.例子

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

minf(x)=x21+2x222x1x22x2

其中

x=(x1,x2)T ,要求选取初始点

x(0)=(0,0)T .

解:(1) Δf(x)=(2x12x2,4x22x12)T
(2) Δf(x(0))=(0,2)T
(3) p=Δf(x(0))=(0,2)T
(4)求步长 t ,用最优步长策略:
f(x(1))=f(x(0)+tp)=minf(x(0)+tp)
得步长 t=14
(5) x1=x0+tp=(0,12)T
按照上述方法继续迭代直到达到迭代终止条件, x=1

4.优缺点

优点:
(1)每一步迭代简单,对初始点要求少
缺点:
(1)由于是对每一步进行最优迭代,但是整体的收敛下降速度不一定最快。
(2)用最速下降法求最优问题,迭代路径呈直角锯齿形如下图,开始的几步迭代很快,但越接近最优点收敛速度越慢。

《运筹学(1)-最速下降法》

这是我第一次写博客,如有写的不好的地方希望大家提提建议,谢谢哈!!!

    原文作者:uestcmarvin
    原文地址: https://blog.csdn.net/uestcmarvin/article/details/78671779
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞