約束二進制二次規(guī)劃測試函數(shù)的一個構造方法

雍龍泉

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

?

約束二進制二次規(guī)劃測試函數(shù)的一個構造方法

雍龍泉

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

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

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

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

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

1預備知識

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

用x右乘上式, 得

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

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

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

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

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

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

2測試函數(shù)的構造方法

考慮如下形式的二進制二次規(guī)劃

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

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

(-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)的最優(yōu)解相同,其目標值僅相差一個常數(shù)k=cTe/2+eTQe/8。

證明考慮輔助函數(shù)

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

(1)

(2)

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

下面給出約束二進制二次規(guī)劃測試函數(shù)的構造方法。

例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, 對應的目標函數(shù)

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

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

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

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

進而,當ε≥3,比如取ε=4,5,6,…,可以得到一系列的二進制二次規(guī)劃, 使得這些二進制二次規(guī)劃都具有共同的最優(yōu)解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,對應的目標函數(shù)

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

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

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

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

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

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

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

3測試函數(shù)的驗證

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

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

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

4結束語

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

圖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二次規(guī)劃的全局最優(yōu)性條件及算法[D]. 上海: 上海大學, 2005.

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

[5]黃紅選.全局優(yōu)化引論[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版.西安: 西北工業(yè)大學出版社,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]李興斯, 譚濤.求解二進制二次規(guī)劃問題的一種連續(xù)化方法[J].工程數(shù)學學報,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—), 男, 陜西省洋縣人, 陜西理工學院副教授, 主要研究方向為最優(yōu)化理論與算法。

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

收稿日期：2014-12-18

[中圖分類號]O224

[文獻標識碼]A

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