二次規(guī)劃問(wèn)題

1、序列二次規(guī)劃法求解一般線性優(yōu)化問(wèn)題min f (x)hi(x) =0,i E=1,mJs.t.g(x) .0,i I =1,m?(1.1)基本思想：在每次迭代中通過(guò)求解一個(gè)二次規(guī)劃子問(wèn)題來(lái)確定一個(gè)下降方向，通過(guò)減少價(jià)值函數(shù)來(lái)獲取當(dāng)前迭代點(diǎn)的移動(dòng)步長(zhǎng)，重復(fù)這些步驟直到得到原問(wèn)題的解。1.1等式約束優(yōu)化問(wèn)題的 Lagrange-Newtoife考慮等式約束優(yōu)化問(wèn)題min f (x)s.t.h j (x) - 0, j E=1,，m(1.2)其中f ： Rn t R, hi :Rn t R(i w E)都為二階連續(xù)可微的實(shí)函數(shù).記 h(x) =(,(x),., hm(x)T .貝。)的Lagrang

2、e函數(shù)為：mL(x,u): f (x) i ui * hi(x); f (x) -uT * h(x)i 1(1.3)其中u =(U1,U2,., Um)T為拉格朗日乘子向量。約束函數(shù) h(x)的 Jacobi矩陣為：A(x) = $h(x)T = ($h1(x),., hm(x)T .T*ul對(duì)(1.3)求導(dǎo)數(shù)，可以得到下列方程組：.等卷尸、)現(xiàn)在考慮用牛頓法求解非線性方程(1.4).L(x,u)的 Jacobi矩陣為:N(x,u)=W(x,u) -A(x)T '<-A(x) 0)(1.(5)m其中 W(x, u) =Vxx L( x,u) =V2 f (x) _£ u

3、i * V2hi(x)是拉格朗日函數(shù)L(x,u)關(guān)于 x 的i 4Hessen 矩陣.N(x,u)也稱為K-T矩陣。對(duì)于給定的點(diǎn) 4 =(xk,uj ,牛頓法的迭代格式為：z« = Zk+Zk.其中A. =(dk,vj是線性方程組W(xk,uk)- A(xk)-A(xJ01Vk)，Z-7f(xk)+A(xk)Tuk<h(xk)(1.(6)的解。注意：只要A(xJ行滿秩且 W(xk,uJ是正定的，那么(1.6)的系數(shù)矩陣非奇異，且方程組 有唯一解。引理1：已知矩陣U w Rn加Sw Rn如，則對(duì)任意滿足ST*x = 0的非零向量x都有xTUx0的充要條件是存在常數(shù) 。* A0,使

4、得對(duì)任意的 仃之仃*都有xT*(Ur *S*S T)x 0,-x = 0 Rn.證明略。鑒于方程組(1.6)的求解數(shù)值不穩(wěn)定，故考慮將它轉(zhuǎn)化成一個(gè)嚴(yán)格凸二次規(guī)劃問(wèn)題.轉(zhuǎn)化的條件是(1.4)的解點(diǎn)x處的最優(yōu)性二階充分條件成立，即對(duì)滿足A(x )T * d = 0的任一向T量 d=0,成立 d *W(x ,u )* d >0O1 T再由引理1知：當(dāng)T >0充分小時(shí)， W(x*,u*) +A(x*)T A(x*)正定。2考慮(1.6)中的W(xk,uk)用一個(gè)正定矩陣來(lái)代替，記1 TB(xk,uk)=W(xk,uk) 3A"")則當(dāng)(xk,uk)T (x ,u )時(shí)，

5、矩陣B(x ,u )正定。(1.(6) 一個(gè)展開式為W(Xk,Uk)*d k-A(Xk)T *Vk f(Xk) A(Xk)T*Uk將上式變形為:1TT1W(Xk,Uk) hA(Xk)TA(Xk)*d k-A(Xk)T*Vk Uk "人函祝=Jf(Xk) 221令 Uk: = Vk +Uk + A(Xk)TdkW： B(Xk,Uk)*d k-A(x / * Uk = Vf %). 2因此，(1.6)等價(jià)于UkRf(Xk)'<h(X k) B(Xk,Uk) -A(xk)A(Xk)(1.(7)進(jìn)一步，可以把方程（1.7）轉(zhuǎn)換成如下嚴(yán)格凸二次規(guī)劃:誣朱二:叫山)s.t h(x

6、k) + A(x k) d = 0(1.(8)方程（1.7）和（1.8）具有同解的。1.2 一般形式的約束優(yōu)化問(wèn)題將1.1節(jié)中構(gòu)造二次規(guī)劃子問(wèn)題求解等式約束優(yōu)化問(wèn)題的思想推廣到一般形式的約束優(yōu)化問(wèn) 題（1.5）。在給定點(diǎn)Zk =（Xk,UkJ*）后，將約束函數(shù)線性化，并對(duì)拉格朗日函數(shù)進(jìn)行二次多項(xiàng)式近似，得到下列二次規(guī)劃子問(wèn)題:1 T.一.Tmin d W(Xk,uk)d , i f(X k) d2h(Xk) h(Xk)Td =0,i Es.t Tgi(Xk) ' gi(Xk) d =0,i I(1.9)其中 E =1,，m1, I =1,m2, Wk = W(x k, Uk,睚)=Xx

7、L(Xk,Uk,均)，拉格朗日函數(shù)為m1m2L(x,u) = f(x)- Ui * hi(x) J *g i(x).i 1i 1是，迭代點(diǎn)Xk的校正步dk以及新的拉格朗日乘子估計(jì)量 Uk由，書可以分別定義為問(wèn)題的一個(gè)K-T點(diǎn)x*和相應(yīng)的拉格朗日乘子向量U*,九* 。定理1:給定約束優(yōu)化問(wèn)題(1.1)的最優(yōu)解d *和相應(yīng)的拉格朗日乘子u*, K* > 0 .假定在x*處，下面的條件成立：(1) 有效約束的Jacobi矩陣Js(x*)行滿秩，其中S(x*)=ej i(x*)；(2) 嚴(yán)格互補(bǔ)松弛條件成立，即 gi(x*)之0J；之0,九i*gi(x*) =0, gi(x*)+九i* A0；(

8、3) 二階最優(yōu)性充分條件成立，即對(duì)滿足A(x )T* d =0的任一向量d#0,成立T*d *W(x ,u , )* d 0.*那么若(xk,Uk,%)充分靠近(x ,u ,九)，則二次規(guī)劃問(wèn)題(1.9)存在一個(gè)局部極小點(diǎn)d ,使,一一、.，.、，r 一 t一* *.得其對(duì)應(yīng)的有效約束指標(biāo)集S(d )與原問(wèn)題在x處的有效指標(biāo)集 S(x )是相同的。注意：在構(gòu)造二次規(guī)劃子問(wèn)題時(shí)， 需要計(jì)算拉格朗日函數(shù)在迭代點(diǎn)xk處的Hessen矩陣,計(jì)算量過(guò)大。為了克服這個(gè)缺陷，韓世平基于牛頓-拉格朗日法提出了一種利用對(duì)稱正定矩陣Bk來(lái)代替拉格朗日矩陣 Wk的序列二次規(guī)劃法。對(duì)于一般約束優(yōu)化問(wèn)題(1.1),在迭

9、代點(diǎn)Zk =(xk,uk,%),構(gòu)造下列形式的二次規(guī)劃子問(wèn)題:1 (1.10)min d B(x k, uk)d f(x k) d 2hi(xj ' hi(xJTd =0,i Es.tT9(xk)gi(xk) d =0,i I并且用(1.10)的解dk作為原問(wèn)題變量x在第k次迭代過(guò)程中的搜索方向。其中dk有一個(gè)好的性質(zhì)是它許多罰函數(shù)(價(jià)值函數(shù))的下降方向。例如，對(duì)于 L1精確罰函數(shù)：_ 一 1 一一P(x,二)=f(x) |hi(x)|gi(x)_ |i 壬iI其中 0 A 0 為罰參數(shù)，gi(x)_ =max0, _gi(x) 0為了保證SQR方法的全局收斂性，通常借助價(jià)值函數(shù)來(lái)確定

10、搜索步長(zhǎng)。用來(lái)衡量一維 搜索的好壞。算法(一般約束優(yōu)化問(wèn)題的SQP方法)Step 0:給定初始點(diǎn)(Xo,Uo, %)乏Rn父Rm1父Rm2,對(duì)稱正定矩陣B。乏Rn.計(jì)算A0 =Vh(x0)T , A0=yg(X0)T, A0 = A： IA01,選擇參數(shù)w(0,5), Pw(0,1),容許誤差01見(jiàn)玩1,令k：=o.Step 1:求解子問(wèn)題(1.10)得最優(yōu)解dk.Step 2:若 |dk |1" 且 |hk |1 +|(gk)_111M 玩，stop，得到(1.1)的一個(gè)近似 KT 點(diǎn)(Xk,Uk, 'k).Step 3:對(duì)于某種價(jià)值函數(shù) （x,。），選擇罰參數(shù)。使得dk是

11、該函數(shù)在Xk處的下降方向。Step 4: Armijo搜索.令mk是使下列不等式成立的最小非負(fù)整數(shù)m :中（Xk ,:mdk,；=k）。'（刈，；入）_ ： 2（Xk,；k；d k）,令 ak := Dmk,Xk 1 :=Xk akdk.Step 5: 計(jì)算Ak+=Vh(xk書),A<+ = h(xk41),4書=I LA；"以及最小二乘乘子,Uk+- . T 1,a IT r、=Ak 書Ak 書 A AkJfk 書L" 一Step 6:校正矩陣Bk為Bk小令Sk =akdk,yk ='、xL(Xk .1,山.1, 'kJxL(Xk,Uk1,

12、1)民 1 = BkBkSkSTBk .sk BSTZkZkskTzk其中Zk - &yk . (1 -九)Bksk參數(shù)4定義為1,Skyk _0.2sT BkSk6k =40.8sT BkSkn_ t _TT,Skyk 0 0.2s k Bk sk自 BkS< -s< ykStep 7：令 k:=k +1,轉(zhuǎn) 1.注意：(step 1)利用K-T條件，問(wèn)題(1.10)等價(jià)于Hi(d,u, ) =Bkd-(AE)Tu-(Ak)'"(Xk) =0,H2(d,u,K) =h(xj +AEd =0,(1.11) .0,g(Xk) Akd .0, g(Xk) Ak

13、d =0.第三式是m2維互補(bǔ)問(wèn)題，定義光滑函數(shù)中(；，a,b)=a b- a2 b2 2；2其中名>0為光滑參數(shù).令”，a,b)=( 1(%a,b),，m2(%a, b)T ,其中；，i（ ；,a,b） = i g（人）（Ak）id- ：一口國(guó)）（Ak）id22?其中（Ak）i表示Ak的第i行.記z = （%d,u$）w RQRnMR隈Rm2，那么（1.11）問(wèn)題等價(jià)H(z):= H( ,d,u,)%1|H1(d,u,九)H2(d,u?)R%dS) 一則H的Jacobi矩陣為100H'l。Bk-(AV10AE0_v D2(z)Ak00 1 -(Ak)T0Di(z) 一其中v =弁恪d , K) =(v1,Vm2)T ,Vi由下式確定:Vi2 ；i2 gi(Xk) (Ak)id2 2；2而 Di (z) =diag(a1(z),，ag (z), D2(z) =diag(D(z),，bm2 (z),其中 a3,bi(z)由下式確定:2 gi(Xk) (Ak)id2 2；2gi(xj (Ak)idbi 二 1 一 ,i2 gi(xk) (Ak)id2 2心給定參數(shù)¥三(0,1),定義非負(fù)函數(shù)：(z)= 11H(z)|min1,|H(z)|.(step 3)中選擇價(jià)值函數(shù),1：，(xQ