自動化學(xué)約束優(yōu)化約束非線minfs.t.gi(x)hj(x)

j1,...,不等式約束優(yōu)化問題線性約束優(yōu)化問題，…定義1設(shè)， ,則稱是處的一個可行方向。在處的所有可行方向的集合記為 2在定理1:設(shè)是 中非空集合,若是(NLP)問題局部最優(yōu)解，則

在處可微即:局部最優(yōu)解，則處的可行方向一定不是下降方向證明：反證，設(shè)存在向量h0,hF0V，即hF0hVhFf(x)Th00,當(dāng)0,時 f(xhf(xhV20,當(dāng)0,2時，有xh令min1,2,當(dāng)0,f(xhf(x)，且xhD即xh比x更優(yōu)，與x是局部最優(yōu) 最優(yōu)點(diǎn)可能出現(xiàn)的情況在可行域內(nèi)在約束邊界 約束最優(yōu)解minf(x1,x2) s.tx2

2x22x212x22x21不難看出，可行域是弧AB，最優(yōu)點(diǎn)是B點(diǎn)x*二．不等式約束的一階最優(yōu)性條 ， 表示處全部起作約束的標(biāo)號在討論可行方向時，希望只考慮在處起作用的約束條g1g1(x)x1dx0dddg2(x)例設(shè)g1(x)x2 2x

0,g(x)1x

g(x)x0 ,2T極約 點(diǎn)的 指標(biāo)集(xg2(x)g(x)1g3(x)Ox重新定用替代定理1中的可行方向錐

最優(yōu)性定理2：設(shè)，在可微，在續(xù)，如果是（NLP）問題局部最F0VV0VhV0h0當(dāng)0,xh即只需證gi(xh0i1hV，由V定義iI(x有g(shù)(x)Th0 gi(xgi(x則有g(shù)i(x

h010當(dāng)0,1時，gi(xh)gi(x),iI(x)gi(xh)gi(x)0,iI(x（1）而當(dāng)iI(xgi(x0，已知iI(xgi(x)x處連續(xù)2 0當(dāng)0,2時，gi(xh)0iI(x（2）由（12min1,2,當(dāng)0,時，對igi(xh)0xhDh為可行方向hVV0凸集的進(jìn)一凸 4SRn，若xxS， x1(1)x2

凸5S的凸包：由S中元素所有可能的凸組合構(gòu)它是所有包含集合S的凸集的交，即它是包含集合S的最小凸6KRn，若xK0，有xK則稱K為錐；若錐K還是凸集，則稱之為定義7SRn是非空凸xSx不在S中任何線段的內(nèi)部，則x是凸集S的極點(diǎn)。顯然，多邊形頂點(diǎn)、圓周上的點(diǎn)均為S中的某方向d不能表示為該集合的兩個不同方向的正的線性組dS的極方向。凸集的分十分關(guān)鍵的作用。集合的分離是指對于兩個集合S1S2，存在一個超平面H有pTx那么H一邊的xpTx 9SSRn中兩個非空集合HpTx 1為超平面，如果xS,都有pTx對于1分離集S13SRn是非空yS，則存在唯一的點(diǎn)xS，它y的距離最短。進(jìn)一步，xy距離最短的充要條件(xx)T(xy)0，x凸集的4（凸集的分離定理）設(shè)SRnyRnyS，則存p0和實(shí)數(shù)，使得pTxxS，并且同時滿足pTy即超平pTx嚴(yán)格分離y和閉凸S。證明：由于S是閉凸集yS。故定理3存在唯一的一xS，使(xx)T(xy)0，x p(yx)，則 pT(xx)0， pTxpTx。再 pTx則xS， pTx。pTypTypTxpT(yxx(yx)T(yx) y 2x故 pTy定理證5（Farkas）ARmncRn，Ax cTxATy y也可表示Ax0cTx0有解的充要條件ATycy0例AmnB是ln矩陣cRn應(yīng)用Farkas引理證明下列兩個系統(tǒng)恰有一個有解：1Ax0Bx0cTx0對于某xRn2ATyBTzcy0，對某yRnz然后利Farkas可以把該等式轉(zhuǎn)化為不等式描述：Bx0Bx0,BxA這樣，系統(tǒng)1的不等式系統(tǒng)可以描 為

x0,cTxB 利用Farkas引理，系統(tǒng)1描述的不等式系A(chǔ) ABx0,cTx0有解系統(tǒng)B c,0無解 yzyRmzzRl，即 1 z z 2yATyBTzBT cz0 1z z2zz1z2z是自由變量，無非負(fù)限制，2ATyBTzcy0：Gordan：有解的充要解釋 夾角都為鈍Gordan1 2A 2

使得1,2,3X夾角都為鈍角，則存在非零向yj0,j123使yTyTyT 因?yàn)椴淮鎄，使得1,2,3X夾角都為鈍角，所1y22y331y22y33x13x2 17x 3x 3x 17x

x13x22 217x 3 Ax0無解，其中,A 1 Gordan理，只需證明存ATy0y0有解即可也就是證明

y1

17y30有非零解，且解非負(fù)即可。由13y12

11y3y13y217y331y211y3y13y217y3,3(3y217y3)y211y3y24y3,y15可見，當(dāng)任y30時，均y15y30,y24y30，由Gordan理，命題得證最優(yōu)性的代數(shù)條件(FritzJohn條件定理7： 在可微在連續(xù)，如果是（NLP）問題的局部最優(yōu)解，存在不全為零的非負(fù) ,使:理2,在,,量.得,即由Gordan,數(shù)成 得,知,T題的最優(yōu)minf(x)1

7)22

g(x)10x2x2 g2(x)4x1x2g3(x)x2g1(xxfg1(xxf(x)g2(x在點(diǎn),Tf(x)8,g(x)6,g(x) 設(shè)86104 12 2 此方程有分量不全為的非負(fù)解，如于是在處滿足FJ條件 f(x) g1(x)g2(x)x1

(2x2)2(f(x)0,g(x)2,g(x) 0 設(shè)0210 10 20 此方程有解=（02k任何正于是在處滿足FJ條件 在可微在連續(xù) 證明：由定理7，存在不全iiI0f(x)igi(x)0，而不i(x)=0

i,iI gi(x)iI(x)線性相關(guān)與題

,iI則f(xigi(x)例驗(yàn) 1計算f(xgi

f(x)

2),g(x)

,g(x)

2x

1 2 0 （2）x(1)0g(x(1)0g0 I(x(1))f(x(1))4,g(x(1))1,g(x(1))0

1 K-T條件f(x(1g(x(1g(x 4110 10 21 41

04, 得2 14x(1不是K-T（3）對x(2)1點(diǎn)g(x(20g(x(21 1I(x(2))f(x(2))2,g(x(2))1,g(x(2))2

1 K-T條件f(x(2g(x(2g(x 2112 12 21 212

0,得22

ix(2K-TK-T條件的另一種形K-T條件等價由條件,當(dāng)時而當(dāng)時 例minf(x)x11)2s.tg1(x)x1x22g(x)x 求滿足K-T條件f(x)

1),g(x)

1,g(x)0 f(x)1g1(x)2g2(x)由K-T條件g(x)0, (x) 0, 2(x11)1 112 1(x1x22) 2x2 10,2 由（4）2x2020，由）1

0,由（）(1) 0，由（3）(x20

1,1,

0,

0, x20x2,由

12舍x= 0 0x1K-T 設(shè)域的

線性無關(guān),則存 ,滿罰函數(shù)自動化學(xué)小化方法(SUMT---SequentialUnconstrainedMinimizationTechnique) minf( s.t.g(x) j h(x)j

i1,2,,j構(gòu)成一個新的目標(biāo)函數(shù)，稱為懲罰 (x,r(k),r(k))f(x)r(k)G[g(x)]r(k)H[h( (x,r(k),r(k))f(x)r(k G[g(x)]r(k H[h( 懲罰項(xiàng)必須具有以下極限性質(zhì)mlimr(k)G[g(x)]m

llimr(k)H[h(x)]k

k

(x,r(k),r(k))f(x(k))懲罰函數(shù)

外點(diǎn)子算目標(biāo)函數(shù)—-價格，約束條件---規(guī) 采購代價=商品價格+罰懲罰函數(shù)的導(dǎo)例1考慮單變量問 minf(x) 的圖s.tx1顯然該問題最優(yōu)解是x*不考慮約束條件，最優(yōu)解x0距離x*1較遠(yuǎn)，如何才能使其 近如果保持曲線位于可行域(-,-的最優(yōu)點(diǎn)的橫坐標(biāo)就會逐漸向*1這一過程可用數(shù)學(xué)式

x1(x,r)

r(x x1當(dāng)從逐0漸增大時，函數(shù)就(,)上面k拉起的曲線，當(dāng)充分大時，函數(shù)(xr)的無約束極小點(diǎn)*充分接近x*1.k(x2r(x1)2)2x2r(x1)0x 1r,x1)。例 minF(X)g(X)x1構(gòu)造如下(x,r(k))

(x10)(可行域內(nèi)xr(k)(x

(x10)(可行域外d 1

(k

(x1)

x1

2r(k0.1x0.1

2r(k (k (x,r(k)) (k x (x

(x10)(可行域內(nèi)(x10)(可行域外(x,r(k)) xr(k)(x束邊界越遠(yuǎn)，曲線被抬0.1(x,r(k0.1 xr(k)(xx1

2r(k基本原 去近原約束問題的最優(yōu)解。minf

minf 0,i1~ s.tgi(x)0,i1~2不等式約

等式約外點(diǎn)法懲罰函數(shù)的構(gòu)對于具有不等式約束的優(yōu)化問題minf(x)s.tgi(x) i1外點(diǎn)法的形((x,r)f(x)rmin[0,g jjr0r1r2fj(x,rk)f(x)rk[g(x)]2j

r0r1r2懲罰項(xiàng)的作用:迫使可行域外的函數(shù)f

可行域(x,rk)

f(x)r

[g

可行域j j0012罰因子的(( fP(x合力使得迭代點(diǎn)向() 1）給出，， 若使得（第個約束不滿足，轉(zhuǎn)否則停初始點(diǎn)x(0)的選初始罰因子r(0)遞增系數(shù)c

4)終止條[x*[x*(rk),rk][x*(rk1),rk[x*(rk1),rk1x*(rk)x*(rk1)323krkk

)程序框例4

minf(X)x1 g(X)xx2 g2(X)x1解：首先構(gòu)造懲罰函(X,rk)

x1 xxrk x2)2 14r x2)x12r 12r

x21 x(rk)x2 rx*2f*1---2---3---4---∞000g(Xg(X)xx2 112f(X)x1g2(X)x1 0.125 Xk f(Xk)minf(x)1( 1)3 例5s.t g1(x)1x1g2(x)x2

用外點(diǎn)法(x,r)1(x1)3xrmax0,1xrmax0,

(x1)22rmax0,1x 12rmax0,x 為解上面第一個方程，討論兩種情形 （1）1x0max0,1x00 (x1)20x1，此點(diǎn)不滿足1x0，即不在可行 （2）1x0max0,1x1x0 (x1)22r(1x)0

r2kkx1r2kk

，由于只考慮

1的情r2kkx1r2kk

0（舍去r2kkx1r2kk同理由0得 2 2k即x1(rk)1rk

rk4rk4k

rkrk4kr24 r

r2 rrkrkkk

rkrkkk

1, x2(rk)

2

0, 所以，x*1x* xx(x,k)f()1---10無約束問題min(xrkf(xrk的最優(yōu)解為*k limx* k k證明：因?yàn)閗

無約束問題的xk

kkk(x*,rk) ,rkkk ,rk+1)(x*,rk+1)k f(x*)rkP(x*)f(x* )rkP(x*

k kf(x* )rk1P(x* )f(x*)rk1P(x*

k k 因?yàn)?式(x*,rk) ,rk+1

端用k

rk以得 kk由）x*rk)krkP(x*)rk1P(x* k

)rkP(x* )+rk1P(x*k （rk

rk)(P(x*

)P(x*

0kkP(x* )P(x*kkk 結(jié)合）和（）4式f(x*)f(x* kk由（5）可知(*k

P(x)f(x*)f(x*)rkP(x* k(x*,rk)(x,rkkf(x) 式和（）5

(*kf(x* 所以，極限和(*,rk limf(x*k 存

k (xk,r)=f(xk)rP(xk所以極限存在k(*

rk k 以limP(x*0，再由的P(xk 有P(x*)=P(limx*)=limP(x*k k 這說明x*由）式x,ff(x*)=f(limx*)=limf(x*)fk k 所以*原約束問題的最優(yōu)k外點(diǎn)法的不足：為了讓無約束問題的最優(yōu)解*k約束問題的最優(yōu)解*,滿足允許的誤差精無法預(yù)料k竟要大到什么程度。顯然，太大的 計算機(jī)在數(shù)值計算上 。另外，外點(diǎn)k在迭代過程中*某個充分大的處迭代rk對于某些實(shí)際問題，這樣的近似最優(yōu)解是不能被接內(nèi)點(diǎn)內(nèi)點(diǎn)法將增廣目標(biāo)函數(shù)定義于可行域內(nèi)，序列迭代點(diǎn)在可行域內(nèi)逐步近約束邊界上的最優(yōu)點(diǎn)。內(nèi)點(diǎn)法只能用來求解具有不等式約束的優(yōu)化對于只具有不等式約束的優(yōu)化問題 f(s.t.g(x)

(j 一.懲罰函數(shù)形(x,r)f(x)

mm(k)m

gi(

ixr)fxrk)ln[g im(x,r)f(x)+r(k) mii1[g(i例1minFXg(X)1x先構(gòu)造懲罰函數(shù)min(X,r(k))F(X)r(k xr(k g(X 1d1r(k (1x)2

解得r(kx(r(k))r(k=＝01r(k cr(k

k r=0.01,﹍﹍ x*→二.內(nèi)點(diǎn)法構(gòu)造懲罰函數(shù)應(yīng)遵循原懲罰項(xiàng)min(X,r(k))F(X)r(k g(X當(dāng)x由可行域內(nèi)靠近任一約束邊界時1g(X

三三min(X,r(k))F(X)r(k1g(X由于內(nèi)點(diǎn)法只能在可行域內(nèi)迭代，而最優(yōu)解很可能在可行域內(nèi)靠近邊界處或就在邊界上，此時盡管懲罰函數(shù)的值很大，但罰因子是不斷遞減的正值，經(jīng)多次迭代，接近最優(yōu)解時，懲罰項(xiàng)已是很例2用內(nèi)點(diǎn)法 f(x)x2 1s.t.gx)x1 的最優(yōu)解1解:首先構(gòu)造內(nèi)點(diǎn)懲罰函數(shù)(x,r)x2x2rkln(x rk2x x 2x22聯(lián)立求解

12rkx(r12rk 2x(rk)2考慮約束

g(x)1x11x(r)111 最優(yōu)點(diǎn)迭代

x(r0) x(r1) x(r2) x(rk) 四.算法步在可行域內(nèi)部D0選擇一個初始內(nèi)點(diǎn)選取初始罰因子r(0)與罰因子降低系數(shù)c，并置求minφ(x(K),r(K))解出最優(yōu)點(diǎn)K←K+1，r(K)←cr(K-1)，xK0←xK-1*，并轉(zhuǎn)步驟按終止準(zhǔn)則判別，若滿足轉(zhuǎn)步驟6），否則轉(zhuǎn)步驟輸出最優(yōu)解（X*，F(xiàn)*），停止計算五.收斂條[x*[x*(rk),rk][x*(rk1),rk[x*(rk1),rk1x*(rk)x*(rk1)例3用內(nèi)點(diǎn)法求下列問題的最優(yōu)解：n(X)x1

g(X)x2x0 g2(X)x10解:構(gòu)造懲罰函2(X,rk)F(X)rk j1gj(XXrFXrln(gX jj2或(X,rk)F(X)rk jj1g2(Xj(X,rk)

rkln(x2x2)rkln(x 2rk 1 x2

rkx2 x1

114

18r 18r rkx r01

X0X0 X1

F(X0)1當(dāng)r0.52

X2

F(X)2當(dāng) 0.25

F(

)當(dāng)r30.125當(dāng)rk0

X3Xk

F(X3)F(Xk)六.選取初始內(nèi)點(diǎn)的算法步 （1）x0Rn,0c1k令

g(xk)0,1i

g(xk)0,1i i若 ,則x0D，迭代停止，否則轉(zhuǎn) i xg(x)0,iT 使minV )V(xk

k k其中V(x,k1gi(xk1

g 令k1

k1 (c1kk1轉(zhuǎn)算法流

求內(nèi)點(diǎn)混合罰函minf(x),x s.t.g(x) j h(x)j

i1,2,,jD0

g(x0i1~m若imi

1 i(x,r(k))f(x)r(k)lg[g(x)]i

r(k

[hj( minf(x)lgx1h(x)x2x24 g(x)x11構(gòu)造混合罰函(x,r(k))(lgxx)1(x2x24)2r(k)lg(x r(k 01.553 11.334 3乘子算LgnLagraneLgage乘子的迭代進(jìn),乘子算法是對內(nèi)點(diǎn)法,外點(diǎn)法,混合法的改明,乘子算法優(yōu)于若是無約束極小化問題的最優(yōu)解， 注意到可行 出是不可能的。

求 但當(dāng)非常大時，罰函數(shù)問題Hesse矩陣呈現(xiàn) 外點(diǎn)法2(x,r)(x2

minf(x)s.tx21x2r(x

1)2 (x,r)

2(x1 2x2r(x 2(x,r)

2 k k

22r 子令是子問

p再看Lagrange乘子函數(shù)L(xf(xjhj(x)pj的駐h(x) L(x*,*)f(x*) k為了使x(kk比較上面兩

jx*令------修正Lagrange乘子向量的迭代公然后再進(jìn)行 次迭代， 繼續(xù)迭代，直 ，從而如果不收斂或收斂很慢，可增大罰因子 再進(jìn)行迭代。收斂快慢的一般標(biāo)準(zhǔn)是：，解處的Lagrange，廣LagrangeLagrange而 o ，得到點(diǎn)> ，轉(zhuǎn)否則進(jìn)入 轉(zhuǎn)乘子法求解下列問(x,,M)(2x2xxx2)(1)(xx2)M

(x,M)(2x

xxx2) x2)

x 6xx50,x4x5 x(1)

x(1)

,h(x(1))

(k(x,k）,M)(2x2xxx2)(k) x2)

x

3(k

12

x(k) 0x(k)

x(k)

5(k)20 由(k+1)=(k

Mh(x(k))(k

2(x(k

x(k

2)7(k

3(2)12 17

23

1

) 5(2)20 28 h(xh(x(2)h(x(1)

23**=1.75，此時仍

2

3*12 原問題最優(yōu)解x*

,f(x*)5 5*5 該問題有唯一極小點(diǎn)* 0取為x 0h(x*)9.5107,

Mk1

x* 五．不等式約束的乘子算 出

于入上面了乘子法

2 11

12x2xxx2

max(0,M(xx

1

當(dāng)1M(x1x22

xxx2+1M(xx2)22 1

4xxM(xx2)

x2xM(xx2)

6M x(1)8M

110M518M 當(dāng)

2)0x,,M)=2x

2x2 214x 0,x 1 x(1)

g(x(120,

1 251設(shè),

x(1) 2323修正

(k

max[0,(k

2(x(k)x(k

2)]111

1同理可得() (3) x(3)11最后可得原約束問題的最優(yōu)解 x(3)1

7f(x*)7增廣目標(biāo)函矩陣范數(shù)、條件數(shù)與矩陣?yán)紤]下面的兩個線性方程2x1 6x2 與2x1 6x2 2x 2 x 其解分別為：xx1x 2

xx110x x 向量范XRn,若X的實(shí)值函數(shù)N(X)=‖X‖,滿足條件非負(fù)性:‖X‖0,且‖X‖=0的充要條件為齊次性kX‖=|k|‖X:‖則稱N(X)=‖X‖為Rn上的向量X的范定義：設(shè)X=(x1,x2,…,xn)TRn,則定義x21x2x21x2x2 X2向量的－范數(shù)

max{xi1i向量的1－范數(shù)

X1

xi1x矩陣范定義:設(shè)矩陣ARn×n,若A的實(shí)值函數(shù)N(A)=‖A‖,滿足條件非負(fù)A‖0且‖A‖=0當(dāng)且齊次A‖=||‖A三角不等柯西－施瓦茨不等則稱‖A‖為矩陣A的范數(shù)定義：設(shè)向量XRn,矩陣ARn×n,且給定一種向量范數(shù)‖X‖p,則p p X

pmaxXp

,p1,2,為由向量范數(shù)派生的矩陣算子范數(shù)定理：設(shè)A=(aij)n×n,則對應(yīng)于3種常見的向量范數(shù)，有3種矩陣范nA1max

列和的1

Amax

行和的 2

j

max是ATA的最大特征值，也稱為譜范矩陣范數(shù)的一些 A0,&,A0A②AA, ABA A,B ABA A,B Ax

A

,x條件數(shù) 矩Axbb0A(x*x)bb cond(A) condA

AA定義：稱條件數(shù)很大的矩陣 矩陣， 矩陣對應(yīng)方程組 方程組，反之，則稱A為良態(tài)矩陣常用的條件 (A) cond1(A)cond2(A)

A AAA

(AT (AT ATA代表矩陣ATA的最大特征判斷矩陣是 ，有時并不計算A1，而由以下經(jīng)驗(yàn)判行列式很大或很小（如某些行、列近似相關(guān)元素間相差大數(shù)量級，且無規(guī)主元消去過程中特征值相差大數(shù) A

0.99

b1.990.99

0.

1.97計算cond(A)2精確解 1x精確解 1

9800 9900 = 9900 10000解：A是對稱矩陣，其特征det(IA)

120.cond(A)22

39206>>向自動化學(xué)第一Frank-Wolfe自動化學(xué) 其中 記 一階連續(xù)可微 近原問題，這是一個線性規(guī)劃問設(shè)(2)最有形形1):若，則線劃的時可證為問題的K-T：形1）現(xiàn) 則也 滿足（2）的K-T條件而原問題(1)K-T ，，同時滿足K-T條件故是原問題（1）的K-T點(diǎn)。情形2): ， 因?yàn)?若情形2)出現(xiàn):顯然,當(dāng)然不是線性規(guī)劃問題（2）的最優(yōu)解，由是（2）的最優(yōu)解，必有從而 在處的下降方向?yàn)闉? 設(shè)最佳步長因子 ，用取代，重復(fù)以上計算過程二、算法迭代步 ，

，Stop,；否則轉(zhuǎn)4)進(jìn)行一維搜索，得最優(yōu)步長因子 ，，轉(zhuǎn)2)

若迭代到某步，有則為原問題的K-T點(diǎn)若情形1）總不發(fā)生，則算法產(chǎn)生一有界無窮 ，其任意極限點(diǎn)都是原問題的K-T點(diǎn)。2(x 2(x f(x)2(x14f2(x 2(x

x

第一次迭minTf(x0)xmin20x1x1x2s.tx1x2 x, 用單純形法求出此線性規(guī)劃的最引入松馳變量x3x4

min20x1x1x2x3s.tx1x2x4

001110014820400f0 02101101182400f08x* 0T為該（LP）y08 8 2）Tf(x0)(y0x0) 4061448 60y0x0660 minf(x0(y0x0))minf(66,20 0f(66,26)664226 12(106)12(62)144144d0

x0(y0x0)

6T0880第二次迭代x1代替x0，重復(fù)以上步0 x f(x1)2x1 x 2x

x2 minTf(x1)xx1x2s.tx1x2 001110014800f000Tf(x1)(y1x1)

80064000 y1x10為搜索方向，對原目標(biāo)函數(shù)作一維搜索求其最優(yōu)步長 minf(x1(y1x1))minf(0,80 0d 01d 2

0令x2x1(y1x1) 1第三次迭代

4f(x2)2x18 8

0

x2 求解線性規(guī)minTf(x2)xx1x2s.tx1x2用單純形法求出此線性規(guī)劃的最 0011100148000f00Tf(x2)(y2x2) 000 x*x20即性自動化學(xué)一．線性近似規(guī)劃的

是可行解，將，（3）求解由（2）和（3）

點(diǎn),制 ,,題若滿足可行性,則 轉(zhuǎn)4),否則令,返2),重新解縮小步若,且滿足則點(diǎn)為近似最優(yōu)解,否則,近似規(guī)劃法求解：第一次g(x(1))9.75,g(x(1)) 2x1 2x1g1(x)

2x,g2(x)

2 2x(1g(xg(x) g(x)g(x(1))g(x(1))T(xx(1)g1(x)g1 )(x (1) g(x)9.75

x1

40.25

x xg(x)4.25

x1

9.25

x x步長x

(1)

x1

x2

12x132,1x22.511x15,1.5x2又有約0x15,0x2101x11.5x2minf(x)2x140.256x15x29.756x 1x1把（1）（1）x1x2有上下界，如 ,即x 0,令

x

j

0j

x即可 x

tjx

t

0,x"t

xjx"0j

x"x即可 這里y1x11,y2x21x150y11.5x23.50y2minf(x)2y1y26y15y26y5 到 s.ty1yy用單純形法解（2）式，可得

41 6 31對于g(x(2))1.6626g1 )1.0586 不滿足原非線性規(guī)劃的約束條第二次迭0.5減少步長限制為(2)(1) 返回修正上述近得到新的近似線性規(guī)劃問題minf(x)2x140.256x15x29.756x 2x 2x2用單純形法解（3）x(3)4,f(x(3g(x(3))0,g(x(3)) ) 第一次迭代近似(LP)可行域?yàn)橥辜疉BCDE,最優(yōu)點(diǎn)A(463)第二次迭代:近似(LP)可行域?yàn)橥辜疐GHIJ,最優(yōu)點(diǎn)F(440.256x15x2迭代點(diǎn):x(1)A9.756x15x2f(X)第三

Rosen梯度投自動化學(xué)一、算法若當(dāng)前迭代點(diǎn)位于約束域內(nèi)部，此時負(fù)梯度 二、投影矩陣的基本 是線性空間的子空間，如果和中每個向量的分解式是唯一的，這個和被稱為直投影矩陣：設(shè) 矩陣若 ，則稱為投影矩設(shè) 2為投影矩

3若為投影矩陣 P設(shè)P為投影矩(IP)TIPTIIPIPIPPP2I2PPI3）PxL,Qx (Px)T(Qx)xTPT xTP(I xT(P xT(P 0,L 又xRnxIxPQ)xPxQxpqpLq顯然這種表示是唯一的，若不然xpqp'q',p,p'L,q,q'ppq'q,ppLq'q而LL正交，則pp')T(q'q0即ppq'q,pp')Tpppp'20pp'0ppqqRnLL的直LL投影矩陣特定理： 是任一投影矩陣， 在處的一個下降方證明：欲證hf(xxTf(x)h0Pf(x0PPTPPPTf(x)hTf(x)Pf(x)Tf(x)PTPfPf(x)TPf(x)Pf(x)2考慮問題 ，一階連續(xù)可微作分解，使

，是矩陣的若是的內(nèi)點(diǎn)，

則為投影矩陣證明ATAAT)1A為投影 AT(AAT)1

AAT)1

(AAT

AT(AAT)1

AT(AAT)1AAT(AAT)1A AT(AAT)1AA AT(AAT ATAAT)1A為投影矩 PIATAAT)1 為投影矩 四．算法收斂 的可行解,在處則非零向量為處的可行方證明要性非零向量hx處的可行方向0,使得對(0,xh即A(xh) C(xh) 由（1）A1(xh)A1xA1hb1 b1A

AxAh AxA

b 2 20,A1h由（2）C(xh)dCxChCxd,Ch0ChA1h0Ch0h為可行方向00,A(xhbC(xh)A2xb200,A2(xh(0,),A(xh)又Ch0Cxd0C(xh)CxChCx故0當(dāng)0,A(xhbC(xhxhDh為處的可行方如果同時滿足， 應(yīng)該是處的可行下降方向 令,（1）h0hf(xx處的可行下降方向證明：先證h為可行方 APA[IAT(AAT)1 AAAT(AAT) AhAPf(x)A1h0Ah0ChC C 再由條件hPf(x)0P為投影矩陣知hf(xx處的一個下降方向hPf(xf(xx處的可行下降方向(2h0若滿足u0x為原（NLP）的K-T證明：hPf(x)0，即[IAT(AAT)1A]f(x) f(x)AT(AAT)1Af(x) 令A(yù)AT)1Af(xw，上式可以表示為 f(x)ATw0f(x)

u f(x)( CT)u v v 1f(x)ATuCTv1已知u0上式恰Kuhn-Tucher條件x滿足K-Tx為原（NLP）的K-T（3）當(dāng)若不滿 ，則 中 的行，得到新

，并 替代， ，則

在處的一與（1）類似可以證明?0為可行下降方向）由（1）結(jié)論，只須證明?P?f(x)0即可。?只須證A中有線性相關(guān)的行向量，與A行滿秩 P?f(x)[I?AAT)1A] f(x)(AAT)1Af(x ???AT ?T?

另一方Pf(x)[IAT(AAT)1A]f(x f(x)AT[(AAT)1Af(x f(x)AT 即Pf(x)f(x)?Twu

i其中ww中除去u后得到的1維向i0riA中對應(yīng)ui

的行向 (1)-?T?) i0

r組成i0i 0,說明原A的行向量線0與A是行滿 ???AT)1Af(x w直接由u?構(gòu)成，?為u中直接劃去 行所v v五、算法迭代步選取初始可行點(diǎn)，計算精度，作分 ，使 ,行滿秩,其行秩2） , 3 若則停 為原（NLP）的K-T點(diǎn) 則 中劃 對應(yīng)的行向量，得到新 2）一維搜索，確定步 轉(zhuǎn) kminf(xkhkA(xkh) k必須滿 ks.tC(xkh)k

分析約束條件h為可行方向，由引理， 0而xk為可行點(diǎn)，Cxk 顯然約束條件（2）對任意0自然成立對于約束條件（1）A(xkhbA(xkh hk為可行方向，A1hkAxkb，所以只須0 minf(xkhk故問

A

A

2 而由AxkA bAh

A Axkb

Axk Ah0

2A2hk02max確定滿

Axkminxk

h0,iI(xk i

Ah不滿足

i

A2hk梯度投影算法求解：f(x)4x12x24x10 0 2x 0 第一 1）f(x14x10僅由3 I(x1)3,4A 0,b0,A

1, 2 1 0

5 A1A 0 （約束條件中沒有等式約束2）PIAT(AAT)1 II 0 hPf(x1)00 0 i計算w，判定ui0w(AAT)1Af(x1

0 0T 04 uuu2uiminuimin4,66u2 故在A中劃去對應(yīng)于u26的行向量 ?? 1?1 ?I?AAT 0 1 1 10 00

1 1 ?P?f(x1) 040 求最大可行步長A?

106 2 56

22

min

A 222 10 5 min

10 56 0 2 5 0 min 6 min 1 6

求x2

00

0 0 6 6 x10x26f(xf

)

1令 01,011d 故

1,

0

10

01 1 第一次迭代第二次迭 x20，I(x22,3,f(x2 AA

5 5 ,b , 0 ,b ,

1 , 1 , A1

0 PIAT(AAT)1 0 5T 5 5T 1 0 0 0 0 0

hPf(x2) 060 w(AAT)1Af(x2

5 5T 56

0 0 02 28

5 5 uuu 2 minumin2,2828 5 得??,

28所對應(yīng)的第二5 ?I?AAT 0 15 55

5 26 26

5

70

266

13h2Pf(x)

1

2 14

26 13 24計算

,

,x3

31第二次迭代第三 24

3對 31，f3

)

,I

) AA1 PIAT(AAT)1

526 26

532hPf(x3

1

w32u

26 3132

此時f(xug2x

31

故x3 為原（NLP)的全局最優(yōu) 算法迭代過

Zoutendijk可行方自動化學(xué)一.線性約minf(x)(NLP)s.t.Ax CxAmnCpnbRmCRpx(NLP)xAA1,bb1,Axb,Ax 2 2

I(xiixbi,1i由上一節(jié)梯度投影算法我們知道向量hx處的下降可行方向的條Ah0,Ch0,f()Th 1于是通過解線性minf(x)T(LP)

Chxh顯然，如h滿足下降可行方向條件則對任意0,，向量h也必滿足增加關(guān)于h的約束條件，比如minf(x)T Ah(LP)

Chjh ,j1j

定理(Farkas定理）設(shè)A ,cRn,則Ax0,cTx0有解充要條件是ATyc,y0無 minf 定理x(NLPs.t.Axb的一個可 CxAA1,bb1,Axb,Axb 2 2minf(x)T Ah

(LP)

Chjh 1,j1j

的最優(yōu)解為(LP)的最優(yōu)目標(biāo)函數(shù)值小于h*必為原(NLP)在x處的一個下降可行方向(LP)的最優(yōu)目標(biāo)函數(shù)值h0顯然是(LP)的可行解，故(LP)（1)(LP)0，即最優(yōu)解h*1f(x)Th*0Ah*0,Ch*1h*x1不等式組f(x)Th Ah0,Ch0無解11Ah0Ch0Ch0f(x)Th01ATuCT v)f(x vv2v1，上式說明存在向量uv(u01f(x)ATuCTv1取初始可行x1kxk，作分AA1bb1AxbAxb 2 2

處的線性規(guī)劃問題

minf(xk)T Ah Chj 1,j1j得最優(yōu)解k

f(xk)Tk

0則停xkK-T，否則I(xk)xk處對應(yīng)于不等式約束的主動約束標(biāo)號集minixk

h0,iI(xk

Ah不滿足max

2 A2hk求, f(xkh)f(xkh) 0 xk1

khkkk112.1.1用Zoutendijk可行方向法解下minf(x)x2x22x 2x1x21 xx2 x

0)T第一1）f(x(1)) 4)T，對x(1) 僅有34）約束起作用I(x1)3,4x(1)處，作分解A 0,b0,A

1,b 1 0

2 x(1處求可行下降方向h(1，minF(h)f(x(1))T(LP)

A1h

1,jminF(h)2h11 h1即(LP) h2 1h1 1h2用單純形法解得：h(1) 2）確定Ah(1)

111

2bAx(1)min 2 A 21 10 min 1 11 1

2 10 0 0min

2min 2 2

一維搜索求步長(1x(20 1 x(1)h(1)00 1 x1x2f(xf(x(1)h(1))226令 03,0 d

故(1)1x(2)x(1)(1)h(1)F(h(160第二次迭 4）x(2)1，I(x(21,2,f(x A 1,b1,A 0,b0 1 0 在點(diǎn)x(2)處求可行下降方向h(2)，minf(x(2))T(LP)

A1h

1,jmin 2hh 即(LP) hh 1h1 1h2 5）確定Ah(2) 01 bAx(1)

(2)2 min ,A2

A 1 0 1 2A2

0,

16）一維搜索求步長(2),x(3) 1 1x(2)h(2)1 1 1 x11x21f(x中f(x(2)h(2))222令 01,0 d

1(2)1x(3)2

(2)

2 23 2第二次迭代結(jié)F(h(220，繼續(xù)迭 3

7）對x(3) ，I(x(3))2,f(x(3)) 2

1 A 1,b2,A 0,b0 x(3)處求可行下降方向h(3)解線性規(guī)劃問minF(h)f(x(3))T(LP)

1,jminF(h)h1 hh(LP

1h11h2 3F(h(3))0,由定理知，x(3) 是K- 2)

3為原（NLP)的全局最優(yōu)

2二.非線性約 考慮不等式約束 f(x) gi(x)0,i其中n,f(xg(x)i

選擇下降可行是在處起作用約束下標(biāo)集又,

gi(x)f(x)gi(x)(iI(x))在處可微函,數(shù)在gi(x)(iI(x))連續(xù),如果f(x)Th g(x)Thi則

iI f(x)Th gi(x)T

h (iI gi(x) gi(x)(iI(x))gi(xh) iI(x) 當(dāng)(x)在可微(x gi(xh)gi(x)gi(x)Th+o(hgi(xh)gi

g(x)Th+o(h

i()Th,右端i0端由.gi(x)0(igi(xh)由上分析知,對充分小的gi(xh)0,i( 因此h為x處的下

minfs.t.gi(x)0,i1 x點(diǎn)處的可行下降方向d滿足g(x)Td0,iI(x zzdf(x)Tdg(x)Tdz,iI(x) z下降最多的方向d由方向?qū)?shù)f(x)f(x)Th

f

hcosf(x),可知，以上問題可以轉(zhuǎn)化為求使z最小的線性規(guī)劃問minf(x)Tdz(LP)s.tg()Tdz0,iI(x dd

1,j1假如(LP)的最優(yōu)解(z*d*z*0ii

有解d可行下降z*0ii

Gordan理可證此時x為原規(guī)劃的FritzJohnit

,I(x){i|gi(x)證明:問題(7)的目標(biāo)函數(shù)最優(yōu)值為0的充要條是不等式f(x)Th無

Th0,(iI f(x)Th0,gi(x)T無解

h0,(iI 存在不全為0的數(shù)使w00wi0,i (

w0f(x)

wg(x)T 為求步長,求解一維搜索問題minf(x(k)h(k) 0 SUP{g(x(k

h(k))0,i1,...,m} 計算步給定初始可行點(diǎn)(1) k令(){i|gi(x(k)) LP) s.t.f(x)Thzgi(x)Thz

iI(x)hj1,j1,...,得最優(yōu)解z,h(k),z;,,轉(zhuǎn),x(k Fritz 求解一維搜索minf(x(k)h(k)

0

得最優(yōu)解 中由給kk

x

x(k

h(k)

k:k 3.Topkis-Veinott修 f(x)Thzgi(x)Thzgi

ihj1,jTopkis-Veinott算給定初始可行點(diǎn)(1)

k f(x)Thzgi(x)Thzgi

ihj1,j得最優(yōu)解(zh(kk若 止 點(diǎn);,xk),

Fritz求解一維搜索minf(x(k)h(k) 0其中由ax

5)x置k,(11(k x5)x置k

h(k) k:k 定理：考慮問題函 f(x),gi(x)(i連續(xù)可微又設(shè)是{(k) Topkis的序列則的{x(k)一聚點(diǎn)都是 第五節(jié)約梯度自動化學(xué)1963年，Wo1fe(ReducedGradientMethod).考慮具有線性約束的非線性規(guī)劃問minf Ax x基本原用既約梯度構(gòu)造假設(shè)問題(1)的約束是 的，且xA N),xxBx）可以表示

Nminf(xB,xNs.t.BxBNxNxB,xN B1bB1Nx，用非基變量 代入目標(biāo)函數(shù)，得到即F(xNf(xB(xNminF(xNs.t.B

B1bB1N

xN當(dāng)xB0時，稱之為非 的情形，xB0表示xB的所有分量都大于0.xN0不帶其它約束條件因此問題(2)是比原來問題（1）較低維的簡單問 度r(xN)F(xNxBN f(xB(xN),xN)-(B1N)T f(xB(xN),xN)xBN由于（3）式中(N簡后的個變量n(xN的梯度xN，所以稱為的既約梯f(x，記為r(xN現(xiàn)在有了r(xN，我們要找f(x)的極小值，顯然就可以沿負(fù)既約梯度方向(r(xN))搜索移xN，使得目標(biāo)函數(shù)值下降。(k關(guān)鍵是如何確定在點(diǎn)xN處的可行下降方向 ？以及如何定步長

？以保x(k1)xk

h(k)是可行點(diǎn)，且目標(biāo)k值下降kh(k)記h(k) h(k h(k)h(k)h(k)分別對應(yīng)基變量和非基變量的分 為使目標(biāo)函數(shù)值下降，h(k)應(yīng)取負(fù)既約梯度方向h(k) N但是，當(dāng)某個分量 0且rj(xN)0時j沿負(fù)既約梯度方向?qū)?dǎo)致決策變量非負(fù)性不滿 rj(xN)0,j因此，定x(k)r(x(k)

r(x(k))h(khN

N

N N

rj(x(k))由前面引理知，為保證h(k)為可行方向，h(k)需要滿Ah(k)0h(k) N

0Bh(k

Nh(k) h(k h(k)B1Nh(k

x(k)0因此h(k)x(k)也一定是可行方向，故 h(k)B1Nh(k)Nh(khN

下面確定步長k x(k1)x(k

h(k)k x(k1)x(kk

h(k

0,j1njh(k)0時，對任意的0（7）jjh(k)0時，應(yīng)取j

(kxh(k)xhh(k)

min

(kxjx

h(k

其

(k h h定理：設(shè)x是問題（1）的可行解，A N mn矩陣B為m階可逆矩

xT, 函數(shù)f(x在點(diǎn)x處可微，又設(shè)h是（4）和（5）式定義的方向，如果h0，則h是下降可行方向，而且h0的充要條xK-T既約梯度法的迭代步驟給出初始可行點(diǎn)x(1，容許誤差0k從x(k)中選擇m個大分量，它們的下標(biāo)集記為 kAj列記為PjB是由PjjJk構(gòu)成的mN是由PjjJk構(gòu)成的mnm(3)求出 )，并由式（4）和式（5）求出h(k)和h(k) 從而得到搜索方向h(k

h(k

，則停止計算，得到點(diǎn)x(k)作為的最優(yōu)解，停止迭代；否則，轉(zhuǎn)由（8）式求 ，從x(k)出發(fā)，沿h(k)搜索minf(x(k)h(k)s.t.0得到最優(yōu)解kx(k1)x(kk

h(kkk1 f(x)4x1, f(x)2x2 f(x(1))4, f(x(1)) r(x(1)) N

f(x(1))(B1N)TxBx

r(x(1))160,d(1)x(1)r(x(1)) N1 r(x(1))60,d(1)r(x(1)) r(x(1))50,d(2)x(2)r(x(2))

N1 r(x(1))50,d(2)r(x(2)) 第十次規(guī)劃Quadratic自動化學(xué)第一節(jié)接消去自動化學(xué)什么是二次規(guī)劃等式約束二次規(guī)劃問題的解法直接消去法(DirectEliminationLagrange直接消去法(DirectElimination第二節(jié)Lagrange自動化學(xué)考慮二次規(guī)

min1xTHxcT2 Ax

Rank(A)m,xRn,bLagrange函L(x,)1xTHxcTxT(Ax 2令xL(x)0L(x)Axb ATx

c即

Lagrange矩陣可 AT

RT

，由 AT

In HQATRnHRTATSAQARTm

假設(shè)H1存在，由上述關(guān)系得到矩陣QR,S的表達(dá)QH1H1AT(AH1AT)1AH S(AH1AT 由（3）式等號兩端乘以Lagrange矩陣的逆，則得到問題xQcRTRc

xx(k是（1）x(kAx(k)b，gkf(x(k))Hx(k)x(k)k

，可將（7）和（8）改xx(k

例用Lagrange minx22x2x2

x1x2x32x1x2x3解 H 0,c0,A

1,122

b4,H1

2 02

2 12

3

14 4

4 4Q 3,R

3

5

S4 2 11 3 代入得到問題的最優(yōu)

3x

22第三節(jié)作用集方自動化學(xué)對于不等minf(x)1xTHxCT2s.tAx

Lagrange起作用集方法是利用起作用為起點(diǎn)，把在該點(diǎn)起作用的約束作為等式約束kx(k)指標(biāo)集I(k)表示，求解等式約束問minfi aixi

iI(k

aiA的第ix(k處起作用約束函數(shù)x(k，令xx(k，則f(x)1(x(k))TH(x(k))cT(x(k))1THTHx(k)1x(k)THx(k)cTcTx(k 1THf(x(k))Tf(x