DC規劃的一些結論及推廣

付　裕，馬琳晶，李科科

(重慶師范大學，重慶 401331)

?

DC規劃的一些結論及推廣

付裕，馬琳晶，李科科

(重慶師范大學，重慶 401331)

針對DC(difference of convex)規劃，結合最優化理論和算法的相關知識，用不同的方法對DC規劃中已有的一些定理和結論進行了證明。在此基礎上，對其中一些結論進行了推廣，并且闡述了一類DC規劃和其對應的反凸規劃的最優解之間的聯系。最后利用L-次微分等相關知識，提出并討論了一類特殊DC規劃和其相關的一類凸規劃的最優解之間的聯系與區別。

最優化理論和算法；DC規劃；反凸規劃；最優解

DC(difference of convex)規劃是非凸規劃中很重要的一類規劃問題，它在經濟、管理和工程等領域有著廣泛的應用。事實上，許多最優化問題，如不定二次規劃[1]、弱凸規劃[2]和廣義幾何規劃[3-4]等，都是DC規劃問題的特殊形式。許多方面的應用涉及的函數可以表示成2個凸函數的差，此時產生的優化問題可以表示為DC規劃，例如聚類分析、選址問題、交通運輸規劃、多層次規劃、多目標規劃和工程設計等[5-9]。由于許多數學規劃問題都可以轉化為DC規劃來求解，因此研究DC規劃的理論和算法具有重要的理論意義和應用價值。

1　預備知識

定義1[10]定義在凸集X?Rn上的實值函數f稱為X上的d.c.(或者DC)是指對于所有x∈X,f能表示成

(1)

其中，p,q是X上的凸函數。Rn上的d.c.稱為d.c.函數(或者DC函數)，式(1)稱為f的d.c.分解(或者DC分解)。

定義2[10]全局優化問題稱為d.c.規劃問題，或者d.c.規劃(DC規劃)，是指它具有如下形式：

(2)

其中X是Rn上的閉凸子集，且所有的函數fi是d.c.函數(i=0,1,…,m)。

不失一般性，令f0(x)=f(x)-g(x)，并且對所有的i=1,…,m，令fi(x)=0，那么規劃(2)可以轉化為如下形式的規劃：

其中： f和g是Rn上的2個凸函數；X是Rn中的閉凸子集。

定義3[10]典范d.c.規劃問題是指如下形式的優化問題：

其中c∈Rn，g∶Rn→R上是凸的，并且D是Rn的閉凸子集。

2　DC規劃向典范形式的變換

子集F∈Rn稱為d.c.集，是指它可以表示為F=DK，其中D和K是Rn中的兩個凸集。在文獻[10]中，R.Horst和N.V.Thoai給出了如下引理1和引理2，本文給出引理2的詳細證明過程。

引理1[10](1)對于每一個集合M={x∈Rn∶di(x)≤0,di(x)是d.c.(i=1,…,m)}有一個d.c.集F∈Rn+1，使得(x,xn+1)∈F?x∈M。(2)每個d.c.集F={x∈Rn∶h(x)≤0,g(x)≥0},其中h和g是凸函數，可以描述成如下形式：

其中，函數d(x)是d.c.函數。

引理2[10]Rn中的每個d.c.規劃可以轉換成1個等價的Rn+2中的典范d.c.規劃。

證明因為Rn中的每個形如問題(2)的規劃等價于Rn+1中如下形式的規劃：

(3)

定義gj(x,xn+1)(j=0,1,…,m)如下：

則規劃(3)可寫為如下等價形式：

(4)

設M和gj(x,xn+1)分別為：

M={xn+1∈R∶gj(x,xn+1)≤0

j=0,…,m, x∈Rn}

gj(x,xn+1)=pj(x,xn+1)-qj(x,xn+1)

j=0,1,…,m

其中pj和qj均為凸函數，并且令

那么M為

定義凸函數φ(x,xn+1,xn+2)、凸函數ψ(x,xn+1,xn+2) 和d.c.集F分別為：

φ(x,xn+1,xn+2)=p(x,xn+1)-xn+2

ψ(x,xn+1,xn+2)=q(x,xn+1)-xn+2

F={(x,xn+1,xn+2)∈Rn+2∶φ(x,xn+1,xn+2)≤0,

ψ(x,xn+1,xn+2)≥0}

那么，(x,xn+1,xn+2)∈F?x∈M成立，即規劃(4)等價于規劃min{xn+1∈R∶(x,xn+1,xn+2)∈F}。綜上所述，引理2得證。

由引理1和引理2以及引理2的證明可得到命題1，該命題是引理2的推廣形式。

命題1Rn中的每個d.c.規劃可以轉換成一個等價的Rn+k(k為正整數)中的典范d.c.規劃。

證明由引理2的證明可知Rn中的每個形如問題(2)的規劃等價于Rn+1中的形如(3)的規劃。

因為規劃(3)可以轉換成一個與Rn+k中等價的如下形式的規劃：

(5)

所以，Rn中的每個形如問題(2)的規劃等價于Rn+2中的形如(5)的規劃。

定義gj(x,xn+1,xn+2),j=0,1,…,m+1,如下：

那么規劃(5)可寫為如下等價形式：

(6)

設M和gj(x,xn+1)分別為：

其中pj和qj均為凸函數，并且令

那么M為

分別定義凸函數φ(x,xn+1,xn+2,xn+3)、凸函數ψ(x,xn+1,xn+2,xn+3)和d.c.集F如下：

那么(x,xn+1,xn+2,xn+3)∈F?x∈M成立，即規劃(6)等價于規劃

以此類推可得：Rn中的每個d.c.規劃可以轉換成一個等價的Rn+k(k為正整數)中的典范d.c.規劃。

3　一類DC規劃和反凸規劃

考慮如下形式的DC規劃：

其中：f和g是Rn上的2個凸函數；X是Rn內的閉凸子集。

利用1個輔助變量t(∈R)，定義如下規劃：

規劃(Q)稱為反凸規劃[11]。

R.Horst和N.V.Thoai在文獻[9]中給出了引理3，本文給出引理3的證明過程。

引理3[1]x*∈X是規劃(P)的一個最優解，當且僅當存在t*∈R，使得(x*,t*)為規劃(Q)的一個最優解。

證明

1) 充分性。因為x*∈X是規劃(P)的一個最優解，所以對任意的x∈X有不等式 f(x*)-g(x*)≤f(x)-g(x)成立。令t*=g(x*)，則對所有滿足條件t≤g(x)的x(∈X)和t(∈R)有不等式 f(x)-t≥f(x)-g(x)≥f(x*)-g(x*)=f(x*)-t*成立，故(x*,t*)為規劃(Q)的一個最優解。

(7)

成立。因為(x*,t*)是規劃(Q)的一個最優解，所以對任意的x∈X和t∈R有g(x*)-t*≥0和

(8)

此時不等式(7)可變為：

(9)

不等式(9)與(8)矛盾，所以，x*不是規劃(P)的一個最優解。

綜上所述，引理3得證。

由引理3和其證明過程可得以下命題：

命題2x*∈X是規劃(P)的一個最優解當且僅當(x*,t*)為規劃(Q)的一個最優解，其中t*=g(x*)。

4　一些特殊DC規劃的最優性條件

先考慮一類DC規劃：

(10)

其中： f和g是Rn上的兩個凸函數；X是Rn內的閉凸子集。

文獻[12]給出了規劃(10)的一個最優性條件，即引理4，并利用互反原理和集合的魯棒性等知識對引理4進行了證明。本文將給出引理4的第2個證明方法。

x∈X,t∈R}

證明

x∈X t∈R}

成立。

事實上，因為點x*∈X是問題(10)的一個最優解，對任意的x∈X有下列不等式成立：

(11)

由x和t的任意性可知

(12)

即點x*∈X是問題(10)的一個最優解。

綜上所述，引理4得證。

下面考慮一類特殊DC規劃：

(13)

其中：f是Rn上的凸函數；g是Rn上的連續可微凸函數，且ui

成立，且G(x)是Rn上的凸函數。因此，規劃(14)為凸規劃。

(14)

由DC規劃(13)和凸規劃(14)之間的聯系，可得以下定理：

(15)

綜上所述，定理1得證。

5　結束語

本文利用最優化理論和算法的相關知識，使用不同于以前的方法對DC規劃中已有的一些定理和結論進行了詳細證明，并對其中一些結論進行了推廣，闡述了一類DC規劃和其對應的反凸規劃的最優解之間的聯系與區別。此外，本文還運用L-次微分等相關知識，提出并討論了一類特殊DC規劃和一類凸規劃的最優解之間的關系。本文的內容和結果對研究DC規劃具有重要的理論意義和應用價值，在此基礎上，還可以進一步對DC規劃的最優性條件和最優化算法進行研究和探索。

[1]ABSIL P A,TITS A L.Newton-KKT interior-point methods for indefinite quadratic programming[J].Computational optimization and applications，2007，36(1):5-41.

[2]WU Z Y.Sufficient Global Optimality Conditions for Weakly Convex Minimization Problems[J].Journal of Global Optimization，2007，39:427-440.

[3]TSENGA C L，ZHANB Y,ZHENGB Q P，et al.A MILP formulation for generalized geometric programming using piecewise-linear approximations[J].European Journal of Operational Research，2015，245(2):360-370.

[4]SHEN P P,LI X A.Branch-reduction-bound algorithm for generalized geometric programming[J].Journal of Global Optimization，2013，56(3):1123-1142.

[5]周波，錢堃，馬旭東，等.一種新的基于保證定界橢球算法的非線性集員濾波器[J].自動化學報，2013，39(2):150-158.

[6]ASTORINO A,MIGLIONICO G.Optimizing sensor cover energy via DC programming[J].Optimization Letters，2016，10(2):355-368.

[7]DINH T P，HOAI A L T,PHAM V N， et al.DC programming approaches for discrete portfolio optimization under concave transaction costs[J].Optimization Letters，2016，10(2):261-282.

[8]HOAI A L T，DINH T P.DC programming in communication systems:challenging problems and methods[J].Vietnam Journal of Computer Science，2014，1(1):15-28.

[9]HOAI A L T，NGUYEN M C,DINH T P.A DC Programming Approach for Finding Communities in Networks Neural Computation，2014，26(12):2827-2854.

[10]HORST R，PARDALOS P M,THOAI N V.Introduction to Global Optimization[M].Second Edition.Kluwer Academic Publishers，2000.

[11]TUY H.Convex programs with an additional reverse convex constraint[J].Journal of Optimization Theory and Applications，1987,52(3):463-486.

[12]郝斯特,帕達勞斯,托伊.全局優化引論[M].黃紅選譯.北京：清華大學出版社，2003.

[13]HORST R，THOAI N V.DC Programming:Overview[J].Journal of Optimization Theory and Applications，1999,103(1):1-43.

(責任編輯陳艷)

Some Conclusions and Generalization of DC Programming

FU Yu，MA Lin-Jing，LI Ke-ke

(Chongqing Normal University, Chongqing 401331, China)

For DC (difference of convex) programming, some theorems and conclusions of it were proved combined with the relevant knowledge of the optimization theory and method by using different methods. And on this basis, some of these conclusions have promoted. Furthermore, we expounded the relationship of the optimal solution between the type of DC programming and their corresponding reverse convex programming. Finally, the relation and difference between the optimal solutions of a special class of DC programming and its related convex programming were presented and discussed by using the knowledge of L-subdifferential and other related knowledge.

optimization theory and algorithm; DC programming; reverse convex programming; optimum solution

2016-03-16

重慶市研究生創新訓練項目(CYS16144)

付裕(1990—),女,四川巴中人,碩士,主要從事全局最優化研究，E-mai:619668521@qq.com。

format：FU Yu，MA Lin-Jing，LI Ke-ke.Some Conclusions and Generalization of DC Programming[J].Journal of Chongqing University of Technology(Natural Science)，2016(10):163-168.

10.3969/j.issn.1674-8425(z).2016.10.026

O224

A

1674-8425(2016)10-0163-06

引用格式：付裕，馬琳晶，李科科.DC規劃的一些結論及推廣[J].重慶理工大學學報(自然科學)，2016(10):163-168.