常用无约束最优化方法.ppt

《常用无约束最优化方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章常用无约束最优化方法内容§5.1最速下降法§5.2Newton法§5.3修正Newton法§5.4共轭方向法§5.5共轭梯度法§5.6变尺度法§5.7坐标轮换法§5.8单纯形法引言本章讨论多维无约束最优化问题:minf(X)它的求解是指,在Rn中找一点X*,使得对于任意的都有但大多数最优化方法只能求到局部最优点,即在Rn中找到一点X*,使得上述不等式在X*的某个领域中成立.这个矛盾对于实际问题一般容易解决.根据问题的实际意义多半可以判定用优化方法求出的局部最优解是否为全局最优解.而在理论上这是个比较复杂的

2、问题,本书不涉及.无约束优化方法是优化技术中极为重要和基本的内容之一.它不仅可直接求解无约束优化问题,而且很多约束优化问题也常转化为无约束优化问题,然后用无约束优化方法来求解.另,有些无约束优化方法只略加处理,即可求解约束优化问题.无约束优化理论发展较早,比较成熟,方法也很多,新的方法还在陆续出现.把这些方法归纳起来可以分成两大类:一类是仅用计算函数值所得到的信息来确定搜索方向,通常称它为直接搜索法,简称为直接法,另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向,这一类方法称为间接法(解析法).直

3、接法不涉及导数、Hesse矩阵,适应性强,但收敛速度较慢;间接法收敛速度快,但需计算梯度,甚至需要计算Hesse矩阵.一般情况是,在可能求得目标函数导数时尽可能用间接方法;在不能求目标函数导数或根本不存在导数时就使用直接法.其中则点X*就是问题的全局最优点.迭代终止准则(H准则)⑴当第k次迭代点Xk与最优解X*充分靠近,即

4、

5、Xk-X*

6、

7、充分小时,Xk可作为最优解,这样可用

8、

9、Xk-Xk+1

10、

11、<ε1作为迭代终止准则,此准则是不完全可靠的,因为,

12、

13、Xk-Xk+1

14、

15、充分小并不能保证

16、

17、Xk-X*

18、

19、充分小,

20、这时函数值的差

21、

22、f(Xk)-f(Xk+1)

23、

24、很大,所以要增加条件:

25、

26、fk-fk+1

27、

28、<ε1就比较可靠了,其中fk=f(Xk),fk+1=f(Xk+1)⑵当fk的值或Xk分量的值与1相比很大时,上述准则就太严格了,即满足上述准则就要用很多计算.此时可用下列准则:⑶当算法涉及到梯度时,可用下列准则:

29、

30、f(Xk)

31、

32、<ε3通常ε1=ε2=10-5、ε3=10-4并要求但实际计算中X*是未知的.§5.1最速下降法对于无约束最优化问题的求解,按最优化算法的基本思想是从一个给定的初始点X0出发,通过基本迭代格式

33、Xk+1=Xk+tkPk,按照特定的算法A产生一串点列{Xk},如果此点列收敛,则其极限点为所求的最优解.一、最速下降法基本原理在基本迭代格式Xk+1=Xk+tkPk中,每次迭代搜索方向Pk取目标函数f(X)的负梯度方向,即Pk=-f(Xk),而每次迭代的步长tk取最优步长,由此所确定的算法A称为最速下降法.如图所示,假经过k次迭代得到第k个迭代点Xk.现在从Xk出发,可选择的下降方向很多,一个非常自然的想法是沿最速下降方向(即负梯度方向)进行搜索应该是有利的,至少在Xk邻近的范围内是这样.步长因子的确定为了

34、使目标函数在搜索方向上获得最多的下降,沿Pk进行一维搜索,由此得到第k+1个迭代点即Xk+1=Xk+tkPk,其中步长因子tk按下式确定记为显然,令k=0,1,......就可以得到一个点列其中X0是初始点,由计算者任意选定.当f(X)满足一定的条件时,上面所产生的点列{Xk}必收敛于的极小点.以后为书写方便,记因此,在不发生混淆时,再记Y已知目标函数f(X)及其梯度g(X),终止限ε1、ε2和ε3.⑴选定初始点X0,计算f0=f(X0),g0=g(X0);置k=0.⑵作直线搜索:Xk+1=ls(Xk-gk);

35、计算fk+1=f(Xk+1),gk+1=g(Xk+1).⑶检测是否满足终止准则.若满足,则打印最优解Xk+1,f(Xk+1)停机;否则,置k=k+1转(2).最速下降法算法流程图二、最速下降法迭代步骤开始选定X0结束计算f0=f(X0),g0=g(X0)输出X,f满足终止准则NX0=X,f0=f,g0=g直线搜索:X=ls(X0-g0)计算f=f(X),g=g(X)目标函数为正定二次函数的最速下降法设正定二次函数求Xk+1的表达式.gk=g(Xk+1)=AXk+1+b现在从Xk出发沿-gk作直线搜索以确定Xk+

36、1:其中tk是最优步长因子.有得:由此解出:从而得到即为最速下降法用于二次函数的显式迭代公式.第k次迭代点为Xkf(X)关于X求梯度:g(X)=AX+b或试用最速下降法求函数的极小点.迭代两次,计算各迭代点的函数值,梯度及其模,并验证相邻两个搜索方向是正交的.设初始点为解其中由由二次函数最速下降法的迭代公式有例5.1(P89)梯度表达式是因为由此说明相邻两个搜索方向是正交的.三、最速下