DC規(guī)劃的一些結(jié)論及推廣

付　裕，馬琳晶，李科科

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

?

DC規(guī)劃的一些結(jié)論及推廣

付裕，馬琳晶，李科科

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

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

最優(yōu)化理論和算法；DC規(guī)劃；反凸規(guī)劃；最優(yōu)解

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

1　預(yù)備知識

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

(1)

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

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

(2)

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

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

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

定義3[10]典范d.c.規(guī)劃問題是指如下形式的優(yōu)化問題：

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

2　DC規(guī)劃向典范形式的變換

子集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是凸函數(shù)，可以描述成如下形式：

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

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

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

(3)

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

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

(4)

設(shè)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均為凸函數(shù)，并且令

那么M為

定義凸函數(shù)φ(x,xn+1,xn+2)、凸函數(shù)ψ(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成立，即規(guī)劃(4)等價于規(guī)劃min{xn+1∈R∶(x,xn+1,xn+2)∈F}。綜上所述，引理2得證。

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

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

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

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

(5)

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

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

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

(6)

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

其中pj和qj均為凸函數(shù)，并且令

那么M為

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

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

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

3　一類DC規(guī)劃和反凸規(guī)劃

考慮如下形式的DC規(guī)劃：

其中：f和g是Rn上的2個凸函數(shù)；X是Rn內(nèi)的閉凸子集。

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

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

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

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

證明

1) 充分性。因為x*∈X是規(guī)劃(P)的一個最優(yōu)解，所以對任意的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*)為規(guī)劃(Q)的一個最優(yōu)解。

(7)

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

(8)

此時不等式(7)可變?yōu)椋?/p>

(9)

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

綜上所述，引理3得證。

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

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

4　一些特殊DC規(guī)劃的最優(yōu)性條件

先考慮一類DC規(guī)劃：

(10)

其中： f和g是Rn上的兩個凸函數(shù)；X是Rn內(nèi)的閉凸子集。

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

x∈X,t∈R}

證明

x∈X t∈R}

成立。

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

(11)

由x和t的任意性可知

(12)

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

綜上所述，引理4得證。

下面考慮一類特殊DC規(guī)劃：

(13)

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

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

(14)

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

(15)

綜上所述，定理1得證。

5　結(jié)束語

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

[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]郝斯特,帕達勞斯,托伊.全局優(yōu)化引論[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

重慶市研究生創(chuàng)新訓(xùn)練項目(CYS16144)

付裕(1990—),女,四川巴中人,碩士,主要從事全局最優(yōu)化研究，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規(guī)劃的一些結(jié)論及推廣[J].重慶理工大學學報(自然科學)，2016(10):163-168.