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

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

1、5.1 无约束问题的 最优性条件,1局部极小点 2严格局部极小点 3全局（总体）极小点 4严格全局（总体）极小点。 注：在非线性规划中，大多数算法都致力于求最优化问题的局部极小点，一般求全局极小点极为困难，仅当问题为凸规划时，局部极小为全局极小。,一、极小点的概念,二、无约束问题最优性条件,5.2 最速下降法,解:,例1:用最速下降法求,的极小值,只迭代一次,二.算法终止标准,三、最速下降算法收敛性定理,四.最速下降法的收敛速度,五.算法特点,相邻两次迭代的搜索方向是正交的,迭代点列呈锯齿形前进，迭代点越靠近最优解附近,目标函数值下降的速度越慢，算法收敛速度慢。,5.3 牛顿法,解:,1)计算

2、,2)方向,3)求最优步长,代入目标函数得：,令,4)判断,即为所求,四.牛顿法的进一步修正,5.4 信赖域法,5.5 拟牛顿法,最速下降法,牛顿法,拟牛顿法,单纯形搜索法,对偶拟牛顿法,最小二乘法,5.6 共轭方向法,5.7 powell算法,一.Powell算法,1964年由Powell提出，后经Zangwoll（1967年）和Brent（1973年）改进，是迄今为止最有效的直接搜索法。,该算法有效地利用了迭代过程中的历史信息，建立起能加速收敛的方向,有理论基础，以二次函数f(x) = 1/2 xTAx + bTx + c为模型进行研究。,为什么选择二次函数作为模型?,1、在非线性目标函数

3、中，最简单的是二次函数，故任何对一般函数有效 的方法首先应对二次函数有效；,2、在最优点附近，非线性函数可用一个二次函数作近似，故对二次函数 使用良好的方法，通常对一般函数也有效；,3、很多实际问题的目标函数是二次函数。,定理: 假设 1. n元函数f(x) = 1/2 xTAx + bTx + c中矩阵A是对称正定的； 2. 向量d(0), d(1), , d(m-1) (mn)是互相A共轭的； x(0), x(1)是不同的任意两点，分别从x(0), x(1)出发，依次沿d(0), d(1), , d(m-1) 作一维精确搜索，设最后一次一维搜索的极小点分别为x(0)*和x(1)*。 则有：

4、向量d = x(0)*x(1)*与d(0), d(1), , d(m-1) 互为A共轭。,以上定理说明如果已知前m个共轭 方向，可以找到第m+1个共轭方向,二.Powell算法的迭代过程,一边搜索， 一边找共轭方向,共分n个阶段，每一阶段都进行n+1次搜索，最后产生一个共轭方向,二维空间中的Powell方法示意图,以二次函数f(x1 , x2 ) 为例,例:用Powell法求解,可以验证d(2,3)与d(2,2)关于A共轭,三.Powell算法流程,开始,例: 用powell算法求解(书上例11.4.2),5.8 单纯形法,一. 单纯形(Simplex)定义,二. 单纯形搜索法的基本思想,单纯

5、形法是利用单纯形的顶点计算目标函数值, 按一定规则进行探索性搜索,对搜索区单纯形顶点的函数值进行比较,判断目标函数的变化趋势,确定有利的单纯体移动的方向.,单纯形搜索法中,单纯形的移动是通过反射、收缩、 扩张三种运算来实现,最坏点,次坏点,最好点,三.单纯形的搜索移动,为作反射运算,需求出除最坏点外的其余所有顶点的重心,反射运算求反射点, 反射系数，常取,二维单纯形,有四种可能：,单纯形搜索法对不同情况给出相应处理措施,情形三：,进行收缩运算,情形四：,进行收缩运算,计算收缩点,与情形三处理相同,只是收缩点的计算不同,产生新的单纯形后,继续下一轮迭代,5.9 坐标轮换法,基本算法,（a）搜索有

6、效；（b）搜索低效；（c）搜索无效,存在的问题,5.10 模式搜索法,一.模式搜索法,5.11 旋转方向法,旋转方向法是Rosenbrock于1960年提出,旋转方向法是在每一次迭代中采用变步长的轴向移动, 然后利用轴向的旋转来产生一组新的方向作为下一次迭代的轴向，其目的是为了加快收敛速度,与模式搜索法中的轴向移动的区别,新轴向的产生,为了提高求解效率,需要进行各轴向的旋转,并以新的n个单位正交方向组作为下一次迭代的轴向,从探测阶段的开始点指向该探测阶段的结束点的方向 xk+1-xk 很可能是有利于目标函数下降的方向,因此新的一组轴向应该包括这个方向.,旋转方向法的收敛性问题一直没有解决,Davies，Swann和Campey将旋转方向法中沿轴向的变步长移动改为沿轴向做最优一维搜索，给出了修正的旋转方向法，修正的旋转方向法是收敛的,