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

《工程优化设计理论基础.ppt》由会员分享，可在线阅读，更多相关《工程优化设计理论基础.ppt（49页珍藏版）》请在第壹文秘上搜索。

1、工程优化设计内容提要 工程优化问题建模工程优化问题建模 优化数学理论优化数学理论 一维搜索方法一维搜索方法 无约束问题直接搜索方法无约束问题直接搜索方法 无约束问题间接接搜索方法无约束问题间接接搜索方法 约束问题直接搜索方法约束问题直接搜索方法 线性规划与二次规划问题求解线性规划与二次规划问题求解 约束问题间接搜索方法约束问题间接搜索方法 启发式算法启发式算法 优化软件系统优化软件系统优化数学理论一一.优化模型优化模型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 二二.约束相关概念约束相关概念

2、(1)(1)可行点可行点(Feasible Point),Feasible Point),x0 满足满足hi(x0)=0,i=1,2,mgi(x0)0,i=m+1,p优化数学理论(2)(2)可行域可行域(Feasible Region)(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)(2)可行域可行域(Feasible Region)(Feasible Region)F=x|hi(x)=0,i=1,2,m gi(x)0,

3、i=m+1,p 例子例子:h1(x)=2x1+3x2+x3-6=0 g2(x)=-x10 g3(x)=-x2 0 g4(x)=-x3 0 x2x1x3F=ABCABCDE优化数学理论(3)(3)有效约束有效约束,或取作用约束或取作用约束(Active Constraint)Active Constraint)可行域边界点所在约束为该点的有效约束可行域边界点所在约束为该点的有效约束，其他约束为不取作用约束（Inactive constraint）。X(1):g1(x)0X(2):g1(x)0,g2(x)0X(3):无优化数学理论(3)(3)有效约束有效约束,或取作用约束或取作用约束(Active

4、 Constraint)Active Constraint)h1(x)=2x1+3x2+x3-6=0 g2(x)=-x10 g3(x)=-x2 0,g4(x)=-x3 0 x2x1x3F=ABCABCDE对于约束对于约束gi(x)0,若若gi(x0)=0,则则gi是是x0的有效约束的有效约束.如如g3是是D的有效约束的有效约束.对于约束对于约束gi(x)0,若若gi(x0)aTx1=aTx0=aT(y-x0)0-aTy aTx0=aT(x-x0)0-aTx aTx0=优化数学理论四四.FarkasFarkas引理引理(线性不等式定理线性不等式定理)设设A Rmxn,b Rn,则下述两组方程中仅

5、则下述两组方程中仅有一组有解有一组有解:(1)Ax 0,bTx0(2)ATy=b,y 0这里这里x Rn,y Rm,02121xaxaxaxaaaAxTmTTTmTTa ai iT Tx x 0,0,a ai i与与x x的的夹角夹角 9090o oATy=(a1,a2,am)y=y1a1+y2a2+ymam=bb b是是a a1 1,a,a2 2,a,am m的正线性组合的正线性组合揭示了揭示了m m个向量与个向量与另一向量的线性组另一向量的线性组合合,与它们定义的半与它们定义的半空间交集的联系空间交集的联系.02121xaxaxaxaaaAxTmTTTmTTa ai iT Tx x 0,0

6、,a ai i与与x x的的夹角夹角 9090o o优化数学理论ATy=(a1,a2,am)y=y1a1+y2a2+ymam=bb b是是a1,a2,am的正线性组合的正线性组合 b属于属于D0情况情况1:1:a2a2Tx 0a1Tx 0a1b=y1a1+y2a2,y10,y20,(2)有解 bTx0D2D1D1D2=,所以(1)无解.D1=x|a1Tx 0,a2Tx 0D2=x|bTx0D002121xaxaxaxaaaAxTmTTTmTTa ai iT Tx x 0,0,a ai i与与x x的的夹角夹角 9090o o优化数学理论ATy=(a1,a2,am)y=y1a1+y2a2+yma

7、m=bb b是是a1,a2,am的正线性组合的正线性组合情况情况2:2:a2a2Tx 0a1Tx 0a1bbTx0D1D0不包含b,所以 ATyb (2)无解.D1D2 ,(1)有解D1=x|a1Tx 0,a2Tx 0D2=x|bTx0D2D0a1a4a3a202121xaxaxaxaaaAxTmTTTmTTa ai iT Tx x0,0,所有所有a ai i都在以都在以x x为法向的为法向的平面的反侧平面的反侧优化数学理论ATy=(a1,a2,am)y=y1a1+y2a2+ymam=0存在三角形存在三角形a ai ia aj ja ak k包含原点包含原点表明表明a ai i在大于等于在大于

8、等于180180o o的扇区内的扇区内.GordanGordan择一定理择一定理:设设A Rmxn,则则或者存在或者存在x Rn,使使Ax 0,或者存在或者存在y Rm,使使ATy=0,y 0,y 0(分量不全为零分量不全为零)且两者不能同时成立且两者不能同时成立.xa1a4a3a2b=0优化数学理论函数等高线函数等高线Stop here last time优化数学理论优化数学理论几何方法找最优点几何方法找最优点优化数学理论几何方法找最优点几何方法找最优点解在解在D D的内点、边界、顶点处，求解难度不一样！的内点、边界、顶点处，求解难度不一样！优化数学理论函数梯度函数梯度 f(x(2)f(x(

9、1)优化数学理论函数函数HessianHessian矩阵矩阵例子例子优化数学理论二次函数与二次函数与正定正定矩阵矩阵正定条件正定条件负定条件负定条件XXff优化数学理论梯度向约束面或多约束面的交线上的梯度向约束面或多约束面的交线上的投影投影 g1 g2d fb设设b b=f-d=x g1+y g2,则则 g1Tb=g1T f=x g1T g1+y g1T g2 g2Tb=g2T f=x g2T g1+y g2T g2(x,y)T=GTG-1GT fb=G(x,y)T=GGTG-1GT f优化数学理论五五.凸函数凸函数凸函数定义凸函数定义:f(x)的定义域的定义域D Rn是凸的是凸的,且对于任意

10、且对于任意x,y D有有 f(x+(1-)y)f(x)+(1-)f(y),0 1则称则称f(x)为凸函数为凸函数.若若 f(x+(1-)y)f(x)+(1-)f(y),0 0,m0,使使 u uT T 2 2f(x)u f(x)u m|u|2,x D,u Rn则水平集则水平集L(x0)=x D|f(x)f(x0)是有界闭凸集合是有界闭凸集合.优化数学理论六六.一般最优性必要条件一般最优性必要条件f(x)是定义域是定义域D Rn上的连续函数上的连续函数,对于方向对于方向s,如果如果0,使使 f(x0+s)f(x0),0 则称则称s是是f(x)在在x0处的下降方向处的下降方向.x0处的所有下降方向

11、记为处的所有下降方向记为D(x0).(1).(1).下降方向定义下降方向定义定理定理:如果如果f(x)可微可微,且且 f(x)Ts0,sk-s,则称则称s是在是在x0处的一个可行方向处的一个可行方向.x0处的所有可行方向记为处的所有可行方向记为F(x0).(1).(1).可行方向定义可行方向定义一般最优性必要条件一般最优性必要条件定理定理:若若x*是优化问题的局部最优解是优化问题的局部最优解,则则F(x*)D(x*)=.Fss极限下的可行方向极限下的可行方向一般可行方向一般可行方向skFDUsable feasible direction优化数学理论七七.一阶最优性必要条件一阶最优性必要条件(

12、1).(1).线性化可行方向定义线性化可行方向定义 h(x)s设设x0 F,F为可行域为可行域,s Rn,且且 sT hi(x0)=0,i=1,2,m sT gi(x0)0,i A(x0),有效不等式约束集合有效不等式约束集合则称则称s是在是在x0处的线性化可行方向处的线性化可行方向.x0处的所有线性化可行方向记为处的所有线性化可行方向记为L(x0).sh(x)=0 g(x)g(x)0FF七七.一阶最优性必要条件一阶最优性必要条件(2)(2)约束线性化定理约束线性化定理若所有约束若所有约束hi(x)和和gi(x)在在x0 F处连续可微处连续可微,则则 (1)F(x0)L(x0)(2)如果或者所

13、有如果或者所有hi(x),i=1,2,m,gi(x),i A(x0)是线性函数是线性函数 或者约束梯度之间（包括或者约束梯度之间（包括 hi(x)和和 gi(x)）线性无关线性无关,则则F(x0)=L(x0)成立成立.解释解释:(1):(1)说明说明L(xL(x0 0)比实际可行方向定义松比实际可行方向定义松.(2)(2)一些极端情况下一些极端情况下,F(x0)L(x0).sg1(x)0g2(x)0F g1(x)sT g1(x0)0sT g2(x0)0 g2(x)s属于属于L(x0),但不属于但不属于F(x0)LICQ:Linear Independent Constraint Qualifi

14、cation优化数学理论七七.一阶最优性必要条件一阶最优性必要条件(2).(2).一阶最优性必要条件定理一阶最优性必要条件定理(Kuhn-TuckerKuhn-Tucker条件条件)设设hi(x)和和gi(x)一阶连续一阶连续,如果或者所有如果或者所有hi(x),i=1,2,m,gi(x),i A(x*)是线性函数是线性函数,或者约束梯度之间或者约束梯度之间（包括包括 hi(x)和和 gi(x)）线性无关线性无关,则存在则存在=(1,2,p),使使pmixgpmixgxhxfiiipmiiimiii,.,1,0*)(,.,1,00*)(*)(*)(11解释解释:(1):(1)当全为等式约束时当

15、全为等式约束时,只有第一、二项只有第一、二项,可正可负可正可负.(2)(2)当全为不等式约束时当全为不等式约束时,只有第一、三项只有第一、三项,约束中约束中 i 0,iA(x*)和和 i=0,iI-A(x*),I=m+1,phi(x)=0 hi(x)fi(x)FFhi(x)=0 hi(x)fi(x)优化数学理论七七.一阶最优性必要条件一阶最优性必要条件当当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)Fg2(x)=0 g2(x)pm

16、ixgpmixgxhxfiiipmiiimiii,.,1,0*)(,.,1,00*)(*)(*)(11解释解释:(2)(2)当全为不等式约束时当全为不等式约束时,只有第一、三项只有第一、三项,约束中约束中 i 0,iA(x*)和和 i=0,iI-A(x*),I=m+1,p-fi(x)此项等价于求和条件此项等价于求和条件只考虑取作用约束！只考虑取作用约束！优化数学理论七七.一阶最优性必要条件一阶最优性必要条件优化数学理论七七.一阶最优性必要条件一阶最优性必要条件X X*是最优解吗是最优解吗?如果是如果是,为什么为什么必要条件不成立必要条件不成立?注意线性化要求的检查注意线性化要求的检查!优化数学理论七七.一阶最优性必要条件一阶最优性必要条件证明证明:由约束线性化定理知由约束线性化定理知,F(xF(x*)=L(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*),i A(x0)由由Farkas引理知引理知,As 0,-f(x*)Ts0 无解等价于无