第四章无约束优化方法.pptx

第四章无约束优化方法第四章无约束优化方法第四章无约束优化方法第四章无约束优化方法34 4、1 1 坐标轮换法坐标轮换法基本思想基本思想:把一个把一个n维无约束最优化维无约束最优化问题转化为依次沿问题转化为依次沿n个坐标轴方向得个坐标轴方向得一维最优化问题。一维最优化问题。即迭代方向依次为即迭代方向依次为:第一轮第一轮:任取一初始点任取一初始点X(0)一维搜索求一维搜索求得得一维搜索求一维搜索求得得第二轮第二轮:4终止准则终止准则:上式点距准则中得上式点距准则中得两点应就是一轮迭两点应就是一轮迭代得始点与终点代得始点与终点利用一维优化方法确定沿该方向上具有最小目标函数值得步长利用一维优化方法确定沿该方向上具有最小目标函数值得步长,即即:minF(X:minF(X(k)(k)+S S(k)(k)=F(X)=F(X(k)(k)+(k)(k)S S(k)(k)迭代步长迭代步长得确定得确定:5坐坐标轮换法法得得流流程程图 6坐标轮换法得特点坐标轮换法得特点:具有程序结构简单具有程序结构简单,易于掌握等优点。但收敛慢易于掌握等优点。但收敛慢,适用于适用于n10得低维优化问题得低维优化问题。另收敛速度与等值线得形状有关另收敛速度与等值线得形状有关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、95025 10例题例题4、1 用解析法验证用解析法验证 解解:令令正定正定114、2 鲍威尔鲍威尔(Powell)法法v鲍威威尔尔法法就就是是直直接接搜搜索索法法中中一一个个十十分分有有效效得得算算法法。该算算法法就就是是沿沿着着逐逐步步产生生得得共共轭方方向向进行行搜搜索索得得,因因此此本本质上上就就是是一一种种共共轭方向法方向法,鲍威威尔尔法得收法得收敛速率速率较快。快。v以以共共轭方方向向作作为搜搜索索方方向向,不不只只限限于于鲍威威尔尔法法,也也用用于于其其她她一一些些较为有有效效得得方方法法,可可以以统称称为共共轭方方向向法法。因因此此,共共轭方方向向得得概概念在念在优化方法研究中占有重要得地位。化方法研究中占有重要得地位。v共共轭轭方方向向在在最最优优化化问问题题中中得得应应用用就就是是基基于于其其具具有有一一个个重重要要性性质质,即即:设设 S1、S2、Sn就就是是关关于于A得得n个个互互相相共共轭轭得得向向量量,则则对对于求正定二次函数于求正定二次函数 得极小点得极小点,从从 任任意意初初始始点点出出发发,依依次次沿沿Si(i=1,2,n)方方向向进进行行一一维维最最优优化化搜索搜索,至多至多n步便可以收敛到极小点、步便可以收敛到极小点、122、5 关于优化方法中搜寻方向得理论基础关于优化方法中搜寻方向得理论基础2、5、2 共轭方向共轭方向(见第二章见第二章)一、共轭方向得基本概念一、共轭方向得基本概念若有两个若有两个n维矢量维矢量S1、S2,对对nn阶对称正定矩阵阶对称正定矩阵A能满足能满足:称称n维空空间矢量矢量S1与与S2对A共共轭共共轭矢量所代表得方向称矢量所代表得方向称为共共轭方向。方向。正交正交:可以瞧作就是共可以瞧作就是共轭得特例得特例例例:(1)共共轭并正交并正交大家学习辛苦了，还是要坚持继续保持安静继续保持安静继续保持安静继续保持安静14例例:(2)共共轭但不正交但不正交设设A A为为nnnn阶实对称正定矩阵阶实对称正定矩阵,有一组非零得有一组非零得n n维矢量维矢量S S1 1、S S2 2、SqSq,若满足若满足 ij ij 则称矢量系则称矢量系S Si i(i(i1 1,2 2,qn)qn)对于矩阵对于矩阵A A共轭共轭 15以二维函数为例以二维函数为例:二维正定二次函数具有两个重要特性二维正定二次函数具有两个重要特性:1 1)二维正定二次函数得等值线就是同心得椭圆族二维正定二次函数得等值线就是同心得椭圆族,且椭圆中心就且椭圆中心就 就是正定二元二次函数得极小点。就是正定二元二次函数得极小点。2)2)过同心椭圆族中心过同心椭圆族中心x*x*作任意直线作任意直线,此直线与诸椭圆交点处得切线此直线与诸椭圆交点处得切线相互平行。或者说相互平行或者说:两条平行得任意方向得切线两条平行得任意方向得切线,其切点得连线必通其切点得连线必通过椭圆簇得中心。过椭圆簇得中心。可以证明上诉可以证明上诉S S1 1与与S S2 2方向就是方向就是关于矩阵关于矩阵A A得共轭方向。得共轭方向。16S1与与S2就是对就是对A共轭得一对矢量共轭得一对矢量证明证明:设直线方程为设直线方程为代入代入F(X),并关于并关于求极值求极值即即结论结论:两个平行方向得极小点构成两个平行方向得极小点构成得新方向与原方向相互得新方向与原方向相互共轭共轭即即S S1 1与与S S2 2对对A A共轭共轭也即对于也即对于二维正定二次函数只要分别沿两个共轭方向寻优二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点即可找到最优点、17v与此类似与此类似,可以推出对于可以推出对于n n维正定二次函数维正定二次函数,共轭方向得一个共轭方向得一个十分重要得极为有用得性质十分重要得极为有用得性质:从任意初始点出发从任意初始点出发,依次沿依次沿n n个个线性无关得与线性无关得与A A共轭得方向共轭得方向S S1 1,S S2 2,S Sn n各进行一维搜索各进行一维搜索,那么那么总能在第总能在第n n步或步或n n步之前就能达到步之前就能达到n n维正定二次函数得极小点维正定二次函数得极小点;并且这个性质与所有得并且这个性质与所有得n n个方向得次序无关。简言之个方向得次序无关。简言之,用共轭用共轭方向法对于二次函数从理论上来讲方向法对于二次函数从理论上来讲,n n步就可达到极小点。因步就可达到极小点。因而说共轭方向法具有有限步收敛得特性。通常称具有这种性而说共轭方向法具有有限步收敛得特性。通常称具有这种性质得算法为二次收敛算法。质得算法为二次收敛算法。v共轭矢量之所以引起优化研究者得重视共轭矢量之所以引起优化研究者得重视,就就是因为它得这就就是因为它得这些性质对提高优化方法得收敛速率极为有用。些性质对提高优化方法得收敛速率极为有用。18例例设二二维目目标函数函数，给定方向定方向S1e2，初始点，初始点，求与，求与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*=0 0T 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,e3S1得线性组合得线性组合S3就是就是e3,S1,S2得线性组合得线性组合新一环方向组新一环方向组:e2,e3,S1 线性相关线性相关!降维降维23鲍威尔法得基本思想鲍威尔法得基本思想:对原始共轭方向法进行修正对原始共轭方向法进行修正,即在某即在某环已取得得环已取得得n+1n+1个方向中个方向中,选取选取n n 个线性无关个线性无关,共轭程度尽可能共轭程度尽可能高得方向作为下一环得基本高得方向作为下一环得基本方向组方向组,从而避免出现从而避免出现“退化退化”现现象、象、鲍威尔法与原始共轭方向法得主要区别就是鲍威尔法与原始共轭方向法得主要区别就是:在构成在构成K+1K+1环基本方向组时环基本方向组时,不再总就是淘汰前一环不再总就是淘汰前一环(K(K环环)中得中得第一个方向第一个方向,而就是根据条件式而就是根据条件式就是否得到满足分两种情况来处理。就是否得到满足分两种情况来处理。4、2、1 鲍威尔修正算法鲍威尔修正算法24映射点一、一、Powell 修正算法得搜索方向修正算法得搜索方向Powell 判别式判别式25情况一情况一:Powell 判别式中若至少判别式中若至少 有一个不等式成立有一个不等式成立,则则第第K+1环得方向组仍用老方向组环得方向组仍用老方向组 初始点初始点:当当F2 F3时时,当当F2F3时时,情况二情况二:Powell 判别式中若两个判别式中若两个 不等式均不成立不等式均不成立,则则第第K+1环得方向组环得方向组去掉函数值下降最大得方向去掉函数值下降最大得方向,补上新增得方向补上新增得方向初始点初始点:26 以二维为例以二维为例:两条件式至少有一成立且两条件式至少有一成立且F2F3 27两条件式均不成立且两条件式均不成立且m=1 两条件式均不成立且两条件式均不成立且m=2 28终止准则终止准则:采用了上述产生基本方向组得新采用了上述产生基本方向组得新方式后方式后,除了第一环以单位坐标矢除了第一环以单位坐标矢量系为基本方向组外量系为基本方向组外,以后每轮开以后每轮开始就不必重置单位坐标矢量系始就不必重置单位坐标矢量系,只只要一环接一环继续进行即可。随要一环接一环继续进行即可。随着逐环迭代得继续着逐环迭代得继续,各环得基本方各环得基本方向组将渐趋共轭。因此向组将渐趋共轭。因此,这个修正这个修正了得鲍威尔算法了得鲍威尔算法,虽然已不再像基虽然已不再像基本算法那样具有二次收敛得性质本算法那样具有二次收敛得性质,但修正算法确实克服了退化得不但修正算法确实克服了退化得不利情形利情形,同时仍能够有效地、越来同时仍能够有效地、越来越快地收敛于无约束最优点越快地收敛于无约束最优点x*。二、修正算法得迭代步骤及流程图二、修正算法得迭代步骤及流程图映射点2930试用用鲍尔尔修正算法求目修正算法求目标函数函数 的最的最优解。解。迭代精度迭代精度=0.001。已知初始点已知初始点解解:第一第一环迭代迭代计算算 沿第一坐沿第一坐标方向方向e1进行一行一维搜索搜索沿第二坐沿第二坐标轴方向方向e2进行一行一维搜索搜索 31例题例题 沿沿s1方向一方向一维搜索得极小点与极小搜索得极小点与极小值 需需进行第二行第二环迭代迭代计算。算。第二第二环迭代迭代计算算:首先确定上首先确定上环中得最大函数下降量及其相中得最大函数下降量及其相应方向方向 映射点及其函数映射点及其函数值32检验鲍尔尔条件条件鲍威威尔尔条件两式均不成立。第二条件两式均不成立。第二环基本方向基本方向组与起始点与起始点为沿沿e2方向作一方向作一维搜索得搜索得沿沿S1方向一方向一维搜索得搜索得 构成新生方向构成新生方向沿沿S2方向一方向一维搜索得搜索得去掉函数值下降最大得方向去掉函数值下降最大得方向,补上新增得方向补上新增得方向初始点取新增方向得极小点初始点取新增方向得极小点33例题例题 4、2 检查迭代终止条件检查迭代终止条件需再作第三环迭代计算。需再作第三环迭代计算。根据具体情况来分析根据具体情况来分析,S1、S2实际上上为共共轭方向得方向得(见图4、9)。本。本题又就是二次函数又就是二次函数,按共按共轭方向得二次收方向得二次收敛性性质,上面得上面得结果就就是果就就是问题得最得最优解。可以解。可以预料料,如果作第三如果作第三环迭代迭代,则一一定各一定各一维搜索得步搜索得步长为零零,必有必有故得最优解故得最优解34解解:令令正定正定 用解析法验证用解析法验证 得得:35鲍威尔法得特点鲍威尔法得特点:就是到目前为止求解无约束优化问题得最有就是到目前为止求解无约束优化问题得最有效得方法。不需求导数效得方法。不需求导数,只需计算目标函数值。只需计算目标函数值。适用中、小型问题。适用中、小型问题。36梯度法得基本思想梯度法得基本思想:利用函数在其负梯度方向函数值利用函数在其负梯度方向函数值下降最快这一局部性质下降最快这一局部性质,将将n n维无约束优化问题转化维无约束优化问题转化为一系例得沿目标函数负梯度方向得一维寻优问题。为一系例得沿目标函数负梯度方向得一维寻优问题。4、3 梯度法梯度法终止准则终止准则:取取:所以所以:37例例题题4、3 用用梯梯度度法法求求目目标标函函数数F(x)=+25 得得最最优优解解。已已知知初初始点始点x(0)2 2T,迭代精度取迭代精度取=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(x11)22(x21)2x1x210得最优解。初始点得最优解。初始点x(0)0 0T,105。解解:函数得梯度函数得梯度海赛矩阵及其逆海赛矩阵及其逆在在x(0)点处点处49沿沿S(0)方向一维搜索求最优步长得方向一维搜索求最优步长得代入函数解得代入函数解得:(0)=1故新迭代点为故新迭代点为该点得梯度该点得梯度满足终止条件满足终止条件,迭代即可结束迭代即可结束50补充补充:求逆矩阵求逆矩阵称作矩阵称作矩阵A得伴随方阵得伴随方阵,中元素中元素 就是就是 中元素中元素 得代数余子式得代数余子式 划去划去 所在行列后余下得所在行列后余下得n-1阶子式阶子式例例:51解解:令令正定正定用解析法验证用解析法验证 F(x)4(x11)22(x21)2x1x210得得:52牛顿法得特点牛顿法得特点:牛顿法具有二次收敛性牛顿法具有二次收敛性,对正定二次函数一次迭代即可达对正定二次函数一次迭代即可达到极小点。对目标函数性态较好或当初始点取在极小点附到极小点。对目标函数性态较好或当初始点取在极小点附近时收敛速度快。近时收敛速度快。但对目标函数有较高得要求但对目标函数有较高得要求,必须存在一阶、二阶偏导必须存在一阶、二阶偏导数数,H(x(k)需正定且非奇异。计算复杂需正定且非奇异。计算复杂,计算量大。计算量大。53梯度法与牛顿法对比梯度法与牛顿法对比方方 法法梯梯 度度 法法牛牛 顿顿 法法迭代公式迭代公式迭代方向迭代方向稳定下降性稳定下降性肯定能保证稳定下降肯定能保证稳定下降须须H(X)处处正定处处正定才能稳定下降才能稳定下降收敛速度收敛速度离离X*远时下降速度较快远时下降速度较快,离近时下降很慢离近时下降很慢离离X*近时收敛很快近时收敛很快二次收敛性二次收敛性不具有二次收敛性不具有二次收敛性具有二次收敛性具有二次收敛性54观察梯度法与牛顿法得迭代式观察梯度法与牛顿法得迭代式:变尺度法得基本思想变尺度法得基本思想:设法构造一个对称正定阵设法构造一个对称正定阵Ak代替代替,并并在在选选代代计计算算中中,使使其其逐逐渐渐逼逼近近 。因因此此,一一旦旦达达到到极极值值点点附附近近,就可望达到牛顿法得收敛速度就可望达到牛顿法得收敛速度,同时又避免了矩阵得求逆计算。同时又避免了矩阵得求逆计算。其选代公式其选代公式:Ak就就是是就就是是根根据据需需要要构构造造得得nn阶阶对对称称矩矩阵阵,它它就就是是随随着着迭迭代代点点位位置得变化而变化得。置得变化而变化得。梯度法梯度法:牛顿法牛顿法:4、6 DFP变尺度法变尺度法554、6、2 变尺度法变尺度法构造矩阵得产生构造矩阵得产生递推方法产生递推方法产生:校正矩阵校正矩阵 变尺度法采用构造矩尺度法采用构造矩阵来代替牛来代替牛顿法中海法中海赛矩矩阵得逆得逆阵,其主要目其主要目得之一就是得之一就是为了避免了避免计算二算二阶偏偏导数与数与计算它得逆矩算它得逆矩阵,力力图仅用梯度用梯度与其她一些易于与其她一些易于获得得信息来确定迭代方向。得得信息来确定迭代方向。分析一下海分析一下海赛矩矩阵与梯度之与梯度之间得关系。得关系。564、6、2 变尺度法变尺度法构造矩阵得产生构造矩阵得产生海赛矩阵与梯度之间得关系海赛矩阵与梯度之间得关系位移矢量梯度矢量差拟牛牛顿条件条件(拟牛牛顿方程方程)PII-(84-85)DFP公式公式574、6、3 对对DFP法几个问题得说明与讨论法几个问题得说明与讨论(1)DFP公式总有确切得解。(2)构造矩阵得正定性。(3)DFP法搜索方向得共轭性。(4)关于算法得稳定性。v为了提高实际计算中得稳定性,一方面应对一维搜索提出较高得精度要求,另一方面在发生破坏正定性时,将构造矩阵重置为单位矩阵E重新开始,通常采用得简单办法就是在n次迭代后重置单位矩阵。4、6、4 DFP算法得迭代步算法得迭代步骤58例题例题 4、6 v用DFP变尺度法求目标函数F(x)4(x15)2(x26)2得最优解。已知初始点x(0)8 9T,迭代精度0、01。解解:第一次迭代第一次迭代:式中最优步长(0)应该用一维搜索方法在计算机上求解。为了说明问题,又因为此例目标函数简单,所以用解析法来求: