約束二進制二次規劃測試函數的一個構造方法

雍龍泉

(陜西理工學院 數學與計算機科學學院， 陜西 漢中 723000)

?

約束二進制二次規劃測試函數的一個構造方法

雍龍泉

(陜西理工學院 數學與計算機科學學院， 陜西 漢中 723000)

[摘要]基于蓋爾圓定理, 給出了約束二進制二次規劃測試函數的一個構造方法: 對原問題, 通過線性變換, 得到一個新的不定二次規劃, 且該不定二次規劃恰好以給定初始點為最優解; 進而構造出了一系列具有共同最優解的約束二進制二次規劃。

[關鍵詞]二進制二次規劃;測試函數;半正定矩陣;蓋爾圓定理

非線性整數規劃在經濟、計算機科學、工程技術中有非常重要的應用。 多年的研究表明, 非線性整數規劃是數學規劃和運籌學中最困難的研究領域之一。 即使是形式上看起來很簡單的線性約束二次整數規劃在全空間上求解也是不可判定的, 即不存在求解該問題的算法。 因此, 在求解非線性整數規劃問題時, 往往要假定是在有界閉箱上進行求解。 0-1二次規劃是一類特殊的非線性整數規劃, 國外學者Barhona和Hansen對0-1二次規劃做了大量的研究, 并且給出了一些具體的實例[1-2]；國內學者對0-1二次規劃也做了大量的研究, 得到了一些比較好的結果[3-5]。 總體上說, 求解非線性整數規劃問題的方法到目前為止還不多, 現有的算法可分為3類：(1)化為等價問題，主要包含化為連續優化問題的方法和線性化為整數規劃問題的方法； (2)分支定界法，對目標函數和約束函數是可定界的非線性整數規劃問題, 這種方法是適用的；(3)近似方法，是為了盡快找到問題好的但未必是最優解而設計的方法, 主要包括隨機方法和局部搜索方法[7-11]。

衡量一個算法的優與劣, 就需要利用算法做相應的數值實驗進行測試。 而做數值實驗時, 就要求所給的測試問題的最優解已知；只有知道了測試問題的最優解之后, 那么用設計的算法來進行測試, 再用計算后的結果和已知最優解做比較, 這樣才能知道算法的優劣。因此, 如何構造測試問題(驗證算法的好與差), 這就成了計算數學的難點。 本文初步給出了約束二進制二次規劃測試函數的一個構造方法: 用給定的可行點z0和矩陣M構造出了一系列的約束二進制二次規劃, 使得這些二進制二次規劃都具有共同的最優解。

1預備知識

定理1設A是n×n的實對稱矩陣, 則A的特征值皆為實數。

用x右乘上式, 得

定理2(蓋爾圓定理) 矩陣A=(aij)∈Cn×n的一切特征值都在它的n個蓋爾圓的并集之內。

也就是λ∈Gi0,當然λ也在A的n個蓋爾圓Gi(i=1,2,…,n)的并集之內。

定理3由矩陣A的所有蓋爾圓組成的連通部分中任取一個, 如果它是由k個蓋爾圓構成的, 則在這個連通部分中有且僅有A的k個特征值(蓋爾圓相重時重復計數, 特征值相同時也重復計數)。

定理3的證明見文獻[12]。

下面通過例子來說明上述定理的應用。

本文利用蓋爾圓定理得到了一系列ε使得M+εI半正定,此結果比文獻[13]中的結論更完善, 更具有普遍性。

2測試函數的構造方法

考慮如下形式的二進制二次規劃

其中c∈Rn,Q是n×n的實對稱矩陣,S是一個非空凸集。

作線性變換z=e-2x,其中eT=(1,1,…,1)。由于z=e-2x,也即x=(e-z)/2, 代入(QP1) 的目標函數中得到

(-c/2-Qe/4)Tz+zT(Q/4)z/2+cTe/2+eTQe/8,

若記a=-c/2-Qe/4,M=Q/4, 則(QP1)可以轉化為

注：通過線性變換z=e-2x,把x∈S變換為z∈D(由于S是非空凸集,故D也是非空凸集);(QP2)與(QP1)的最優解相同,其目標值僅相差一個常數k=cTe/2+eTQe/8。

證明考慮輔助函數

因此, 對任意的z∈D,z∈{-1,1}n,都有φ(z)≥φ(z0),即

(1)

(2)

由(2)式知道,對任意的z∈D,z∈{-1,1}n,都有f(z)≥f(z0);這表明所構造的f(z)恰好在z0點達到最優。

下面給出約束二進制二次規劃測試函數的構造方法。

例3z∈D,z∈{-1,1}2,其中集合D={(z1,z2)|z1+z2≤1,2z1-3z2≤5,-z1≤2},給一個可行點z0=(1,-1)T和一個n×n的實對稱矩陣M1(顯然這里M1不定), 利用前面例1的結果,當ε≥3時M1+εI為半正定矩陣。

若取ε=3, 則a=-(M1+εI)z0=(0,2)T, 對應的目標函數

此時, 相應的(不定)二次規劃為

由定理4可知, (QP3)的最優解為z*=z0=(1,-1)T。

再利用線性變換z=e-2x,得到相應的約束二進制二次規劃

且該約束二進制二次規劃的最優解為x*=(0,1)T。

進而,當ε≥3,比如取ε=4,5,6,…,可以得到一系列的二進制二次規劃, 使得這些二進制二次規劃都具有共同的最優解x*=(0,1)T。

例4z∈D,z∈{-1,1}4,其中集合

給一個可行點z0=(-1,-1,-1,1)T和一個n×n的實對稱矩陣M2(顯然這里M2不定), 利用前面例2的結果, 當ε≥5時M2+εI為半正定矩陣。

若取ε=5,則a=-(M2+εI)z0=(6,8,4,-2)T,對應的目標函數

此時,相應的(不定)二次規劃為

由定理4可知,(QP5)的最優解為z*=z0=(-1,-1,-1,1)T。

再利用線性變換z=e-2x, 得到相應的約束二進制二次規劃

且該約束二進制二次規劃的最優解為x*=(1,1,1,0)T。

進而, 當ε≥5,比如取ε=6,7,8,…,可以得到一系列的二進制二次規劃,使得這些二進制二次規劃都具有共同的最優解x*=(1,1,1,0)T。

例如取ε=1×104,得到如下約束二進制二次規劃(QP7)為

且該約束二進制二次規劃的最優解也是x*=(1,1,1,0)T。

3測試函數的驗證

為了驗證所構造測試函數的準確性，用LINGO軟件分別就(QP4)、(QP6)和(QP7)進行了求解，所得的結果見圖1—圖3。

圖1　(QP4)的LINGO代碼及求解結果

LINGO軟件求解結果進一步表明, 本文構造的測試函數是正確的。

4結束語

本文給出了約束二進制二次規劃測試函數的一個構造方法。 因此, 在對約束二進制二次規劃的算法做數值實驗的時候, 就不必再拿經典的例子[14]做測試, 而改用本文構造的算例進行測試, 這在很大程度上豐富了算法的數值實驗結果。

圖2　(QP6)的LINGO代碼及求解結果

圖3　(QP7)的LINGO代碼及求解結果

[1]BARAHONA F. A solvable case of quadratic 0-1 programming[J]. Discrete Applied Mathematics, 1986, 13(1): 23-26.

[2]HANSEN P. Methods of Nonlinear Zero-one Programming[J]. Annals Discrete Math，1979(5):53-70.

[3]陳偉.0-1二次規劃的全局最優性條件及算法[D]. 上海: 上海大學, 2005.

[4]鄧俊威.線性約束下0-1二次規劃問題的研究[D].北京: 清華大學, 2010.

[5]黃紅選.全局優化引論[M].北京: 清華大學出版社, 2005: 54-110.

[6]ADAMS W P,Forrester R J,Glover F W.Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs [J].Discrete Optimization,2004,1(2):99-120.

[7]PAN S H,TAN T,JIANG Y X.A global continuation algorithm for solving binary quadratic programming problems[J].Computational Optimization and Applications,2007,41(3):349-362.

[8]HE S,LUO Z Q,NIE J,et al.Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization [J].SIAM J Optim,2008,19(2):503-523.

[9]ENDRE B,HAMMER P L,SUN R,et al.A max flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO) [J].Discrete Optimization,2008,5(2):501-529.

[10]PARDALOS P M,PROKOPYEV O A,SHHLO O V,et al.Global equilibrium search applied to the unconstrained binary quadratic optimization problem [J].Optimization Methods and Software,2008,23(1):129-140.

[11]MU X W,ZHANG Y L,LIU S Y.A new branch and bound method with pretreatment for the binary quadratic programming [J].Applied mathematics and computation,2008,192(1):252-260.

[12]程云鵬.矩陣論[M].2版.西安: 西北工業大學出版社,2001:234-249.

[13]PARDALOS P M.Construction of Test Problems in Quadratic Bivalent Programming [J].ACM Transactions on Mathematical Software,1991,17(1):74-87.

[14]李興斯, 譚濤.求解二進制二次規劃問題的一種連續化方法[J].工程數學學報,2006,23(3):499-504.

[責任編輯：張存鳳]

Method of constructing test problems for constrained binary

quadratic programming

YONG Long-quan

(School of Mathematics and Computer Science, Shaanxi University of Technology,

Hanzhong 723000, China)

Abstract:Based on Gerschgorin’s disk theorem, a method of constructing test function with known global solution for a class of constrained binary quadratic programming is presented. By using the linear transformation, a new indefinite quadratic programming is obtained, whose minimum occurs at the initial point over the given domains. Furthermore, a series of binary quadratic programming that has a common optimal solution is constructed.

Key words:binary quadratic programming;test function;positive semidefinite matrix;Gerschgorin’s disk theorem

作者簡介：雍龍泉(1980—), 男, 陜西省洋縣人, 陜西理工學院副教授, 主要研究方向為最優化理論與算法。

基金項目：陜西理工學院科研計劃項目(SLGKYQD2-14)

收稿日期：2014-12-18

[中圖分類號]O224

[文獻標識碼]A

[文章編號]1673-2944(2015)06-0051-06