《工程优化设计-理论基础》由会员分享，可在线阅读，更多相关《工程优化设计-理论基础（49页珍藏版）》请在金锄头文库上搜索。
1、工程优化设计,黄正东二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) 可行域(Feas
2、ible Region),g1(x)=9x1+4x2-3600g2(x)=3x1+10x2-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),
3、可行域边界点所在约束为该点的有效约束，其他约束为不取作用约束（ 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) aTx1= aTx0=
4、,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,
5、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
6、 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 g1
7、Tg2g2Tb= 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 0,使 uT2f(x)u m |u|2, x D, u Rn则水平集L(x0)=x D | f(x) f(x0)是有界闭凸集合.,优化数学理论,六. 一般最优性必要条件,f(x)是定义域DRn上的连续函数,对于方向s, 如果0,
8、 使 f(x0+s) f(x0), 0 则称s是f(x)在x0处的下降方向. x0处的所有下降方向记为D(x0).,(1).下降方向定义,定理: 如果f(x)可微, 且f(x)Ts0, 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 R
9、n, 且 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)比实
10、际可行方向定义松. (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)）线性无关, 则存
11、在=(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,
