《无约束优化方法》PPT课件.ppt

1,第四章,无约束优化方法,2,4.1 概 述 尽管工程实际中的问题几乎都是约束优化问题，但无约束优化方法仍是优化方法中最基本的组成部份，因为解约束问题的一些有效方法就是将约束问题转化为无约束问题求解。何况还有很多问题本身就是无约束问题，人们对无约束优化方法研究也比较成熟。 解无约束优化问题的一类方法是需利用函数的一阶或二阶导数，它们要充分利用函数的解析式子故称为解析法(间接法)。另一类方法在迭代过程中只需计算函数值，故称直接法。相对直接法而言解析法又称间接法。因为解析法充分利用了函数的解析性质，所以它们的收敛速度多数比直接法快，但可靠性一般较低。,3,4.2 最速下降法 (Gradient Method) 一.基本思想 梯度方向是函数值变化率最大的方向：沿着梯度方向函数值 上升最快;沿负梯度方向函数值下降最快。用负梯度方向作为搜 索的方向，即: 或用单位负梯度矢量来表示 这种方法是用函数变化率最大的方向作为搜索方向，又称最 速下降法。 二、迭代公式,4,或 式中，步长k可以任选，只要保证f(X(k+1) f(X(k)。通常 是沿负梯度方向进行一维搜索，找出其最优点作为下一步的迭 代点。即： 三、迭代过程及程序框图 四、练习 用梯度法求解f(X)=x12+2x22的极小点 设初始点X(0)=4,4T 要求迭代一次,并验证相邻两次迭代的搜索方向互相垂直。,5,五、梯度法讨论 优点：程序简单，每次迭代所需的计算量小，贮存量也少； 对初始点要求不高，即使从一个不太好的初始点出发，往往也 能收敛到局部极小点。 缺点：收敛的速度慢。 原因：最速下降是函数值 在某一点的变化率而言，是 一个局部的性质，从全局来 看并不是最速下降方向。 因此梯度法的搜索路线呈直 角锯齿形状，所得到的搜索点为绕道逼近最优点的，除非目标 函数是圆。,6,4.3 牛顿类法 (Newtons Method) 一.迭代公式及特点 1.迭代公式 f(X)在迭代点X (k)具有一阶、二阶的连续偏导数，则可将其 展开成Taylor级数，并略去高于二次的项，得到： 二次函数 (X)的极值点 如果将X作为一个逼近点X(k+1),牛顿法的一般迭代公式 式中 如果f(X)是正定二次函数，则H(X)是个常数矩阵，逼近式 X (k)=X*是准确的，由X (k)出发只要迭代一次可得到极小点。,7,2.特点 (1).收敛的速度快，即使到了 最优点邻域时也很快收敛于函数 的局部最优点。 (2).采用定步长迭代，因而 就不能保证每次迭代中目标函 数是下降的。 原因： (X)仅为目标函数 f(X)在X (k)点附近的近似表达 式。 X(k+1)点是 (X)在牛顿方 向上的极小点，而非原函数的 极小点。 解决办法：阻尼牛顿法。,1,2,3,4,5,0,1,2,3,-1,-2,F,C,D,A,B,E,8,二.阻尼牛顿法 1.迭代公式 沿牛顿方向-H(X(k)-1f(X(k)作一维搜索,迭代公式： 其中 k使 在f(X)的Hessian矩阵H (X (k)处处正定的情况下，阻尼牛顿 法能保证每次迭代函数值有所下降。即保持了牛顿法收敛快的 特性，又不要求初始点选得很好。 2.程序框图 三、有关牛顿法的讨论 1.不能保证每次迭代函数值都下降。 原因：Hessian矩阵不定。,9,2.若Hessian矩阵奇异,其逆阵不存在,就不能构成牛顿方 向，迭代无法进行。 3.构造牛顿方向较困难。 是否能找到另一种更好的方法？ a.能像梯度法那样，只需计算目标函数的一阶导数，对初始 点的要求不高，能较好的突破函数的非二次性而迅速趋近于极 值点； b.同时又像牛顿法那样，一但迭代点进入极值点的邻近区域 时很快地收敛于最优点。,10,4.4 坐标轮换法 (Cyclic Coordinate Method) 一.基本思想 降维的思想，将一个n维问题转化为一系列的一维优化问题 来求解。每次将n-1个变量固定，只对一个变量作一维搜索。 进行一维搜索找到X1(1) 进行一维搜索找到X2(1) 进行一维搜索找到Xn(1) 到此完成一轮迭代，X的上角标表示迭代的轮次，下角标表 示坐标轴的序号。每次都是以前一次搜索的终点作本次一维搜 索的起点，一轮迭代完后又重头开始直至收敛，故此法又称变 量轮换法(Alternating Variable Method)。 二、步长的确定 1、随机选取法，保证函数值下降。,11,2、最优步长 Xi=Xi-1+iEi 3、加速步长法 在每次一维搜索中,都是以=0开始, 随后在函数值下降的情况下20 ,40 , 倍增的速度加大步长，直至函数值不再下 降，取其前步长为最终步长。,12,三.迭代过程及框图,13,四.坐标轮换法的讨论 1、坐标轮换法具有程序简单，易于掌握的优点，但它的计 算效率较低，因此它虽然步步在登高，但相当于沿两个垂直方 向在爬山，路途迂迴曲折，收敛很慢，因此它适用于维数较低 (一般n10)的目标函数求优。 2、有“脊线”的目标函数等值线的情形,沿坐标轴方向函数值 不一定下降。,0,p,A,脊线,14,五、练习 用最优步长法求解 f (X)=(x1-2)4+(x1-2x2)2的极小点。 初始点X(0)=0,3T，要求迭代一轮。 请注意沿坐标轴移动的方向。,15,四.模式搜索法(Pattern Search Method&Hooke-Jeeves) 模式搜索法是对坐标轮换法的改进。由两类移动组成： 探测性移动探测一个有利的方向 模式移动循有利的方向加大步长移动 探测性移动的起点为参考点，用R0, R1, 表示，其终点称为基 点，用B0, B1, 表示。模式移动则以基点开始，而以参考点为 终点。两种移动交替进行，即： B0R0B1R1B2BiRiBi+1Ri+1 通常先取一点为整个过程的起始点，记为B0R0 ，即它既是一个参考点又是一个基点。,16,17,4.5 鲍威尔法 (Powells Method) 一.共轭方向的概念(Conjugate Direction) 对于具有正定矩阵H的二元二次函数 依次沿s(0)和s(1)这两个方向 搜索即可到达无约束 极值点X*。,18,1.定义：设A为n阶实对称正定矩阵，若有两 个n维矢量s1和s2，满足s1TAs2=0,则称矢量s1和 s2对矩阵A共轭，共轭矢量的方向称为共轭方 向。 如果A=I(单位阵)，就成为s1Ts2=0，s1和s2方 向正交，即与单位阵共轭的方向是正交方向， 所以正交方向可以说是共轭方向的一个特例。 但正交和共轭不能混为一谈，有的正交不共 轭，有的共轭不正交。,19,20,2.正定二次函数的特点 (1)正定二次二元函数的等值线是椭圆线簇,椭圆线簇的中心 即目标函数的极值点。 (2)过同心椭圆线簇中心作任意直线,此直线与诸椭圆交点处 的切线相互平行。 反之过两平行线与椭圆切点X(a)和 X(b)的连线必通过椭圆的中心。因此 只要沿方向X(a)X(b)进行一维搜索， 就能找出函数的极小点。 而且平行线的方向S1和切点连线 的方向S2为共轭方向,即满足： s1TAs2=0,S1,0,S2,21,3.结论 正定二次二元函数依次沿两个互相共轭的方向作一 维搜索，就能得到极小点。推广到正定二次n元函数 中去,可得出只要依次沿n个互相共轭的方向进行一维 搜索就可得到极小点。如果一个算法的搜索方向是互 相共轭的，就称为共轭方向法。,22,二、基本思想 本质就是共轭方向法，只不过不求导数而已，故又 称不求导数的共轭方向法。 Powell法先沿着n个方向作一维搜索后，把初始点 和终点连结起来产生一个新方向，把原来的第一个方 向去掉，把新方向加在最后，就构成一组共轭方向， 继续进行下去。也可以这样看与模式搜索的关系，假 设沿n个方向进行一维搜索后，又在相应的模式方向 进行了一维搜索，考虑模式方向可能比坐标轴方向 好，所以下一次就去掉一个坐标轴方向而加进模式方 向。,23,二、迭代过程 以二维问题为例： ,24,三、Powell法存在的问题 (1)、对于非二次函数，用Taylor展开只有接近中心处是椭 圆，故收敛就不是二次收敛，即n次不一定达到最优点。 (2)、共轭方向一定是线性无关的。出现线性相关或近似线 性相关，使一些方向漏掉，降维，称为退化，故对Powell法进 行修改，即不一定固定每次去掉的都是第一个方向，而是“哪 个方向好就朝哪个方向走”，从而避免出现线性相关的“退 化”现象。 (3)、修正方法 增加模式移动： X0k、Xnk、Xn+1k分别称为一轮迭代的起点、终点和反射点。 其函数值分别记为：,25,同时，计算各中间点处的函数值，并记为： 计算n个函数值之差。记作： 取 是否要对原方向组进行替换的判别条件： 若满足，则进行替换；若不满足，则下轮仍用原方向组。,26,对于n维问题,27,四、迭代框图,满足： 下一轮不替换方向,不满足： 下一轮 替换方向,28,五、练习 用鲍威尔法求解无约束极值问题 给定 迭代一轮，求出下一轮的初始点和迭代方向。 六、编程实现Powell算法,29,30,Matlab优化工具箱 Fminsearch:用的算法是单纯形搜索法。 Fminunc:不提供梯度矩阵采用线性搜索法，否则信赖域法。,31,32,33,