廣義幾何規劃的一類全局收斂算法

曹香蓮,李 燦

(紅河學院數學學院,云南蒙自 661100)

0 引 言

記,ex= (ex1,ex2,…,exn)T,AiT= (aijl)n×ki,bi=(bi1,bi2,…,biki)T,i=0,1,…,m,j=1,2,…,n, l=1,2,…,ki,則上述問題轉化為,

乘子法是人們熟悉的一類約束非線性優化方法,其數值穩定好,計算過程簡單,其中Fletcher提出的增廣乘子法[1]最受重視.精確增廣Lagrange函數方法[2-6]是把無約束問題定義在原問題變量與乘子變量的乘積空間.而幾何規劃是特殊的非線性規劃,許多非線性優化的方法均可以應用到它中來.本文利用等式約束幾何規劃的精確增廣Lagrange函數[7],結合收斂快、效率高的擬牛頓法[8],再利用幾何規劃的特點,給出了一類有效的求解等式約束優化問題的算法,并在適當條件下,證明了該算法的全局收斂性.

引理1 問題(GPE2)為一凸規劃.

我們構造問題(GPE2)的精確增廣Lagrange函數為,

1 幾何規劃問題

考慮等式約束下的廣義幾何規劃的一般形式,

如果令xj=lntj,j=1,2,…,n,則(GPE)可轉化為如下等價形式:

式中,λ=(λ1,λ2,…,λm)T是問題(GPE2)在最優解 x=x＊時的拉格朗日乘子的一個近似,C(x)= (C1(x),C2(x),…,Cm(x))T,σ＞0為罰因子.

由式(1)可得到,

由此可構造如下方程組,

式中,Bk為Lagrange函數的二階導數矩陣的某種近似,令,

顯然,Bk與 ▽C(xk)Bk▽C(xk)T是非奇異的,則式

(2)的解為,

假設,▽C(k)=[▽C1(x),▽C2(x),…,▽Cm(x)],對一切 x∈Rn行滿秩.

定理1 設x＊與λ＊滿足x＊是問題(GPE2)的嚴格局部極小點的二階充分條件,則存在σ＊＞0,使對所有的σ≥σ＊,x＊為L(x,λ＊,σ)的一個無約束極小點;反之,若有 Ci(x—)=0,1≤i≤m,并且x—是L(x,λ,σ)對于某個λ—的無約束極小點,則 x—為問題(GPE2)的最優解.

2 算 法

有了以上的準備,下面給出本文的算法步驟如下:

(1)選取初始值x0∈Rn,λ0,σ0＞0,B0=I,置k:=0;

(2)計算 Ci(xk),▽Ci(xk),▽xL(xk,λk,σ);

(3)由式(3)和式(4)計算出 △λk和 △xk;

(4)若 △xk=0,則xk為問題(GPE2)的 K-T點,停;

(5)求解 ?k為(1,…)中滿足下式,

的最大值;

(6)修正罰因子σk為,其中,δ和ζ是正常數,rk= ‖λk‖;

3 收斂性證明

證明 (1)充分性.

若 △xk=0,則由式(2)可得到,

即,

故 xk為問題(GPE2)的 K-T點.

(2)必要性.

因為 xk,λk為問題(GPE2)的 K-T點,所以,

又,

我們把 △λk=0代入式(3),可以得到,

因為我們總是假設 ▽C(xk)是行滿秩的,所以有,△xk=0.

因此,△xk為L(xk,λk,σk)下降方向.

引理2 若算法產生的數列{xk}有聚點,則存在k＊,當k＞ k＊時,σk≡σk＊?σ＊.

證明 采用反證法.

如果上式不成立,則有σk→∞(k→∞),由式(6)知,σk= rk+ζ,即,σk= ‖λk‖∞+ζ,從而‖λk‖∞→∞(k→∞),則有{xk}無界.這與假設{xk}有聚點矛盾,故引理2成立.

引理3 當 △xk≠0時,函數L(xk,λk,σk)為一單調下降函數.

證明 當 △xk≠0時,由定理2,▽L(xk,λk, σk)T△x＊＜0.因此,由式(6),

再由σk的定義及引理2,引理3顯然成立.

定理3 若算法產生的點列{xk}為一無窮點列,則{xk}的任一聚點x＊都是問題(GPE2)的 K-T點.

證明 設存在無窮子集K,使k∈K,xk→x＊.定義,

顯然,由Ci(x),i=0,1,…,m的一階連續可微性,有,

由引理3知,L(xk,λk,σk)單調下降.

故由xk→x＊(k∈K)知,

假設 △x＊≠0,則在 x＊處有,▽L(x＊,λ＊, σ＊)T△x＊＜0.從而,由L(x,λ,σ)的凸性及單調下降知,當k∈K,k充分大時,進而有,

式中,?＊=max{?k|k∈K,k→∞},由算法第5步,一定有 ?＊＞0,從而得出矛盾.因此,△x＊=0,則此定理成立.

[1]Fletcher R.An Ideal Penalty Function for Constrained Optimization[J].J Applied Mathematics,1975,15(3):319-342.

[2]Di Pillo G,Grippo L.A New Augmented Lagrangian Function for Inequality Constraints in Nonlinear Programming Problems[J].J Optim Theory Appl,1982,36(4):495-519.

[3]Di Pillo G,Grippo L.A New Class of Augmented Lagrangians in Nonlinear Programming[J].SIAM J Control Optim,1979,17 (5):618-628.

[4]Di Pillo G,Lucidi S.An Augmented Lagrangian Function with Improved Exactness Properties[J].SIAM J Optim,2001,12(2): 376-406.

[5]Di Pillo G,Lucidi S.On Exact Augmented Lagrangian Functions in Nonlinearprogramming[C]//Nonlinear Optimization and Applications.NewY ork:Plenum Press,1996:85-100.

[6]Lucidi S.New Results on A Class of Exact Lagrangian Functions [J].J Optim Theory Appl.1988,58(2):259-282.

[7]王秀國,薛 毅.基于增廣Lagrange函數的RQP方法[J].計算數學,2003,25(4):393-406.

[8]蘇 洲.約束變尺度法應用研究[J].河海大學機械學院學報,1996,10(4):1-5.