工程优化设计理论基础.ppt

工程优化设计,黄正东二0一二年九月,内容提要,工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统,优化数学理论,一.优化模型,min f(x)s.t.hi(x)=0,i=1,2,m gi(x)0,i=m+1,p x=(x1,x2,xn)TRn,f,gi,hi:Rn-R1,二.约束相关概念,(1)可行点(Feasible Point),x0 满足,hi(x0)=0,i=1,2,mgi(x0)0,i=m+1,p,优化数学理论,(2)可行域(Feasible Region),g1(x)=9x1+4x2-3600g2(x)=3x1+10 x2-300 0g3(x)=4x1+5x2-200 0g4(x)=-x1 0g5(x)=-x2 0,优化数学理论,优化数学理论,(2)可行域(Feasible Region),F=x|hi(x)=0,i=1,2,m gi(x)0,i=m+1,p,例子:h1(x)=2x1+3x2+x3-6=0 g2(x)=-x10 g3(x)=-x2 0 g4(x)=-x3 0,x2,x1,x3,F=ABC,A,B,C,D,E,优化数学理论,(3)有效约束,或取作用约束(Active Constraint),可行域边界点所在约束为该点的有效约束，其他约束为不取作用约束（Inactive constraint）。,X(1):g1(x)0X(2):g1(x)0,g2(x)0X(3):无,优化数学理论,(3)有效约束,或取作用约束(Active Constraint),h1(x)=2x1+3x2+x3-6=0 g2(x)=-x10 g3(x)=-x2 0,g4(x)=-x3 0,x2,x1,x3,F=ABC,A,B,C,D,E,对于约束gi(x)0,若gi(x0)=0,则gi是x0的有效约束.如g3是D的有效约束.,对于约束gi(x)0,若gi(x0)0,则gi是x0的无效约束,或不取作用约束.(Inactive constraint)如g2是D的无效约束.g2,g3,g4是E的无效约束.,优化数学理论,(3)有效约束,或取作用约束(Active Constraint),x2,x1,x3,F=ABC,A,B,C,D,E,x0的有效约束集合A(x0)=i|gi(x0)=0,i=m+1,p A(A)=2,4,A(D)=3,A(E)=,h1(x)=2x1+3x2+x3-6=0 g2(x)=-x10 g3(x)=-x2 0,g4(x)=-x3 0,优化数学理论,三.凸集,凸集定义:集合DRn称为凸的,如果对于任意x,yD有 x+(1-)y D,0 1,优化数学理论,三.凸集,凸集分离定理:设DRn为非空闭凸集,yRn,yD,则存在非零向量a Rn 和实数,使得 aTx aTy,x D即存在超平面H=x Rn|aTx=严格分离点y与凸集D.,aT(x1-x0)=0-aTx1=aTx0=,aT(y-x0)0-aTy aTx0=,aT(x-x0)0-aTx aTx0=,优化数学理论,四.Farkas引理(线性不等式定理),设A Rmxn,bRn,则下述两组方程中仅有一组有解:(1)Ax 0,bTx0(2)ATy=b,y0这里xRn,yRm,aiTx 0,ai与x的夹角90o,ATy=(a1,a2,am)y=y1a1+y2a2+ymam=b,b是a1,a2,am的正线性组合,揭示了m个向量与另一向量的线性组合,与它们定义的半空间交集的联系.,优化数学理论,情况1:,a2,a2Tx 0,a1Tx 0,a1,b=y1a1+y2a2,y10,y20,(2)有解,bTx0,D2,D1,D1D2=,所以(1)无解.D1=x|a1Tx 0,a2Tx 0D2=x|bTx0,D0,优化数学理论,情况2:,a2,a2Tx 0,a1Tx 0,a1,b,bTx0,D1,D0不包含b,所以 ATyb(2)无解.D1D2,(1)有解D1=x|a1Tx 0,a2Tx 0D2=x|bTx0,D2,D0,优化数学理论,ATy=(a1,a2,am)y=y1a1+y2a2+ymam=0,存在三角形aiajak包含原点表明ai在大于等于180o的扇区内.,Gordan择一定理:,设A Rmxn,则或者存在x Rn,使Ax 0,或者存在y Rm,使ATy=0,y0,y 0(分量不全为零)且两者不能同时成立.,b=0,优化数学理论,函数等高线,Stop here last time,优化数学理论,优化数学理论,几何方法找最优点,优化数学理论,几何方法找最优点,解在D的内点、边界、顶点处，求解难度不一样！,优化数学理论,函数梯度,f(x(2),f(x(1),优化数学理论,函数Hessian矩阵,例子,优化数学理论,二次函数与正定矩阵,正定条件,负定条件,X,X,f,f,优化数学理论,梯度向约束面或多约束面的交线上的投影,设b=f-d=x g1+y g2,则g1Tb=g1Tf=x g1Tg1+y g1Tg2g2Tb=g2Tf=x g2Tg1+y g2Tg2(x,y)T=GTG-1GTfb=G(x,y)T=GGTG-1GTf,优化数学理论,五.凸函数,凸函数定义:f(x)的定义域DRn是凸的,且对于任意x,yD有 f(x+(1-)y)f(x)+(1-)f(y),0 1则称f(x)为凸函数.若 f(x+(1-)y)f(x)+(1-)f(y),0 1则称f(x)为严格凸函数.,优化数学理论,凸规划(Convex Programming),优化问题称为凸规划问题,如果可行域是凸集合,目标函数是凸函数.,定理:设x*是凸规划的一个局部最优解,则x*也是全局最优解.,定理:设f(x)是凸集合D的二阶连续可微,则(1)f(x)是凸函数的充分必要条件是2f(x)在D上半正定.(2)如果f(x)的2f(x)正定,则f(x)是严格凸函数;反之,f(x)是严格凸函数,2f(x)半正定.,定理:设f(x)是凸集D的二阶连续可微,且存在常数m0,使 uT2f(x)u m|u|2,x D,u Rn则水平集L(x0)=x D|f(x)f(x0)是有界闭凸集合.,优化数学理论,六.一般最优性必要条件,f(x)是定义域DRn上的连续函数,对于方向s,如果0,使 f(x0+s)f(x0),0 则称s是f(x)在x0处的下降方向.x0处的所有下降方向记为D(x0).,(1).下降方向定义,定理:如果f(x)可微,且f(x)Ts0,则s是下降方向.,f(x),s,优化数学理论,六.一般最优性必要条件,设x0 F为一可行点,F为可行域,s Rn,若sk,k,k=1,2,使x0+ksk F,k,且k-0,sk-s,则称s是在x0处的一个可行方向.x0处的所有可行方向记为F(x0).,(1).可行方向定义,一般最优性必要条件定理:若x*是优化问题的局部最优解,则F(x*)D(x*)=.,F,s,s,极限下的可行方向,一般可行方向,sk,F,D,Usable feasible direction,优化数学理论,七.一阶最优性必要条件,(1).线性化可行方向定义,h(x),s,设x0 F,F为可行域,s Rn,且 sT hi(x0)=0,i=1,2,m sT gi(x0)0,iA(x0),有效不等式约束集合则称s是在x0处的线性化可行方向.x0处的所有线性化可行方向记为L(x0).,s,h(x)=0,g(x),g(x)0,F,F,七.一阶最优性必要条件,(2)约束线性化定理,若所有约束hi(x)和gi(x)在x0 F处连续可微,则(1)F(x0)L(x0)(2)如果或者所有hi(x),i=1,2,m,gi(x),iA(x0)是线性函数 或者约束梯度之间（包括 hi(x)和gi(x)）线性无关,则F(x0)=L(x0)成立.,解释:(1)说明L(x0)比实际可行方向定义松.(2)一些极端情况下,F(x0)L(x0).,s,g1(x)0,g2(x)0,F,g1(x),sT g1(x0)0,sT g2(x0)0,g2(x),s属于L(x0),但不属于F(x0),LICQ:Linear Independent Constraint Qualification,优化数学理论,七.一阶最优性必要条件,(2).一阶最优性必要条件定理(Kuhn-Tucker条件),设hi(x)和gi(x)一阶连续,如果或者所有hi(x),i=1,2,m,gi(x),iA(x*)是线性函数,或者约束梯度之间（包括hi(x)和gi(x)）线性无关,则存在=(1,2,p),使,解释:(1)当全为等式约束时,只有第一、二项,可正可负.(2)当全为不等式约束时,只有第一、三项,约束中 i 0,iA(x*)和i=0,iI-A(x*),I=m+1,p,优化数学理论,七.一阶最优性必要条件,当i I-A(x*)时,gi(x*)0,所以,有i=0.当i A(x*)时,gi(x*)=0,且i 0.从一式知,-f 是g的正向组合.,g1(x)=0,g1(x),fi(x),F,g2(x)=0,g2(x),解释:(2)当全为不等式约束时,只有第一、三项,约束中 i 0,iA(x*)和i=0,iI-A(x*),I=m+1,p,-fi(x),此项等价于求和条件只考虑取作用约束！,优化数学理论,七.一阶最优性必要条件,优化数学理论,七.一阶最优性必要条件,X*是最优解吗?如果是,为什么必要条件不成立?,注意线性化要求的检查!,优化数学理论,七.一阶最优性必要条件,证明:由约束线性化定理知,F(x*)=L(x*)一般最优性条件是F(x*)D(x*)=,即L(x*)D(x*)=D(x*):f(x*)Ts0A=(-h1(x*)-hm(x*)h1(x*)hm(x*)gi(x*),iA(x0)由Farkas引理知,As0,-f(x*)Ts0 无解等价于:ATy=-f(x*),y 0,有解.即:,I(正负不限),i 0,优化数学理论,八.一阶最优性充分条件,定理,若优化问题是凸规划问题,且f(x),hi(x),gi(x)连续可微,当K-T条件满足时,x*是全局最优解.,优化数学理论,九.二阶最优性必要条件,定理,设x*是最优解,且f(x),ci(x)二阶连续可微,所有hi(x),i=1,2,m,gi(x),iA(x*)或者是线性函数,或者梯度hi(x)、gi(x)线性无关,从而存在使K-T条件成立,则sT2xxL(x*,*)s 0对一切满足sThi(x*)=0,i=1,2,m,sTgi(x*)=0,iA(x*)的方向s均成立.这里L(x,)=f(x)-ihi(x)+igi(x),解释:对指向F内部 的方向s一般不成立.,F,s,s,F,s,s,f(x),f(x),对双可行方向s,优化数学理论,十.二阶最优性充分条件,定理,设f(x),hi(x)二阶连续可微,所有hi(x),i=1,2,m,gi(x),iA(x*)或者是线性函数,或者梯度hi(x*)、gi(x*)线性无关,若:(1)存在使K-T条件成立;(2)sT2xxL(x*,*)s 0,对一切满足sThi(x*)=0,i=1,2,m,sTgi(x*)=0,iA(x*)的方向s均成立.则x*是严格局部最优解.,解释:（1）通常一阶条件(K-T)保证x*是平稳点,即极点、拐点或鞍点。通过二阶条件才能保证x*是极点。（2）排除拐点或鞍点的方法是考察两个相反方向上f(x)的凸性，所以，只有在边界切方向和F内点才能有两个相反可行方向。（3）对于x*是F内点的情况,问题转化为无约束，2xxL=2f,二阶条件是2f 正定，即sT2f(x*)s 0,对所有s.,为什么是sT2xxL(x*,*)s 0 而不是sT2xxf(x*)s 0?,右图例子:f(x)=y,h(x)=x2+y2-1,*=-1/2,x*=(0,-1),s=(0,1)sT2xxfs=0,sT2xxLs=10,现对较简单的问题min f(x,y),s.t.h(x,y)=0证明以上结论:H(x)=h(x,y(x)0H(x)=hx+hyy 0 y=-hx/hyH”(x)=hxx+hxyy+(hxy+hyyy)y+hyy”=hxx+2hxyy+hyyy2+hyy”0 y”=2hxyhx/hy2-hxx/hy-hyyhx2/hy3F(x)=f(x,y(x)=0,F(x)=fx+fyy=(1,y)f=(1,-hx/hy)f=(hy,-hx)f/hy=0所以，存在使 f-h=0 一阶条件证毕F”(x)=fxx+2fxyy+fyyy2+fyy”=fxx-2hxfxy/hy+hx2fyy/hy2+fy2hxyhx/hy2-hxx/hy-hyyhx2/hy3=(1/hy2)hy2fxx-2hxhyfxy+hx2fyy(fy/hy3)hxxhy2-2hxhyhxy+hyyhx2=二阶条件证毕,如何使用最优性条件?,K-T条件将原问题 min f(x),s.t.h(x)=0 转化为 min L(x),s.t.h(x)=0,这里 L(x)=f(x)-*h(x),假设*已知.两问题有同样的解,这样处理的优点在于:最优解满足xL=0、2xxL正定（在流形h(x)上）,与无约束问题的最优性条件形式上相似.而xf=0、2xxf正定（在流形h(x)上），不能成为解的条件。不足之处：（1）由于*事实上不知道，直接优化L(x,*)不可能。（2）即使*知道，优化L(x,*)时还是要考虑h约束。一般使用方法：（1）由方程xL=xf-xh=0和h(x)=0,求解x*和*。（2）用2xxL在h(x)=0上的正定性，确定x*是否是最优解。,优化数学理论,总结：,1。可行区域F，可行方向F(x),下降方向D(x)，有效约束A(x)，线性下降方向L(x)。2。凸集合与凸函数。3。Farkas引理与Gordan定理。4。一般最优性条件5。一阶最优性条件（K-T条件）6。二阶最优性条件（Hesse矩阵正定或半正定）,