无约束问题的最优化条件.ppt

《无约束问题的最优化条件.ppt》由会员分享，可在线阅读，更多相关《无约束问题的最优化条件.ppt（140页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、自动化学院自动化学院5.1 5.1 无约束问题的无约束问题的 最优性条件最优性条件1 1局部极小点局部极小点2 2严格局部极小点严格局部极小点3 3全局（总体）极小点全局（总体）极小点4 4严格全局（总体）极小点。严格全局（总体）极小点。注：在非线性规划中，大多数算法都致力于求最优化注：在非线性规划中，大多数算法都致力于求最优化问题的局部极小点，一般求全局极小点极为困难，仅问题的局部极小点，一般求全局极小点极为困难，仅当问题为凸规划时，局部极小为全局极小。当问题为凸规划时，局部极小为全局极小。一、极小点的概念二、无约束问题最优性条件二、无约束问题最优性条件自动化学院自动化学院5.2 5.2 最

2、速下降法最速下降法最速下降法又称为最速下降法又称为负梯负梯度法，由度法，由CauchyCauchy于于18471847年给出。是最为古老但又十分基本的一年给出。是最为古老但又十分基本的一种方法。种方法。最速下降法最速下降法解决的是具有连续可微的目标函解决的是具有连续可微的目标函 数的无约束极值问题。数的无约束极值问题。最速下降法的基本思想：从当前点最速下降法的基本思想：从当前点xk出发寻找出发寻找 使得目标函数下降最快的方向，即负梯度方向使得目标函数下降最快的方向，即负梯度方向。优点：迭代过程简单，使用方便。优点：迭代过程简单，使用方便。一一.最速下降法最速下降法关于梯度的复习：关于梯度的复习

3、：梯度是一个向量。梯度是一个向量。n n元函数元函数f(x1,x2,xn)在点在点x处的梯度为：处的梯度为：梯度的方向与函数梯度的方向与函数f 的等值线的一个法线方的等值线的一个法线方 向相同，从较低的等值线指向较高的等值线。向相同，从较低的等值线指向较高的等值线。梯度的方向就是函数梯度的方向就是函数f 的值增加最快的方向，的值增加最快的方向，其相反方向就是函数值降低最快的方向。其相反方向就是函数值降低最快的方向。解解:例例1:1:用最速下降法求用最速下降法求的极小值的极小值,只迭代一次只迭代一次代入目标函数得：令继续迭代,计算可得二二.算法终止标准算法终止标准三、最速下降算法收敛性定理三、最

4、速下降算法收敛性定理四四.最速下降法的收敛速度最速下降法的收敛速度五五.算法特点算法特点 相邻两次迭代的搜索方向是正交的相邻两次迭代的搜索方向是正交的,迭代点列呈迭代点列呈锯齿形前进，锯齿形前进，迭代点越靠近最优解附近迭代点越靠近最优解附近,目标函目标函数值下降的速度越慢，数值下降的速度越慢，算法收敛速度慢。算法收敛速度慢。自动化学院自动化学院 5.3 5.3 牛顿法牛顿法例例2:2:用牛顿法求用牛顿法求的极小值的极小值,解:1)1)计算计算2)2)方向方向3)3)求最优步长求最优步长代入目标函数得：代入目标函数得：令令4)4)判断判断即为所求即为所求四四.牛顿法的进一步修正牛顿法的进一步修正

5、自动化学院自动化学院 5.4 5.4 信赖域法信赖域法自动化学院自动化学院 5.5 5.5 拟牛顿法拟牛顿法例例4:4:著名的著名的rosenbrokerosenbroke函数函数,亦称香蕉函数亦称香蕉函数该问题有唯一极小点该问题有唯一极小点观察不同迭代算法所得到的结果观察不同迭代算法所得到的结果最速下降法牛顿法拟牛顿法单纯形搜索法对偶拟牛顿法最小二乘法自动化学院自动化学院 5.6 5.6 共轭方向法共轭方向法自动化学院自动化学院5.7 powell算法算法问题问题1:1:在实际问题中往往得不到目标函数在实际问题中往往得不到目标函数的梯度的梯度的解析形式的解析形式.只能采用近似计算只能采用近似

6、计算摄动近似法摄动近似法:计算计算在迭代点在迭代点附近分别在附近分别在方向分别给一方向分别给一微小偏差微小偏差,计算计算问题问题2:2:在实际问题中可能得不到目标函数在实际问题中可能得不到目标函数的解析形式的解析形式.只有动态的目标函数值只有动态的目标函数值PIDPID调节器调节器r re e+-y yu u一个典型工业过程控制系统结构图一个典型工业过程控制系统结构图控制对象控制对象选择误差型目标函数选择误差型目标函数,即时间乘绝对误差积分即时间乘绝对误差积分,现需要现需要在目标函数在目标函数:意义下意义下,寻找一组最优的寻找一组最优的PIDPID调节器参数调节器参数使使由于目标函数不是显含被

7、寻参数的函数由于目标函数不是显含被寻参数的函数,并且并且目标函数是在求解系统动态过程中才能计算出来目标函数是在求解系统动态过程中才能计算出来,显然无法采用前面讨论的间接搜索法显然无法采用前面讨论的间接搜索法 为了避免计算目标函数梯度为了避免计算目标函数梯度,产生了许多只需要计产生了许多只需要计算目标函数值的搜索方法算目标函数值的搜索方法称直接搜索法称直接搜索法方法方法单纯形法单纯形法坐标轮换法坐标轮换法模式搜索法模式搜索法共轭方向方法共轭方向方法 一一.Powell.Powell算法算法 19641964年年 由由 PowellPowell提提 出出，后后 经经 ZangwollZangwol

8、l（19671967年年）和和BrentBrent（19731973年）改进，是迄今为止最有效的直接搜索法。年）改进，是迄今为止最有效的直接搜索法。该算法有效地利用了迭代过程中的历史信息，建立起能加速收敛的方向该算法有效地利用了迭代过程中的历史信息，建立起能加速收敛的方向,有理论基础，以二次函数有理论基础，以二次函数f(x)=1/2 xTAx+bTx+c为模型进行研究。为模型进行研究。为什么选择二次函数作为模型为什么选择二次函数作为模型?1 1、在非线性目标函数中，最简单的是二次函数，故任何对一般函数有效、在非线性目标函数中，最简单的是二次函数，故任何对一般函数有效 的方法首先应对二次函数有效

9、；的方法首先应对二次函数有效；2 2、在最优点附近，非线性函数可用一个二次函数作近似，故对二次函数、在最优点附近，非线性函数可用一个二次函数作近似，故对二次函数 使用良好的方法，通常对一般函数也有效；使用良好的方法，通常对一般函数也有效；3 3、很多实际问题的目标函数是二次函数。、很多实际问题的目标函数是二次函数。定理定理:假设假设1.1.n元函数元函数f(x)=1/2 xTAx+bTx+c中矩阵中矩阵A是对称正定的；是对称正定的；2.2.向量向量d d(0)(0),d,d(1)(1),d,d(m-1)(m-1)(mn)(mn)是互相是互相A共轭的；共轭的；3.x(0),x(1)是是不不同同的

10、的任任意意两两点点，分分别别从从x(0),x(1)出出发发，依依次次沿沿d d(0)(0),d d(1)(1),d d(m-1)(m-1)作作一一维维精精确确搜搜索索，设设最最后后一一次次一一维维搜索的极小点分别为搜索的极小点分别为x(0)*和和x(1)*。则有：向量则有：向量d=x(0)*x(1)*与与d d(0)(0),d,d(1)(1),d,d(m-1)(m-1)互为互为A共轭。共轭。以上定理说明如果已知前以上定理说明如果已知前m个共轭个共轭方向，可以找到第方向，可以找到第m+1个共轭方向个共轭方向d(1)x(0)x(1)d(0)d(0)x(0)*x(1)*x*x(0)x(1)d(0)d

11、(0)d(1)d(1)x(0)*x(1)*d(2)x*二二.PowellPowell算算法的迭代过程法的迭代过程一边搜索，一边搜索，一边找共轭方向一边找共轭方向共分共分n个阶段，每一阶段都进行个阶段，每一阶段都进行n+1次次搜索，最后产生一个共轭方向搜索，最后产生一个共轭方向任意任意n个线性无关的方向个线性无关的方向二维空间中的二维空间中的PowellPowell方法示意图方法示意图e(2)e(1)d(0)=e(1)d(1)=e(2)以以二次函数二次函数f(x1,x2)为例为例d(0)d(1)x(1,0)x(1,1)x(1,2)d(1)x(2,2)x(2,0)x(2,1)x*对于二次函数对于二

12、次函数,x*即为极小点即为极小点例例:用用PowellPowell法求解法求解可以验证可以验证d d(2,3)(2,3)与与d d(2,2)(2,2)关于关于A A共轭共轭三三.PowellPowell算法流程算法流程开始开始给定给定x(0),e(1),e(2),e(n)及及 否否x(k)=x(k,n)+k d(n-1)其中其中 k为最优步长为最优步长 k=1,d(i)=e(i+1),i=0,1,n-1 j=0,x(k,j)=x(k-1)x(k,j+1)=x(k,j)+j d(j)其中其中 j为最优步长为最优步长 j=j+1 j=n满足精度满足精度否否k=k+1 x*=x(k+1)结束结束是是

13、是是 d(i)=d(i+1),i=0,1,n-2例例:用用powellpowell算法求解算法求解(书上例书上例11.4.2)11.4.2)几点说明几点说明1、迭代中逐次产生的是共轭方向，是较好的搜索方向，所以、迭代中逐次产生的是共轭方向，是较好的搜索方向，所以Powell法法 又称方向加速法；又称方向加速法；2、原始算法共轭方向不一定能保证。、原始算法共轭方向不一定能保证。因为只有在每次搜索均为一维完全精确搜索因为只有在每次搜索均为一维完全精确搜索的条件下，每个阶段产生的方向才是相互共轭的条件下，每个阶段产生的方向才是相互共轭的方向。的方向。但实际一维搜索一般是近似的，产生的方向不但实际一维

14、搜索一般是近似的，产生的方向不一定共轭，有时甚至是线性相关的，导致搜一定共轭，有时甚至是线性相关的，导致搜索空间降维，这时将找不到真正的极小点。索空间降维，这时将找不到真正的极小点。d(1)x(0)x(1)d(0)d(0)x(0)*x(1)*x*d(1)对于一般函数对于一般函数,n个阶段迭代后一般得不到极小点个阶段迭代后一般得不到极小点,但由于共轭方向的个数只有但由于共轭方向的个数只有n个个,如果继续按上述如果继续按上述方法迭代方法迭代,产生的方向就不再是相互共轭方向了产生的方向就不再是相互共轭方向了,收敛速度会变慢收敛速度会变慢.一种简单改进策略一种简单改进策略:每进行每进行n个阶段的迭代，

15、或当收敛速度个阶段的迭代，或当收敛速度变慢时，以当前点为变慢时，以当前点为 起点，回到第一步重新开始起点，回到第一步重新开始1.基本思想基本思想为克服搜索方向的线性相关问题，为克服搜索方向的线性相关问题，Powell对原始算法进对原始算法进行了改进。行了改进。如何判定方向组是如何判定方向组是“最相互共轭最相互共轭”的的?在每个阶段产生新的方向在每个阶段产生新的方向d后后,更换方向组的方法更换方向组的方法不是一不是一律去掉第一个方向律去掉第一个方向d(0),而是有选择地去掉某个方向而是有选择地去掉某个方向 d(J),原原则是则是使新的方向组使新的方向组“最相互共轭最相互共轭”（四）改进的（四）改

16、进的PowellPowell算法算法定理定理:设设A是是n阶对称正定矩阵，方向组阶对称正定矩阵，方向组d(0),d(1),d(n-1)是规范化的是规范化的,即：即：d(i)T A d(i)=1，(i=0,1,n-1),置置Q d(0),d(1),d(n-1)，则方向组则方向组d(0),d(1),d(n-1)相互相互A共轭的充要共轭的充要条件为：条件为：行列式行列式|Q|的值达到它的最大值。的值达到它的最大值。以上定理是改进以上定理是改进PowellPowell算法的理论基础算法的理论基础自动化学院自动化学院5.8 单纯形法单纯形法一一.单纯形单纯形(Simplex)(Simplex)定义定义例

17、如例如:一维单纯形为一个线段一维单纯形为一个线段,二维单纯形为三角形二维单纯形为三角形三维单纯形为四面体三维单纯形为四面体定义定义:n n 维空间中用维空间中用n n+1+1个顶点所构成的凸多面体称为个顶点所构成的凸多面体称为单纯形单纯形,当这些顶点的距离都相等时当这些顶点的距离都相等时,称正单纯形称正单纯形.x1 x2 x3 x2 x1 二二.单纯形搜索法的基本思想单纯形搜索法的基本思想 单纯形法是利用单纯形的顶点计算目标函数值单纯形法是利用单纯形的顶点计算目标函数值,按一定规则进行探索性搜索按一定规则进行探索性搜索,对搜索区单纯形顶点的对搜索区单纯形顶点的函数值进行比较函数值进行比较,判断

18、目标函数的变化趋势判断目标函数的变化趋势,确定有确定有利的单纯体移动的方向利的单纯体移动的方向.单纯形搜索法中,单纯形的移动是通过反射、收缩反射、收缩、扩张扩张三种运算来实现设是构成单纯形的n+1个顶点.最坏点次坏点最好点三三.单纯形的搜索移动单纯形的搜索移动为作反射运算为作反射运算,需求出除最坏点外的其余所有需求出除最坏点外的其余所有顶点的重心顶点的重心反射运算反射运算求反射点求反射点重心重心反射点反射点 反射系数反射系数，常取常取二维单纯形有四种可能：有四种可能：单纯形搜索法对不同情况给出相应处理措施单纯形搜索法对不同情况给出相应处理措施下面分析下面分析与与的大小关系的大小关系情形一：情形

19、一：比最好点比最好点还要好还要好进行扩张运算进行扩张运算计算扩张点计算扩张点扩张系数扩张系数二维单纯形：二维单纯形：1)如果如果,扩张成功扩张成功,以以取代取代,由由构成新单纯形构成新单纯形2)如果如果,扩张失败扩张失败,以以取代取代,由由构成新单纯形构成新单纯形情形二：情形二：,以以取代取代,由由构成新单纯形构成新单纯形情形三：情形三：进行收缩运算进行收缩运算计算收缩点计算收缩点收缩系数收缩系数1)如果如果,收缩成功收缩成功,以以取代取代,由由构成新单纯形构成新单纯形2)如果如果,收缩失败收缩失败,进行缩边进行缩边,以最以最为中心为中心,其余顶点均向其余顶点均向移近一半距离移近一半距离,好点

20、好点得到新的单纯形得到新的单纯形情形四：情形四：进行收缩运算进行收缩运算计算收缩点计算收缩点与情形三处理相同与情形三处理相同,只是收缩点的计算不同只是收缩点的计算不同产生新的单纯形后产生新的单纯形后,继续下一轮迭代继续下一轮迭代小结小结:以上四种情况以上四种情况,不论属于哪一种不论属于哪一种,所得到的所得到的 新的单纯形新的单纯形,必有一个顶点其函数值小于或必有一个顶点其函数值小于或 等于原单纯形各顶点上的函数值等于原单纯形各顶点上的函数值,重复以上重复以上 过程过程,得到一系列单纯形得到一系列单纯形,向极小点逼近向极小点逼近,直直 至满足收敛标准为止至满足收敛标准为止.四四.单纯形搜索法的收

21、敛标准单纯形搜索法的收敛标准当函数在当前单纯形的当函数在当前单纯形的n+1n+1个顶点的目标函数值个顶点的目标函数值的标准差小于指定精度时的标准差小于指定精度时,迭代结束迭代结束.例例:用单纯形搜索法求解下列问题用单纯形搜索法求解下列问题给定初始单纯形的顶点为给定初始单纯形的顶点为:取取自动化学院自动化学院5.9 坐标轮换法坐标轮换法l 坐标轮换法由坐标轮换法由Desopo于于1959年提出年提出.l 坐标轮换法是每次搜索只允许一个变量变化，其余变量坐标轮换法是每次搜索只允许一个变量变化，其余变量 保持不变，即沿保持不变，即沿坐标方向坐标方向轮流进行搜索的寻优方法。轮流进行搜索的寻优方法。l

22、坐标轮换法把坐标轮换法把多变量多变量的优化问题轮流地转化成的优化问题轮流地转化成单变量单变量的的 优化问题优化问题.基本算法基本算法 给定初始点给定初始点x0,从从x0出发，依次沿坐标轴方向出发，依次沿坐标轴方向 ei=(0,0,1,0,0)T，i=1,2,n,进行最优一维搜索进行最优一维搜索,即即否则，从点否则，从点xn出发出发，令，令x0=xn再依次沿坐标轴方向再依次沿坐标轴方向ei 进行进行最优一维搜索最优一维搜索.如果如果,则停则停,（a a）搜索有效；（）搜索有效；（b b）搜索低效；（）搜索低效；（c c）搜索无效）搜索无效存在的问题存在的问题自动化学院自动化学院5.10 模式搜索

23、法模式搜索法一.模式搜索法例例:用模式搜索法计算用模式搜索法计算该问题有唯一全局极小点该问题有唯一全局极小点,取初始点取初始点,步长步长=0.5,=0.5,=0.5,=0.5,=10=10-10-10 自动化学院自动化学院5.11 旋转方向法旋转方向法l 旋转方向法是旋转方向法是RosenbrockRosenbrock于于19601960年提出年提出l 旋转方向旋转方向法是在每一次迭代中采用变步长法是在每一次迭代中采用变步长的轴向移动的轴向移动,然后利用轴向的旋转来产生一组然后利用轴向的旋转来产生一组新的方向作为下一次迭代的轴向，其目的是为新的方向作为下一次迭代的轴向，其目的是为了加快收敛速度

24、了加快收敛速度与模式搜索法中的轴向移动的区别与模式搜索法中的轴向移动的区别l 沿沿n个单位正交向量个单位正交向量d1,d2,.,dn作轴向移动作轴向移动 l 每一次轴向移动每一次轴向移动的步长在探测过程中独立地随时变化，的步长在探测过程中独立地随时变化，即按照探测成功增大步长，探测失败缩短步长即按照探测成功增大步长，探测失败缩短步长l 沿沿n个轴向移动结束后个轴向移动结束后,即得新的迭代点即得新的迭代点.然后进入新一然后进入新一 轮的变步长轴向移动，此时的轴向为一组由原轴向产轮的变步长轴向移动，此时的轴向为一组由原轴向产 生的正交向量组生的正交向量组.新轴向的产生新轴向的产生为了提高求解效率为

25、了提高求解效率,需要进行各轴向的旋需要进行各轴向的旋转转,并以新的并以新的n个单位正交方向组作为下个单位正交方向组作为下一次迭代的轴向一次迭代的轴向,从探测阶段的开始点指从探测阶段的开始点指向该探测阶段的结束点的方向向该探测阶段的结束点的方向 xk+1-xk很可能是有利于目标函数下降的方向很可能是有利于目标函数下降的方向,因因此新的一组轴向应该包括这个方向此新的一组轴向应该包括这个方向.l 旋转方向法的收敛性问题一直没有解决旋转方向法的收敛性问题一直没有解决l Davies Davies，SwannSwann和和CampeyCampey将旋转方向法中沿轴向的变将旋转方向法中沿轴向的变步长移动改为沿轴向做最优一维搜索，给出了修正的步长移动改为沿轴向做最优一维搜索，给出了修正的旋转方向法，修正的旋转方向法是收敛的旋转方向法，修正的旋转方向法是收敛的