现代设计方法-优化设计4-无约束优化

现代设计方法优化设计部分黄正东，吴义忠2015年本章主要内容优化设计概述优化设计的数学基础一维探索优化方法无约束优化方法约束问题优化方法优化设计若干问题优化设计概述优化设计的数学基础一维探索优化方法无约束优化方法约束问题优化方法优化设计若干问题坐标轮换法梯度法共轭方向法鲍威尔法共轭梯度法牛顿法变尺度法无约束优化方法试想•一个盲人在山顶，他怎么能够尽快找到山谷的家？1.坐标轮换法(1)算法思想1.将多维问题，降为多个一维问题；2.在一维上可使用黄金分割法等直接采样优化方法；3.轮换地以每一个坐标轴作为一维搜索方向。x1x2X0X1X2X3f(X)=c基于一维搜索的优化过程开始给定x、d的初始值计算a*使f(x+a·d)极小xx+a*d满足收敛条件？形成新的d结束坐标轮换法(2)算法1.初始化，0，M（最大迭代次数），n（维度）,k=1,x=x(0).2.对于i=1,2,…,n，进行2.1Si=ei;2.2i=minf(x+Si)2.3x=x+iSi,f=f(x).3.如果|iSi|,或者kM,转步4;否则，k=k+1,转步2。4.输出x,f.结束。一共进行了多少次一维搜索？方向正、负？坐标轮换法(3)举例)0,0(22),(min)0(2221212121Xxxxxxxxxf确定正负方向一维搜索(1)坐标轮换法(3)举例)0,0(22),(min)0(2221212121Xxxxxxxxxf(1)坐标轮换法)0,0(22),(min)0(2221212121Xxxxxxxxxf01）2（1S(3)举例10）2（2S……以上举例是手算实现该算法，用计算机实现时，需用进退法和黄金分割法实现一维搜索。10）k（2S坐标轮换法(4)算法分析1.对于维数较高的优化问题，搜索时间过长，一般当n10时，则不应采用此方法。2.算法效率与f(x)形态有关。收敛速度最快收敛速度慢搜索无效基本思想梯度方向是函数值增加最快的方向，而负梯度方向是函数下降最快的方向，所以梯度法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向一维搜索，直到满足精度要求为止。因此，梯度法又称为最速下降法。2.梯度法f(x0)df(x)=2f(x)=1x0f(x)=0设在某次迭代中已取得迭代点X(k)，从该点出发，取负梯度方向为搜索方向S(k)，即：)()()()()()()()(kkkkkXfXfSXfS或niiknkxfXfxfxfxfXf12)(T21)()(,,,)(其中，这样，第k+1次迭代计算所得的新点为：)()()()()()()1(kkkkkXfXfXX)()()()()1(kkkkXfXX或上式即为梯度法迭代公式。因为X(k)已知，故和不难求出，只要知道步长后，就可以得到新点X(k+1)。由于每次迭代能保证，如此反复计算，最后总能达到最优点X*。为了使目标函数值在搜索方向S(k)上获得最多的下降，每次迭代都进行一维搜索求最优步长，即求)()(kXf)()(kXf)()()()1(kkXfXf)()(min)()()()()(kkkkkSXfSXf迭代步骤1）任选初始点X(0)，计算精度ε，令k=0；2）计算和；3）收敛判断，A.若，则X(k)为近似最优点，停止迭代，输出最优解：，；B.若，则转下一步继续迭代；4）令)()(kXf)()(kXf?)()(kXf)()(kXf)(*kXX)()()(*kXfXf)()(kXf)()()()()(kkkXfXfS5）一维搜索确定最优步长因子，使6）计算；7）令k=k+1，转2）。)(k)(min)()()()()()(kkkkkSXfSXf)()()()1(kkkkSXX例1：用梯度法求函数的极小值，初始点，计算精度。2221)1()1()(xxXfTX0,0)0(01.05.0)12(2)()(2222)(22)(2222)(*2)0()0()0()0()0(21XfSXXXfSXfxxXf一次搜索即可解：（1）如果转（2），否则转（5）。970.0243.0)()(492.16)(164)(82)()0()0()0()0()0(21XfXfSXfXfxxXf1)0()(Xf例2.用一阶梯度法求目标函数f(X)=x12+4x22在初始点X(0)=[22]T，迭代精度=10-2下的最优解。（2）492.16645.7)(970.0243.022)0()0()1()0()0()0()0()1(dXdfSXX（3），并转（1）。（4）第7次迭代后，成立，停止迭代。（5）取时，f(X*)=2.596×10-6≈0092.0476.1157.20)()1()0()0()1(XdXdf,000096.0，0016.0)7(TXTXX000096.00016.0*)7(01.00032.0)(1)7(Xf比较上面两个例题，能得出什么样的结论？梯度法的特点：负梯度方向只是函数值在点X(k)的邻域内下降最快的方向，离开该邻域以后函数值不一定下降最快。因此，采用负梯度方向，从局部看函数值下降快，从全局看却要走很多弯路。因此，梯度法的收敛速度较慢。梯度法的迭代过程，每相邻两步的搜索方向是垂直的，也就是说梯度法的迭代路线是呈锯齿形前进的。梯度法迭代过程中，当迭代点离理论极小点较远时，一次迭代的函数值下降量大。迭代点离极小点越近，函数值下降的速度就越慢。因此，梯度法常与其它优化方法结合使用。即第一步采用梯度法，后面采用其它的方法确定搜索方向。梯度法的收敛速度与目标函数的性质有关。如果目标函数的等值线（面）为同心圆（球），则无论从哪里出发，只需要一次搜索就能达到极小点。例1情况例2情况1）椭圆的共轭方向3.共轭方向法SiS椭圆的一簇平行弦的中点联系通过圆心。并称中点连线方向S与平行弦方向Si为相互共轭方向（关于椭圆）。2）共轭方向的代数定义定义:设A为n×n阶实对称正定矩阵，而S1、S2为在n维欧氏空间En中的两个非零向量，如果满足式S1TAS2=0则称向量S1与S2关于实对称正定矩阵A是共轭的。共轭是正交关系的推广：当A=I时，共轭就是正交。由A对称正定,得：所以,即共轭是仿射变换Q下的正交.0)()()()(212121212/12/12/12/1SSQSQSQSQSASSQQUDUDUDDUDUUATTTTTTTTT关于二元二次函数Hesse矩阵A共轭的几何意义与正交概念的关系变换前变换后几何定义与代数定义是等价的。设X(1):minf(X1+aSi)X(2):minf(X2+aSi)X(1)=X1+a1SiX(2)=X2+a2SiX(1)X(2)则Si与S=X(2)-X(1)关于A共轭.X1X2SiS0)(0)()()('0)()()(')()1()2()2(222)1(11121ASSXXASbAXSSaXfSabAXSSaXfSabAXfAXXXbCXfTiTiTiiTiTiiTiTT关于步长a的导数为0共轭方向法特点：对于二次函数,沿n个共轭方向依次进行一维搜索,在第n次搜索时达到整体最优解。n为X维数.X1X2SiS第一轮:S1(1),S2(1)不一定共轭,产生S(1).第二轮:取S1(2)=S2(1)S2(2)=S(1),产生S(2).第三轮:取S1(3)=S(1)S2(3)=S(2),所以,由定义知,对于二次函数,S(1),S(2)共轭.第一轮第二轮多维共轭方向法算法过程：坐标轮换法的扩展：每轮方向首个方向被去掉，增加新的方向共轭方向法算法分析1.对于二次函数,经过维数n轮(每轮n次一维搜索)循环后,第n轮中的n个搜索方向相互共轭.所以,第n轮能达到最优解.2.对于非二次函数,经过n轮循环后,第n轮中的n个搜索方向对于f(x)的二次局部近似函数的Hessian矩阵只是近似相互共轭,虽然有较高的逼近,但不一定到达极值点.3.算法可能出现n个方向线性相关.例如,当一维搜索中a=0时,X1(2)=X0(2)时S(1)与S(2)线性相关.此时,不能得到最优解.4.对于非二次函数,经过n轮循环后,可以重新选择n个初始搜索方向,以减小前面搜索方向线性相关或退化的影响.4.鲍威尔（Powell）方法该方法是对共轭方向法的改进，避免了出现搜索方向线性相关的情况.基本思想:定理：设A是正定矩阵，n个向量Si已经被规范化为：[Si]TASi=1.设Q为以Si为列的矩阵，则当且仅当Si关于A相互共轭时，行列式的值达到它的最大值。1.倾斜方向Sn+1代替的不一定是S1，而是下降最大的某方向Sm；2.这种替代，只有在|Q（k+1)||Q(k)|的情况下执行，其它情况仍用前一轮的搜索方向。每次尽量使Q行列式值最大(避免线性相关），再与上一个比较，看Sm是否可以被替换Powell方法231)(2)(2123113)()(1,...,2,1)()(13)(2)(01)(0)()(1)(5.0))(2(|)()(|max)(),(),(2fffffffffXfXfXffXffXffXXXkmkmkikinikmknknkkknknX0(k)X1(k)Xn(k)Xn+1(k)条件（*）X(k)n˗X(k)0|Q（k+1)||Q(k)|的等价条件反射点N个搜索中函数值下降最大值（第m个方向）(a)当|Q(k+1)||Q(k)|或条件（*）满足时，Sn+1(k)作为Sn(k+1）；(b)否则，第k+1轮的搜索方向组与第k轮相同。新方向：Sn+1(k)=Xn(k)–X0(k)被去掉的方向：Sm为函数值下降最大的方向如果条件成立，去掉Sm，将Sn+1(k)加到末尾。1.初始化S(1)i=ei,k=1,X(1)0=X(0).2.依次一维搜索:X(k)i=X(k)i-1+aS(k)i:minf(X(k)i-1+aS(k)i),i=1,2,…,n3.计算反射点:S(k)n+1=X(k)n-X(k)0,X(k)n+1=2X(k)n-X(k)04.计算5.转步6.否则否则转步7.6.一维搜索:X=X(k)n+aS(k)n+1:minf(X(k)n+aS(k)n+1)转步7.7.如果结束.否则.k=k+1,转步2.第m个被去掉算法分析1.共轭方向法具有二次收敛性,即二次目标函数n步收敛,效率高,但可能退化到局部空间（某个维数被忽略）.2.与共轭方向法不同,斜方向替代前面的搜索方向是有条件的,所替代的方向是有选择的.3.Powell法不再具有二次收敛性(由于所替换的方向S不定),但计算较稳定,一般反映效果不错.共轭方向法与Powell方法算法思想结合共轭方向法和梯度法的优点,取相互共轭的搜索方向,同时取为与当前点梯度方向相关方向.一般共轭梯度法:1.初始化.g0=f(x0),选择S0使S0Tg00.如S0=-g02.如果|gk|eps,结束.3.一维搜索xk+1=xk+akSk:minf(xk+akSk).4.选择Sk+1,使Sk+1THSj=0,j=0,1,…,k.H=2f(xk)5.k=k+1,转步2.*共轭梯度法Fletcher-Reeves共轭梯度法选择：x2-f(xk+1)Skxkxk+1βkSkSk＋1x*x1Sk+1=-gk+1+βkSkkkkTkkTkkgggggg111/共轭梯度法算法1.初始化.g0=f(x0