D.C.乘性規劃的全局優化算法

周雪剛

(廣東金融學院應用數學系，廣東 廣州 510521)

D.C.乘性規劃的全局優化算法

周雪剛

(廣東金融學院應用數學系，廣東 廣州 510521)

討論了凸集上的D.C.乘性規劃的全局優化算法。首先通過引入輔助變量將D.C.乘性規劃問題轉化為一個等價的D.C.規劃問題；再綜合利用分支定界與外逼近方法求解等價問題；最后用一個實例說明算法的實用性。

D.C.乘性規劃；全局優化；割平面；錐細分

考慮如下D.C.乘性規劃：

(1)

其中，0≤f:Rn→R與0

1 等價問題的轉化

首先將問題轉化為一個等價的D.C.規劃，為此，考慮如下函數F(x,λ)：

(2)

對函數g,h分別定義類似的函數G,H。

定義1設函數f:Rn→R的定義域包含0，且對所有的λ>0與x有f(λx)=λf(x)，則f是正齊次函數。

引理1[6]如果f是凸(凹)函數，則當λ>0時，F與是凸(凹)函數。

引理2[7]函數F(x,λ)是正齊次的，且對任意α2>α1>0，當F(x,λ)≠0時，有不等式F(α2(x,λ))=α2F(x,λ)>α1F(x,λ)=F(α1(x,λ))成立。

F(y,β)=βf(y/β)=βf(x)=f(x)g(x)G(y,β)=βg(y/β)=βg(x)=β2

(3)

定義如下D.C.規劃問題：

(Pd.c.) maxF(y,β)

(4)

設問題(P)和問題(Pd.c.)的最優值分別為v,v1，則v≤v1。

定理1如果(y*,β*)是問題(Pd.c.)的最優解，則y*/β*是問題(P)的最優解。如果x*是問題(P)的最優解，則(x*g(x*),g(x*))是問題(Pd.c.)的最優解。

βf(y/β)=F(y,β)≤F(y*,β*)=β*f(y*/β*)

(5)

根據引理1可知，問題(Pd.c.)中的函數H是凸函數，而F,G都是D.C.函數。定義函數F1(y,β)=βf1(y/β),F2(y,β)=βf2(y/β)，則F1,F2是凸函數，定義G1(y,β)=βg1(y/β)，G2(y,β)=βg2(y/β)，則G1,G2也是凸函數。則問題(Pd.c.)改寫為：

(6)

引入輔助變量μ,v，問題(Pd.c.)轉化為如下等價的問題:

(7)

并且定義如下集合：

(8)

2 上下界

由于問題(Pmain)的可行域包含于問題(Pk)的可行域而目標函數相同，則問題(Pk)的最優值是問題(Pmain)最優值的一個上界。假設Tk包含ki個多面體凸錐Cki(i=1,2,…,ki),且都有n+3條以(y0,β0,μ0,v0)為頂點的邊，設z0=(y0,β0,μ0,v0)且忽略C的上標，存在n+4個線性獨立的點z0,z1,…,zn+3使得:

不失一般性，假設對所有的i=1,2,…,n+3有‖zi‖=1，設θi=sup{θ∈R|z0+θ(zi-z0)∈G2∩G1}和wi=z0+θi(zi-z0)。定義U=(w1-z0,…,wn+3-z0)和L2={z∈Rn+3|z=z0+Uη,eTη≥1}，其中η=(η1,…,ηn+3),e=(1,1,…,1)T。由于z0,z1,…,zn+3是線性獨立，因而U是非奇異的，且有:

L2={z∈Rn+3|eTU-1(z-z0)≥1}

引理3Ω∩C?L2∩C。

證明由G2的凸性與L2的定義很容易證明。

設:

引理4Ω∩C?(L2∩{z|(z)≤0})∩C。

根據引理3，能求得問題(Pmain)的一個上界，設：

u=max{F(y,β)-μ|(y,β,μ,v)∈(L2∩{z|(z)≤0})∩C}

注意到(L2∩{z|l(z)≤0})∩C}是多面體，如果它是非空，則u的值可以它的某個極點上取得，如果它是空，設u=-∞。而(L2∩{z|(z)≤0})∩C}的頂點可以利用文獻[9]中的方法求得。對每一個i=1,2,…,n+3，設如果則z0+θi(zi-z0)與都是問題(Pmain)的可行點。那么:

是問題(Pmain)在Ω∩C上一個下界。假設下界是點(yl,βl,μl,vl)上達到，則根據引理2.2可知，不等式F(λyl,λβl,μl,vl)>F(l,βl,μl,vl)關于所有的λ>1都成立。因而:

l≥=max{F(λyl,λβl,μl,vl)|(λyl,λβl,μl,vl)∈Ω,λ>1}

大于或者等于l。

3 算法收斂性及實例

3.1算法及收斂性分析

根據前面的討論，求解問題(Pmain)的算法如下。

步0 設T0是以z0為頂點的滿足Ω∈T0的初始錐，置l0=-1，u0=∞，k=0。

步2 如果uk-lk=0，則停止，否則置M={Cki|uki≥lk}；選取C∈{Cki|uki=uk}，產生一個錐細分集Y。

步3Tk+1=(M/C)∪Y；lk+1=uk，uk+1=uk,k=k+1,轉步1。

3.2算例

以下例題說明算法的可行性:

原問題存在3個局部極大解，只有一個全局最優點。對比問題(1)形式，取:

對應的問題(Pmain)的函數為:

F1(y,β)-μ=y/4+20β-μF2(y,β)-μ=y2/β-μG1(y,β)-v=y4/(12β3)-v

β2+G2(y,β)-v=y2/(2β)+β2-4β-vH(y,β)=y2/β-16β

[1]Rúbia M. Oliveira, Paulo A. V. Ferreira. A convex analysis approach for convex multiplicative program-ming[J]. Journal of Global Optimization，2008,41(4): 579-592.

[2] Benson H P. An outcome space branch and bound-outer approximation algorithm for convex multiplicative programming[J]. Journal of Global Optim，1999,15: 315-342.

[3] Jaumard B, Meyer C, Tuy H.Generalized convex multiplicative programming via quasiconcave minimi-zation[J]. Journal of Global Optim，1997,10:229-256.

[4] Konno H, Kuno T, Yajima Y.Global minimization of a generalized convex multiplicative function[J]. Journal of Global Optim，1994,4: 47-62.

[5] Benson H P.Global maximization of a generalized concave multiplicative function[J]. Journal of Optimization Theory and Applications，2008,137: 105-120.

[6] Rockafellar R T, Wets R J R. Variational Analysis[M]. Berlin : Springer, 1998.

[7] Konno H, Yamashita H.Minimizing Sums and Products of Linear Fractional Functions ouer a Poly-tope[J].Naval Research Logistics,1999,46:583-596.

[8] Konno H, Ab N.Minimization of the Sum of Three Linear Fractional Functions[J].Journal of Global Optimization, 1999,15:419-432.

[9] Horst R,Tuy H. Global Optimization :Deterministic Approaches[M] . 3rd ed. Berlin : Springer Verlag ,1997.

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2011.04.001

O221.2

A

1673-1409(2011)04-0001-04