第四章无约束优化方法

第四章无约束优化方法第四章无约束优化方法34、1坐标轮换法基本思想:把一个n维无约束最优化问题转化为依次沿n个坐标轴方向得一维最优化问题。即迭代方向依次为:第一轮:任取一初始点X(0)

一维搜索求得一维搜索求得第二轮:4终止准则:上式点距准则中得两点应就是一轮迭代得始点与终点利用一维优化方法确定沿该方向上具有最小目标函数值得步长,即:min{F(X(k)+αS(k))}=F(X(k)+α(k)S(k))迭代步长α得确定:5坐

标

轮

换

法

得

流

程

图

6坐标轮换法得特点:具有程序结构简单,易于掌握等优点。但收敛慢,适用于n<10得低维优化问题。另收敛速度与等值线得形状有关7例题4、1用坐标轮换法求目标函数得无约束最优解。给定初始点精度要求ε=0、1

解:作第一轮迭代计算。沿e1方向进行一维搜索

按最优步长原则确定步长α1,即极小化此问题可用某种一维优化方法求出α1。在这里,我们暂且借用微分学求导解出,令其一阶导数为零,α1=5

以为新起点，沿e2方向一维搜索以最优步长原则确定α2,即极小化得α2=4、5,对于第一轮按终止条件检验8例题4、1对于第一轮按终止条件检验:继续第二轮迭代计算。以下各轮得计算结果列于表4、1。9例题4、1计算五轮后有故近似优化解为F*＝F(x*)=7、9502510例题4、1用解析法验证

解:令正定114、2鲍威尔(Powell)法鲍威尔法就是直接搜索法中一个十分有效得算法。该算法就是沿着逐步产生得共轭方向进行搜索得,因此本质上就是一种共轭方向法,鲍威尔法得收敛速率较快。以共轭方向作为搜索方向,不只限于鲍威尔法,也用于其她一些较为有效得方法,可以统称为共轭方向法。因此,共轭方向得概念在优化方法研究中占有重要得地位。共轭方向在最优化问题中得应用就是基于其具有一个重要性质,即:设S1、S2、…、Sn就是关于A得n个互相共轭得向量,则对于求正定二次函数得极小点,从任意初始点出发,依次沿Si

(i=1,2,…,n)方向进行一维最优化搜索,至多n步便可以收敛到极小点、122、5关于优化方法中搜寻方向得理论基础

2、5、2共轭方向(见第二章)一、共轭方向得基本概念若有两个n维矢量S1、S2,对n×n阶对称正定矩阵A能满足:称n维空间矢量S1与S2对A共轭共轭矢量所代表得方向称为共轭方向。正交:可以瞧作就是共轭得特例例:(1)共轭并正交大家学习辛苦了，还是要坚持继续保持安静14例:(2)共轭但不正交设A为n×n阶实对称正定矩阵,有一组非零得n维矢量S1、S2、…、Sq,若满足

i≠j则称矢量系Si(i＝1,2,…,q≤n)对于矩阵A共轭

15以二维函数为例:

二维正定二次函数具有两个重要特性:1)二维正定二次函数得等值线就是同心得椭圆族,且椭圆中心就就是正定二元二次函数得极小点。2)过同心椭圆族中心x*作任意直线,此直线与诸椭圆交点处得切线相互平行。或者说:两条平行得任意方向得切线,其切点得连线必通过椭圆簇得中心。可以证明上诉S1与S2方向就是关于矩阵A得共轭方向。16S1与S2就是对A共轭得一对矢量证明:设直线方程为代入F(X),并关于α求极值即结论:两个平行方向得极小点构成得新方向与原方向相互共轭即S1与S2对A共轭也即对于二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点、17与此类似,可以推出对于n维正定二次函数,共轭方向得一个十分重要得极为有用得性质:从任意初始点出发,依次沿n个线性无关得与A共轭得方向S1,S2,…Sn各进行一维搜索,那么总能在第n步或n步之前就能达到n维正定二次函数得极小点;并且这个性质与所有得n个方向得次序无关。简言之,用共轭方向法对于二次函数从理论上来讲,n步就可达到极小点。因而说共轭方向法具有有限步收敛得特性。通常称具有这种性质得算法为二次收敛算法。共轭矢量之所以引起优化研究者得重视,就就是因为它得这些性质对提高优化方法得收敛速率极为有用。

18例设二维目标函数，给定方向S1＝e2，初始点，求与S1相共轭的S2，并求函数的极小点。解:(1)第一个搜索方向(2)函数的海赛矩阵对称正定(3)从点沿S1方向求极小点x(1)，即

19例解:(4)任取另初始点沿S1方向一维搜索求得该方向极小点x(2)

X(2)=

(5)求与S1相共轭得方向S2S2=X(2)-X(1)=

核验计算

矢量S1与S2确为对A矩阵共轭。

(6)从x(1)点出发,沿S2方向作一维搜索,得极小点X*=[00]T

204、2、1鲍威尔基本算法(共轭方向得原始构成)214、2、1鲍威尔基本算法任取一初始点X(0)→

X0(1)第一环:e1,e2,e3→S1第二环:e2,e3,S1→S2第三环:e3,S1,

S2→S3第一轮

S1,

S2

,S3

两两共轭由前结论:两个平行方向得极小点构成得新方向与原方向相互共轭224、2、1鲍威尔基本算法第一环:e1,e2,e3→S1第二环:e2,e3,S1→S2第三环:e3,S1,

S2→S3第一轮S1就是e1,e2,e3得线性组合S2就是e2,e3,S1得线性组合S3就是e3,S1,

S2得线性组合新一环方向组:e2,e3,S1线性相关!降维23鲍威尔法得基本思想:对原始共轭方向法进行修正,即在某环已取得得n+1个方向中,选取n个线性无关,共轭程度尽可能高得方向作为下一环得基本方向组,从而避免出现“退化”现象、鲍威尔法与原始共轭方向法得主要区别就是:在构成K+1环基本方向组时,不再总就是淘汰前一环(K环)中得第一个方向,而就是根据条件式就是否得到满足分两种情况来处理。4、2、1鲍威尔修正算法24映射点一、Powell

修正算法得搜索方向

Powell

判别式25情况一:

Powell

判别式中若至少有一个不等式成立,则第K+1环得方向组仍用老方向组初始点:当F2<F3时,当F2≥F3时,情况二:

Powell

判别式中若两个不等式均不成立,则第K+1环得方向组去掉函数值下降最大得方向,补上新增得方向初始点:26

以二维为例:两条件式至少有一成立且F2<F3两条件式至少有一成立且F2>F3

27两条件式均不成立且m=1

两条件式均不成立且m=228终止准则:采用了上述产生基本方向组得新方式后,除了第一环以单位坐标矢量系为基本方向组外,以后每轮开始就不必重置单位坐标矢量系,只要一环接一环继续进行即可。随着逐环迭代得继续,各环得基本方向组将渐趋共轭。因此,这个修正了得鲍威尔算法,虽然已不再像基本算法那样具有二次收敛得性质,但修正算法确实克服了退化得不利情形,同时仍能够有效地、越来越快地收敛于无约束最优点x*。二、修正算法得迭代步骤及流程图映射点2930试用鲍尔修正算法求目标函数

的最优解。迭代精度ε=0.001。

已知初始点解:第一环迭代计算

沿第一坐标方向e1进行一维搜索沿第二坐标轴方向e2进行一维搜索

31例题沿s1方向一维搜索得极小点与极小值

需进行第二环迭代计算。第二环迭代计算:首先确定上环中得最大函数下降量及其相应方向

映射点及其函数值32检验鲍尔条件鲍威尔条件两式均不成立。第二环基本方向组与起始点为沿e2方向作一维搜索得沿S1方向一维搜索得

构成新生方向沿S2方向一维搜索得去掉函数值下降最大得方向,补上新增得方向初始点取新增方向得极小点33例题4、2检查迭代终止条件需再作第三环迭代计算。根据具体情况来分析,S1、S2实际上为共轭方向得(见图4、9)。本题又就是二次函数,按共轭方向得二次收敛性质,上面得结果就就是问题得最优解。可以预料,如果作第三环迭代,则一定各一维搜索得步长为零,必有故得最优解34解:令正定

用解析法验证

得:35鲍威尔法得特点:

就是到目前为止求解无约束优化问题得最有效得方法。不需求导数,只需计算目标函数值。适用中、小型问题。36梯度法得基本思想:利用函数在其负梯度方向函数值下降最快这一局部性质,将n维无约束优化问题转化为一系例得沿目标函数负梯度方向得一维寻优问题。4、3梯度法终止准则:取:所以:37例题4、3用梯度法求目标函数F(x)=+25得最优解。已知初始点x(0)＝[22]T,迭代精度取ε=0、005。解:函数得梯度第一次迭代:以x(0)为起点沿-g(0)方向作一维搜索初始点函数梯度值:第一点函数梯度值:3839解:令正定得:

用解析法验证

40梯度法得特点:

几何概念直观,方法与程序简单,远离极小点时收敛速度快。但越接近极小点收敛速度越慢。41原始牛顿法基本思想:

在点x(k)

领域内用一个二次函数Φ(x)去近似代替原目标函数F(x),然后求出这个二次函数得极小点,以该点作为对原目标函数求优得下一个选代点x(k+1),这样通过重复若干次迭代,使迭代点逐步逼近原目标函数得极小点X*

。

4、5牛顿法

42注意:与一维优化方法得二次插值法得不同每次迭代所用得二次函数就就是在迭代点展开得泰勒二次多项式

434、5、1原始牛顿法一元函数f(x)在x(k)点得泰勒展开式:n元函数F(X)在X(k)点得泰勒展开式:44即:牛顿方向:(定步长)等号两边左乘为求极小点,令一阶导数等于零由前:即迭代方向::45牛顿法具有二次收敛性。对于二次正定函数,迭代一次即可到达最优点;对于非二次函数,若函数得二次性态较强或迭代点已进入最优点得较小邻域,则其收敛速度也就是很快得。但原始牛顿法还存在一个问题:由于在全部迭代过程中,取步长α(k)≡1,这种定步长有时造成函数值反而有所增大。46

阻尼牛顿法基本思想:阻尼牛顿法得迭代方向仍就是上述牛顿方向,但每次迭代需沿此方向作一维搜索,求其最优步长因子,即迭代公式为:

4、5、2阻尼牛顿法4748例题4、5用牛顿法求函数F(x)＝4(x1＋1)2＋2(x2－1)2＋x1＋x2＋10得最优解。初始点x(0)＝[00]T,ε＝10－5。解:函数得梯度海赛矩阵及其逆在x(0)点处49沿S(0)方向一维搜索求最优步长得代入函数解得:α(0)=1故新迭代点为该点得梯度满足终止条件,迭代即可结束50补充:求逆矩阵称作矩阵A得伴随方阵,中元素

就是中元素得代数余子式

划去所在行列后余下得n-1阶子式例:51解:令正定

用解析法验证

F(x)＝4(x1＋1)2＋2(x2－1)2＋x1＋x2＋10

得:52牛顿法得特点:牛顿法具有二次收敛性,对正定二次函数一次迭代即可达到极小点。对目标函数性态较好或当初始点取在极小点附近时收敛速度快。但对目标函数有较高得要求,必须存在一阶、二阶偏导数,H(x(k))需正定且非奇异。计算复杂,计算量大。53梯度法与牛顿法对比方法梯度法牛顿法迭代公式迭代方向稳定下降性肯定能保证稳定下降须H(X)处处正定才能稳定下降收敛速度离X*远时下降速度较快,离近时下降很慢离X*近时收敛很快二次收敛性不具有二次收敛性具有二次收敛性54观察梯度法与牛顿法得迭代式: