工程优化设计-无约束直接法

工程优化设计黄正东二0一0年九月内容提要•工程优化问题建模•优化数学理论•一维搜索方法•无约束问题直接搜索方法•无约束问题间接接搜索方法•约束问题直接搜索方法•线性规划与二次规划问题求解•约束问题间接搜索方法•启发式算法•优化软件系统无约束直接搜索方法一.坐标轮换法直接法:利用迭代过程已有信息和再生信息进行试探和求优,不需要用到函数导数和分析性质。(1)算法思想轮换地以每一个坐标轴作为一维搜索方向的优化搜索方法。无约束直接搜索方法一.坐标轮换法(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)算法分析1.对于维数较高的优化问题，搜索时间过长，一般当n10时，则不应采用此方法。2.算法效率与f(x)形态有关。无约束直接搜索方法二.单纯形方法(1)算法思想单纯形（Simplex）概念:n维空间中的n+1面体f(xh)=max{f(x0),f(x1),…,f(xn)}---高点f(xl)=min{f(x0),f(x1),…,f(xn)}---低点x=nhiiinx,01---除最高点外的所有点的形心xhx2x1xxrxr=x+a(x-xh)---反射点，a反射系数，一般取a=1.无约束直接搜索方法二.单纯形方法分三种情况选择新点:xe=x+y(xr-x)若f(xr)f(xe),则xe-xh否则，xr-xh1。如果f(xl)f(xr),进一步扩展扩展系数y1,一般y=2.xhx2xlxxrxef(xr)比所有单纯形点上值小不进一步扩展,避免狭窄单纯形无约束直接搜索方法二.单纯形方法分三种情况选择新点:xe=x+y(xr-x)若f(xr)f(xe),则xe-xh否则，xr-xh1。如果f(xl)f(xr),进一步扩展扩展系数y1,一般y=2.xhx2xlxxrxef(xr)比所有单纯形点上值小无约束直接搜索方法二.单纯形方法分三种情况选择新点:2。如果max{f(xi),ih}f(xr)f(xl),则xr-xhxhx2x1xxrxef(xr)在单纯形点上值之间,但最少比第二最大值小.分三种情况选择新点:3。如果f(xr)max{f(xi),ih},则f(xh’)=min{f(xh),f(xr)}压缩xc=x+b(xh’-x),0b1,压缩系数，一般b=0.5.如果f(xc)f(xh’),xc-xh否则，以xl为中心压缩整个单纯形：xi=xi+0.5(xl-xi),i=0,1,2,…,nxhx2xlx2xhxhx2x1xxrxcxhx2xxrxcx1f(xr)可以在单纯形点上值之上,但最少比第二最大值大.试探顺序无约束直接搜索方法二.单纯形方法终止条件:2/10211})]()([{niinxfxf初始单纯形:x0=(a1,a2,…,an)x1=(a1+p,a2+q,…,an+q)x2=(a1+q,a2+p,…,an+q)……xn=(a1+q,a2+q,…,an+p)211,211nnqannnp=a为单纯形边长无约束直接搜索方法(2)算法（略）1.初始单纯形所选的尺度与方向对结果有大的影响。2.单纯形可能退化到低维空间情况。3.有人指出，对于变量很多的情况，如n10时，效率不高。二.单纯形方法(3)算法分析无约束直接搜索方法(1)算法思想三.模式搜索法(Hooke-Jeeves方法)通过在坐标轴方向进行探测性移动,确定下降方向,然后,沿着下降方向进行一次模式性移动.第1次探测第2次探测模式移动第1次探测第2次探测模式移动22成功失败下一步,步长减小下一步,步长不变无约束直接搜索方法三.模式搜索法(Hooke-Jeeves方法)探测性移动:X0(k)-ae1X0(k)+ae1X0(k)移动X0(k)-ae1,X0(k),X0(k)+ae1的f(X)最小点,记为X1(k).a为探测移动步长.也可以用一维搜索确定最优位置,但每一步计算量增大.10,无约束直接搜索方法三.模式搜索法(Hooke-Jeeves方法)模式移动:X0(k)Xn+1(k)Xn(k)Xn+1(k)=Xn(k)+[Xn(k)-X0(k)]模式移动没进行优化比较!(2)算法无约束直接搜索方法1.效率比坐标轮换法高。2.算法比单纯形法稳定,没有退化情况。3.但也只适用于变量较少的优化问题，不过,可作为其他搜索方法的初始点生成。三.模式搜索法(3)算法分析无约束直接搜索方法四.共轭方向法及其改进后的Powell法(1)概念与性质无约束直接搜索方法四.共轭方向法及其改进后的Powell法(1)概念与性质A对称正定,所以,A=UTDU=UTD1/2D1/2U=(D1/2U)T(D1/2U)=QTQS1TAS2=S1TQTQS2=(QS1)T(QS2)=S1S2=0即共轭是仿射变换Q下的正交.关于二次函数Hesse矩阵A共轭的几何意义与正交概念的关系无约束直接搜索方法性质设类似与正交化过程无约束直接搜索方法性质3)设X(1):minf(X1+aSi)X(2):minf(X2+aSi)X(1)=X1+a1SiX(2)=X2+a2Si则Si与S=X(2)-X(1)共轭.X1X2SiS无约束直接搜索方法性质4)设,沿n个共轭方向依次进行一维搜索,在第n次搜索时达到整体最优解.n为X维数.X1X2SiS无约束直接搜索方法四.共轭方向法及其改进后的Powell法(2)共轭方向法第一轮:S1(1),S2(1)不一定共轭,产生S(1).第二轮:取S1(2)=S2(1)S2(2)=S(1),产生S(2).第三轮:取S1(3)=S(1)S2(3)=S(2),所以,由性质(3)知,对于二次函数,S(1),S(2)共轭.第一轮第二轮共轭方向法-算法无约束直接搜索方法算法分析1.对于二次函数,经过n轮(每轮n次一维搜索)循环后,第n轮中的n个搜索方向相互共轭.所以,第n轮能达到最优解.2.对于非二次函数,经过n轮循环后,第n轮中的n个搜索方向对于f(x)的二次局部近似函数的Hesse矩阵只是近似相互共轭,虽然有较高的逼近,但不一定到达极值点.3.算法可能出现n个方向线性相关.例如,当一维搜索中a=0时,X1(2)=X0(2)时S(1)与S(2)线性相关.此时,不能得到最优解.4.对于非二次函数,经过n轮循环后,可以重新选择n个初始搜索方向,以减小前面搜索方向线性相关或退化的影响.无约束直接搜索方法(2)Powell法为了避免出现搜索方向线性相关,Powell提出两种方法.基本思想:无约束直接搜索方法(2)Powell法无约束直接搜索方法(2)Powell法Powell算法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.无约束直接搜索方法Powell法另一形式(保证线性无关)引理:设k=det(S1/|S1|,S2/|S2|,…,Sn/|Sn|),k+1=det(S1/|S1|,S2/|S2|,…,Sm-1/|Sm-1|,Sn+1/|Sn+1|,Sm+1/|Sm+1|,…,Sn/|Sn|),则k+1=k*am/|Xn(k)-X0(k)|,这里Xm(k)=Xm-1(k)+amSm证明:ek,i=Si(k)/|Si(k)|,ek+1,i=ek,i,(i!=m),ek+1,m=ek,n+1ek,n+1=(Xn(k)-X0(k))/rk=(aiek,i)/rk,rk=|Xn(k)-X0(k)|k+1=det(ek,1,ek,2,…,ek,m-1,ek,n+1,ek,m+1,…,ek,n)=k*am/rkPowell法另一形式---算法1.初始化,X0,ei.2.依次一维搜索Xi(k)=Xi-1(k)+ai(k)ei(k):minf(Xi-1(k)+ai(k)ei(k)).3.en+1(k)=(Xn(k)-X0(k))/rk,rk=|Xn(k)-X0(k)|,一维搜索Xn+1(k)=Xn(k)+an+1(k)en+1(k):minf(Xn(k)+an+1(k)en+1(k)).4.as(k)=max{ai(k)},k=det(e1(k),e2(k),,…,en(k)),若kas(k)/rkeps,则ei(k+1)=ei(k),i!=s,es(k+1)=en+1(k),计算k+1=k*as(k)/rk否则ei(k+1)=ei(k),k+1=k.•当k=n时,若Xn+1(n)已满足要求,停止,否则,X0(k+1)=Xn+1(k),转步2.算法分析1.共轭方向法具有二次收敛性,即二次目标函数n步收敛,效率高,但可能退化到局部空间.2.与共轭方向法不同,Powell法在斜方向上是反射取点(第1种),而非一维搜索.另外,斜方向替代前面的搜索方向是有条件的,所替代的方向是有选择的.3.Powell法不再具有二次收敛性(由于所替换的方向S不定),但计算较稳定,一般反映效果不错.无约束直接搜索方法四.共轭方向法及其改进后的Powell法总结坐标轮换法---最直接的搜索策略.单纯形法---每轮搜索计算点比坐标轮换法少.模式搜索法---最常用搜索方法之一.方法比前两方法稳定.Powell法----最好的搜索方法.适用于多变量情况.无约束直接搜索方法