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

付　裕，馬琳晶，李科科

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

?

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

付裕，馬琳晶，李科科

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

針對(duì)DC(difference of convex)規(guī)劃，結(jié)合最優(yōu)化理論和算法的相關(guān)知識(shí)，用不同的方法對(duì)DC規(guī)劃中已有的一些定理和結(jié)論進(jìn)行了證明。在此基礎(chǔ)上，對(duì)其中一些結(jié)論進(jìn)行了推廣，并且闡述了一類DC規(guī)劃和其對(duì)應(yīng)的反凸規(guī)劃的最優(yōu)解之間的聯(lián)系。最后利用L-次微分等相關(guān)知識(shí)，提出并討論了一類特殊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)濟(jì)、管理和工程等領(lǐng)域有著廣泛的應(yīng)用。事實(shí)上，許多最優(yōu)化問題，如不定二次規(guī)劃[1]、弱凸規(guī)劃[2]和廣義幾何規(guī)劃[3-4]等，都是DC規(guī)劃問題的特殊形式。許多方面的應(yīng)用涉及的函數(shù)可以表示成2個(gè)凸函數(shù)的差，此時(shí)產(chǎn)生的優(yōu)化問題可以表示為DC規(guī)劃，例如聚類分析、選址問題、交通運(yùn)輸規(guī)劃、多層次規(guī)劃、多目標(biāo)規(guī)劃和工程設(shè)計(jì)等[5-9]。由于許多數(shù)學(xué)規(guī)劃問題都可以轉(zhuǎn)化為DC規(guī)劃來求解，因此研究DC規(guī)劃的理論和算法具有重要的理論意義和應(yīng)用價(jià)值。

1　預(yù)備知識(shí)

定義1[10]定義在凸集X?Rn上的實(shí)值函數(shù)f稱為X上的d.c.(或者DC)是指對(duì)于所有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)，并且對(duì)所有的i=1,…,m，令fi(x)=0，那么規(guī)劃(2)可以轉(zhuǎn)化為如下形式的規(guī)劃：

其中： f和g是Rn上的2個(gè)凸函數(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中的兩個(gè)凸集。在文獻(xiàn)[10]中，R.Horst和N.V.Thoai給出了如下引理1和引理2，本文給出引理2的詳細(xì)證明過程。

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

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

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

證明因?yàn)镽n中的每個(gè)形如問題(2)的規(guī)劃等價(jià)于Rn+1中如下形式的規(guī)劃：

(3)

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

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

(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)等價(jià)于規(guī)劃min{xn+1∈R∶(x,xn+1,xn+2)∈F}。綜上所述，引理2得證。

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

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

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

因?yàn)橐?guī)劃(3)可以轉(zhuǎn)換成一個(gè)與Rn+k中等價(jià)的如下形式的規(guī)劃：

(5)

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

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

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

(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)等價(jià)于規(guī)劃

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

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

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

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

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

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

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

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

證明

1) 充分性。因?yàn)閤*∈X是規(guī)劃(P)的一個(gè)最優(yōu)解，所以對(duì)任意的x∈X有不等式 f(x*)-g(x*)≤f(x)-g(x)成立。令t*=g(x*)，則對(duì)所有滿足條件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)的一個(gè)最優(yōu)解。

(7)

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

(8)

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

(9)

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

綜上所述，引理3得證。

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

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

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

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

(10)

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

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

x∈X,t∈R}

證明

x∈X t∈R}

成立。

事實(shí)上，因?yàn)辄c(diǎn)x*∈X是問題(10)的一個(gè)最優(yōu)解，對(duì)任意的x∈X有下列不等式成立：

(11)

由x和t的任意性可知

(12)

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

[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].自動(dòng)化學(xué)報(bào)，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]郝斯特,帕達(dá)勞斯,托伊.全局優(yōu)化引論[M].黃紅選譯.北京：清華大學(xué)出版社，2003.

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

(責(zé)任編輯陳艷)

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)練項(xiàng)目(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].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2016(10):163-168.