无约束问题的最优化条件PPT课件

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

2、降的速度越慢，算法收敛速度慢,15,5.3 牛顿法,16,17,18,19,解,1)计算,2)方向,20,3)求最优步长,代入目标函数得,令,4)判断,即为所求,21,22,23,24,四.牛顿法的进一步修正,25,26,27,5.4 信赖域法,28,29,30,31,32,33,34,5.5 拟牛顿法,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,最速下降法,61,牛顿法,62,拟牛顿法,63,单纯形搜索法,64,对偶拟牛顿法,65,最小二乘法,66,67,68,69,5.6 共轭方

3、向法,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,5.7 powell算法,89,90,91,92,一.Powell算法,1964年由Powell提出，后经Zangwoll（1967年）和Brent（1973年）改进，是迄今为止最有效的直接搜索法,该算法有效地利用了迭代过程中的历史信息，建立起能加速收敛的方向,有理论基础，以二次函数f(x) = 1/2 xTAx + bTx + c为模型进行研究,为什么选择二次函数作为模型,1、在非线性目标函数中，最简单的是二次函数，故任何对一般函数有效 的方法首先应对二次函数有效,2、在最

4、优点附近，非线性函数可用一个二次函数作近似，故对二次函数 使用良好的方法，通常对一般函数也有效,3、很多实际问题的目标函数是二次函数,93,定理: 假设 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)*。 则有：向量d = x(0)*x(1)*与d(0), d(1), , d(m-1) 互为A

5、共轭,94,以上定理说明如果已知前m个共轭 方向，可以找到第m+1个共轭方向,95,二.Powell算法的迭代过程,一边搜索， 一边找共轭方向,共分n个阶段，每一阶段都进行n+1次搜索，最后产生一个共轭方向,96,二维空间中的Powell方法示意图,以二次函数f(x1 , x2 ) 为例,97,例:用Powell法求解,98,99,可以验证d(2,3)与d(2,2)关于A共轭,100,101,三.Powell算法流程,开始,102,例: 用powell算法求解(书上例11.4.2,103,104,105,106,5.8 单纯形法,107,一. 单纯形(Simplex)定义,108,二. 单纯形

6、搜索法的基本思想,单纯形法是利用单纯形的顶点计算目标函数值, 按一定规则进行探索性搜索,对搜索区单纯形顶点的函数值进行比较,判断目标函数的变化趋势,确定有利的单纯体移动的方向,109,单纯形搜索法中,单纯形的移动是通过反射、收缩、 扩张三种运算来实现,最坏点,次坏点,最好点,三.单纯形的搜索移动,110,为作反射运算,需求出除最坏点外的其余所有顶点的重心,反射运算求反射点,反射系数，常取,二维单纯形,111,有四种可能,单纯形搜索法对不同情况给出相应处理措施,112,113,114,情形三,进行收缩运算,115,116,情形四,进行收缩运算,计算收缩点,与情形三处理相同,只是收缩点的计算不同,

7、产生新的单纯形后,继续下一轮迭代,117,118,119,5.9 坐标轮换法,120,121,基本算法,122,a）搜索有效；（b）搜索低效；（c）搜索无效,存在的问题,123,5.10 模式搜索法,124,一.模式搜索法,125,126,127,128,129,130,131,132,133,134,5.11 旋转方向法,135,旋转方向法是Rosenbrock于1960年提出,旋转方向法是在每一次迭代中采用变步长的轴向移动, 然后利用轴向的旋转来产生一组新的方向作为下一次迭代的轴向，其目的是为了加快收敛速度,136,与模式搜索法中的轴向移动的区别,137,新轴向的产生,为了提高求解效率,需要进行各轴向的旋转,并以新的n个单位正交方向组作为下一次迭代的轴向,从探测阶段的开始点指向该探测阶段的结束点的方向 xk+1-xk 很可能是有利于目标函数下降的方向,因此新的一组轴向应该包括这个方向,