工程优化设计-理论基础

工程优化设计黄正东二0一二年九月内容提要工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统优化数学理论一.优化模型minf(x)s.t.hi(x)=0,i=1,2,…,mgi(x)≤0,i=m+1,…,px=(x1,x2,…,xn)TRn,f,gi,hi:Rn

->R1

二.约束相关概念(1)可行点(FeasiblePoint),x0

满足hi(x0)=0,i=1,2,…,mgi(x0)≤

0,i=m+1,…,p优化数学理论(2)可行域(FeasibleRegion)g1(x)=9x1+4x2-360≤0g2(x)=3x1+10x2-300≤0g3(x)=4x1+5x2-200≤0g4(x)=-x1≤0g5(x)=-x2≤0优化数学理论优化数学理论(2)可行域(FeasibleRegion)F={x|hi(x)=0,i=1,2,…,mgi(x)≤0,i=m+1,…,p}例子:h1(x)=2x1+3x2+x3-6=0g2(x)=-x1≤0g3(x)=-x2≤

0g4(x)=-x3≤

0x2x1x3F=ABCABCDE优化数学理论(3)有效约束,或取作用约束(ActiveConstraint)可行域边界点所在约束为该点的有效约束，其他约束为不取作用约束（Inactiveconstraint

）。

X(1):g1(x)≤0X(2):g1(x)≤0,g2(x)≤0X(3):无优化数学理论(3)有效约束,或取作用约束(ActiveConstraint)

h1(x)=2x1+3x2+x3-6=0g2(x)=-x1≤0g3(x)=-x2≤

0,g4(x)=-x3≤

0x2x1x3F=ABCABCDE对于约束gi(x)≤0,若gi(x0)=0,

则gi是x0的有效约束.

如g3是D的有效约束.对于约束gi(x)≤0,若gi(x0)<0,

则gi是x0的无效约束,或不取作用约束.(Inactiveconstraint)

如g2是D的无效约束.

g2,

g3,

g4是E的无效约束.优化数学理论(3)有效约束,或取作用约束(ActiveConstraint)x2x1x3F=ABCABCDEx0的有效约束集合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=0g2(x)=-x1≤0g3(x)=-x2≤

0,g4(x)=-x3≤

0优化数学理论三.凸集凸集定义:集合DRn称为凸的,如果对于任意x,yD有x+(1-)yD,01优化数学理论三.凸集凸集分离定理:设DRn为非空闭凸集,yRn,yD,

则存在非零向量aRn

和实数,使得

aTxaTy,xD即存在超平面H={xRn

|aTx=}严格分离点y与凸集D.yxaax0x1

aT(x1-x0)=0->aTx1=aTx0=

aT(y-x0)>0->aTy>aTx0=

aT(x-x0)0->aTxaTx0=优化数学理论四.Farkas引理(线性不等式定理)设ARmxn,bRn,则下述两组方程中仅有一组有解:

(1)Ax0,bTx>0(2)ATy=b,y0这里xRn,yRm,aiTx

0,ai与x的夹角90oATy=(a1,a2,…,am)y=y1a1+y2a2+…+ymam=bb是a1,a2,…,am的正线性组合揭示了m个向量与另一向量的线性组合,与它们定义的半空间交集的联系.aiTx

0,ai与x的夹角90o优化数学理论ATy=(a1,a2,…,am)y=y1a1+y2a2+…+ymam=bb是a1,a2,…,am的正线性组合b属于D0情况1:a2a2Tx0a1Tx0a1b=y1a1+y2a2,y1>0,y2>0,(2)有解

bTx>0D2D1D1D2=,所以(1)无解.D1={x|a1Tx0,a2Tx0}D2={x|bTx>0}D0aiTx

0,ai与x的夹角90o优化数学理论ATy=(a1,a2,…,am)y=y1a1+y2a2+…+ymam=bb是a1,a2,…,am的正线性组合情况2:a2a2Tx0a1Tx0a1bbTx>0D1D0不包含b,所以ATyb(2)无解.D1D2,(1)有解D1={x|a1Tx0,a2Tx0}D2={x|bTx>0}D2D0a1a4a3a2aiTx<0,所有ai都在以x为法向的平面的反侧优化数学理论ATy=(a1,a2,…,am)y=y1a1+y2a2+…+ymam=0存在三角形aiajak包含原点表明ai在大于等于180o的扇区内.Gordan择一定理:设ARmxn,则或者存在xRn,使Ax<0,或者存在yRm,使ATy=0,y0,y0(分量不全为零)且两者不能同时成立.xa1a4a3a2b=0优化数学理论函数等高线Stopherelasttime优化数学理论优化数学理论几何方法找最优点优化数学理论几何方法找最优点解在D的内点、边界、顶点处，求解难度不一样！优化数学理论函数梯度f(x(2))f(x(1))优化数学理论函数Hessian矩阵例子优化数学理论二次函数与正定矩阵正定条件负定条件XXff优化数学理论梯度向约束面或多约束面的交线上的投影g1g2dfb设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=G[GTG]-1GTf优化数学理论五.凸函数凸函数定义:f(x)的定义域DRn是凸的,且对于任意x,yD有

f(x+(1-)y)f(x)+(1-)f(y),01则称f(x)为凸函数.若f(x+(1-)y)<f(x)+(1-)f(y),0<<1则称f(x)为严格凸函数.f(x)xxyf(x+(1-)y)

f(x)+(1-)f(y)优化数学理论凸规划(ConvexProgramming)优化问题称为凸规划问题,如果可行域是凸集合,目标函数是凸函数.定理:设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的二阶连续可微,且存在常数m>0,使

uT2f(x)um|u|2,x

D,uRn则水平集L(x0)={xD|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)]Ts<0,则s是下降方向.f(x)s优化数学理论六.一般最优性必要条件设x0

F为一可行点,F为可行域,s

Rn,若sk,k,k=1,2,…,使 x0+kskF,k,且k->0,sk->s,则称s是在x0处的一个可行方向.x0处的所有可行方向记为F(x0).(1).可行方向定义一般最优性必要条件定理:

若x*是优化问题的局部最优解,则F(x*)D(x*)=.Fss极限下的可行方向一般可行方向skFDUsablefeasibledirection优化数学理论七.一阶最优性必要条件(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).sh(x)=0g(x)g(x)≤

0FF七.一阶最优性必要条件(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).sg1(x)≤0g2(x)≤0Fg1(x)sT

g1(x0)≤0sT

g2(x0)≤0g2(x)s属于L(x0),但不属于F(x0)LICQ:LinearIndependentConstraintQualification优化数学理论七.一阶最优性必要条件(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,

i∈A(x*)和i=0,i∈I-A(x*),I={m+1,…,p}hi(x)=0hi(x)fi(x)FFhi(x)=0hi(x)fi(x)优化数学理论七.一阶最优性必要条件当iI-A(x*)时,gi(x*)>0,所以,有i=0.

当iA(x*)时,gi(x*)=0,且i

0.

从一式知,-f

是g的正向组合.g1(x)=0g1(x)fi(x)Fg2(x)=0g2(x)解释:(2)当全为不等式约束时,只有第一、三项,约束中

i

0,

i∈A(x*)和i=0,i∈I-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*)]Ts<0

L(x*):sT

hi(x*)=0,i=1,2,…,m

sT

gi(x*)≤0,iA(x0),有效不等式约束集合

改写为As0,-[f(x*)]Ts>0A=(-h1(x*)…-hm(x*)

h1(x*)…hm(x*)gi(x*),iA(x0))由Farkas引理知,As0,-[f(x*)]Ts>0无解等价于:

ATy=-f(x*),y0,有解.即: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*,*)s0对一切满足sThi(x*)=0,i=1,2,…,m,sTgi(x*)=0,iA(x*)的方向s均成立.这里L(x,)=f(x)-ihi(x)+igi(x)

解释:对指向F内部

的方向s一般不成立.FssFssf(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=1>0x*h(x)=0f(x)=y现对较简单的问题minf(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’+hyyy’2+hyy”≡0y”=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