一類特殊DC規劃的最優性條件和最優化方法

馬琳晶，付 裕

(重慶師范大學 數學科學學院，重慶 401331)

?

一類特殊DC規劃的最優性條件和最優化方法

馬琳晶，付 裕

(重慶師范大學 數學科學學院，重慶 401331)

研究一類特殊DC規劃(即目標函數為DC函數，約束為線性約束和箱子約束)，給出這類DC規劃的一個全局必要性條件，并且根據這個全局必要性條件，結合DCA算法設計了新的局部優化算法，即強局部算法.再利用輔助函數，即填充函數法，給出了一個全局優化方法.最后，通過求解數值算例以及對數值結果的分析，說明新的局部優化算法和全局優化方法的有效性.

DC規劃；DC算法(DCA)；全局必要性條件；全局優化方法

DC規劃在非凸規劃領域有重要的地位，很多非凸規劃問題都可以轉化為DC規劃，比如二次規劃，弱凸規劃，弱凹規劃等.由于DC規劃特殊的結構和廣泛的應用背景，從而引起了學者的關注.一個函數如果可以表示成兩個凸函數相減，那它就稱為DC函數.

解決DC規劃的方法有很多，其中DCA算法是比較出名的一個算法，它由Tao等人提出.它建立于DC規劃的對偶理論與局部最優性條件，與其他方法相比，它的計算速度非?？?，因此，在處理大規模問題時有優勢，并且對于有些問題，計算時常常收斂于全局最優解，但是它只能獲得局部最優解，原因是缺乏可驗證的全局最優性條件[1-7].

填充函數法是一類比較有效的全局優化方法，Wu Z Y等人提出了一類弱凹規劃的全局必要條件，并利用填充函數給出了全局優化方法[8].現有的一些解決DC規劃的全局優化方法，有：分支定界法、分支定界法與外趨近法結合、DC規劃的棱柱算法等[9-10]，這些方法的缺陷在于無法處理大規模問題.因此，DC規劃的全局最優性條件和全局最優化方法的研究很有意義.

本文考慮如下特殊DC規劃問題：

(Q)

其中:f(x)是可微的凸函數，A是m×n矩陣b∈Rm，ci,di∈R，ai≥0，ci≥0.

本文將給出這類特殊DC規劃問題(Q)的一個全局必要性條件，依據這個必要性條件，結合DCA算法，設計了一個新的局部最優解，即強局部算法.再結合填充函數法，給出了一個全局優化方法.最后，給出了數值算例，說明新的局部優化算法和全局優化方法的有效性.

1 預備知識

定義1[9-10]C是Rn上的凸集，T：C→R稱為C上的DC，如果存在G,H：C→R，使得T可以分解成如下的形式：T(x)=G(x)-H(x)，如果C=Rn，則T稱為DC函數.

如下的DC規劃模型：

[DC1] minG(x)-H(x)

其中G,H：X→R是凸函數，X是一個閉凸集.

引理1[9-10]通過添加一個變量t∈R，[DC1]可以等價為如下的反凸規劃[DC2]：

[DC2]minG(x)-t

其中G,H：X→R是凸函數，X是一個閉凸集.其最優解(x*,t*)滿足：x*∈X，G(x*)=t*.

由文獻[1,6],對于解決問題[DC1]的DCA算法歸納如下：

算法1[1,6]([DC1]的DCA算法)

步驟1 令x1∈dom?H(x)，i=1；

步驟2 計算yi∈?H(xi)；

步驟3 計算xi+1∈?G*(yi)(G(yi)的共軛函數)?xi+1是如下凸規劃的解：

步驟4 如果滿足終止條件，則停止；否則i=i+1，返回步驟2.

2 主要結論

本節利用降維的思想，將給出問題(Q)的一個全局必要性條件，根據必要性條件設計強局部算法，最后結合填充函數法，給出一個全局優化方法.為此，引入以下的記號：

2.1 全局必要性條件

(Qi)

(1)

(2)

式(1)就轉化為如下規劃：

(3)

對于任意i，如果Ki≠φ，即aji=0，則有xi∈R，因此，xi∈R(j∈Ki)；

從而問題(Q)轉化成一系列的凸規劃問題問題(Qi).

問題(Qi)是閉凸集上的一維凸規劃，因此，可以得到如下的全局必要性條件.

其中：

2.2 強局部算法

本節依據這個全局必要性條件，結合DCA算法設計了新的局部優化算法，即強局部優化算法.

算法2 (強局部優化算法[SLOM])

步驟1 如果i=n，轉步驟7；否則，轉步驟2；

步驟7 以x0為初始點，利用DCA算法，求得問題問題(Q)的一個局部極小點；

步驟8 如果滿足[NGOC],執行步驟9；否則，i=1，返回步驟1；

2.3 全局優化方法

本節，結合強局部算法和填充函數法，給出問題問題(Q)的全局優化方法，將利用如下的輔助函數[11]：

對于任意r>0，令：

令：

其中r>0，q>0為參數，x*為問題問題(Q)的當前局部極小點.

算法3 (全局優化算法[GOM])

步驟1 令:

轉步驟2；

步驟5 如果qk≤M，令qk=10qk，l=1，轉步驟1；否則轉步驟6；

3 數值結果與分析

本節將給出一些數值算例的結果，說明算法(SLOM)和算法(GOM)的有效性.

考慮如下的問題：

s.t. Ax≤b

其中:

當A=(1,2,3,4)，b=3時，數值結果由表1給出.

表1 EX1的數值結果

由表1可以看出，當初始點取為(0.12,0.2,0.2,0.2)T和(0.12,0,0,1)T，SLOM算法的結果改進了DCA算法的結果，當初始點取為(1,1,1,1)T，SLOM算法沒有改進DCA算法結果，是因為DCA算法獲得的點已經滿足[GNOC]，已經是強局部極小點，這說明，強局部算法是有效的.

考慮如下問題EX2：

s.t. Ax≤b

表2 EX2的數值結果

由表2可以看出，給出的三個初始點，DCA算法得到的結果與SLOM算法相同，原因是DCA算法得到的點已經滿足全局必要條件[GNOC].而GOM算法得到的結果比SLOM算法的結果好，充分顯示了，GOM算法的有效性.

4 結論

本文提出的問題(Q)的全局必要性條件是比較容易驗證的，第3節的算例的數值結果分析，表明強局部算法(SLOM)和全局優化方法(GOM)是可行的，并且是有效的，一般結果比DCA算法的結果要好，在以后的工作中，還將繼續研究一些特殊的DC規劃的全局最優性條件，和全局優化方法.

[1] HOAI A L T,PHAM D T.Sloveing a class of linearly constrained indefinite quadratic problems by dc.algorithms[J].Journal of Global Optimization，1997，11(3):253-285.

[2] HOAI L M,HOAI A L T,PHAM D T,et al.Block Clustering based on DC programming and DCA[J].NECO Neural Computation，2013，25(10):2776-2807.

[3] HOAI A L T,DINH T P.The DC (difference of convex functions) Programming and DCA revisited with DC models of real world nonconvex optimization problems[J].Ann Oper Res，2005，133：2346.

[4] NIU,Y S,PHAM D T,HOAI A L T,et al.Ecient DC Programming Approaches for Asymmetric Eigenvalue Complementarity Problem[J].Optimization Methods and Software，2013，28(4):812-829.

[5] HOAI A L T,PHAM D T,NGUYEN D Y.Behavior of DCA sequences for solving the trust-region subproblem,Journal of Global Optimization[J].Journal of Global Optimization,2012,53(2):317-329.[6] HOAI A L T,DINH T P,VAN N H.DC programming and DCA for General DC program[J].Advanced Computational Methods for Knowledge Engineering,2014(1):535-539.

[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] WU Z Y,BAI F S,YANG Y J,et al.Optimization Methods for Mixed Integer Weakly Concave Programming Problems[J].Journal of the Operations Research Society of China,2014(2):195-222.

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

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

[11] 李國權.非凸二次規劃問題的全局最優性條件及全局優化方法[D].上海：上海大學,2012.

責任編輯：時 凌

Global Optimality Condition and Method for a Special Class of DC Programming Probelms

MA Linjing,FU Yu

(School of Mathematical Sciences,Chongqing Normal University,Chongqing 401331,China)

In this paper, we established a necessary global optimality condition for a special class of DC programming problems with box and linear constraints. According to the necessary condition, we presented a new local optimization method for this DC program. Then, we designed a global optimization method by using auxiliary function. Finally, we also gave some examples to illustrate the efficiency of the new local optimization method and the global optimization method.

DC programming problems;DC algorithm(DCA);global optimality necessary condition;global optimization method

2016-07-13.

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

馬琳晶(1990- )，女，碩士生，主要從事全局最優化的研究.

1008-8423(2016)03-0309-06

10.13501/j.cnki.42-1569/n.2016.09.017

O224

A