雍龍泉

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

?

約束二進(jìn)制二次規(guī)劃測(cè)試函數(shù)的一個(gè)構(gòu)造方法

雍龍泉

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

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

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

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

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

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

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

用x右乘上式, 得

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

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

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

定理3的證明見文獻(xiàn)[12]。

下面通過例子來說明上述定理的應(yīng)用。

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

2測(cè)試函數(shù)的構(gòu)造方法

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

其中c∈Rn,Q是n×n的實(shí)對(duì)稱矩陣,S是一個(gè)非空凸集。

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

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

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

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

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

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

(1)

(2)

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

下面給出約束二進(jìn)制二次規(guī)劃測(cè)試函數(shù)的構(gòu)造方法。

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

若取ε=3, 則a=-(M1+εI)z0=(0,2)T, 對(duì)應(yīng)的目標(biāo)函數(shù)

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

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

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

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

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

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

給一個(gè)可行點(diǎn)z0=(-1,-1,-1,1)T和一個(gè)n×n的實(shí)對(duì)稱矩陣M2(顯然這里M2不定), 利用前面例2的結(jié)果, 當(dāng)ε≥5時(shí)M2+εI為半正定矩陣。

若取ε=5,則a=-(M2+εI)z0=(6,8,4,-2)T,對(duì)應(yīng)的目標(biāo)函數(shù)

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

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

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

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

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

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

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

3測(cè)試函數(shù)的驗(yàn)證

為了驗(yàn)證所構(gòu)造測(cè)試函數(shù)的準(zhǔn)確性，用LINGO軟件分別就(QP4)、(QP6)和(QP7)進(jìn)行了求解，所得的結(jié)果見圖1—圖3。

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

LINGO軟件求解結(jié)果進(jìn)一步表明, 本文構(gòu)造的測(cè)試函數(shù)是正確的。

4結(jié)束語(yǔ)

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

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

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

[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]. 上海: 上海大學(xué), 2005.

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

[5]黃紅選.全局優(yōu)化引論[M].北京: 清華大學(xué)出版社, 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è)大學(xué)出版社,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ìn)制二次規(guī)劃問題的一種連續(xù)化方法[J].工程數(shù)學(xué)學(xué)報(bào),2006,23(3):499-504.

[責(zé)任編輯：張存鳳]

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

作者簡(jiǎn)介：雍龍泉(1980—), 男, 陜西省洋縣人, 陜西理工學(xué)院副教授, 主要研究方向?yàn)樽顑?yōu)化理論與算法。

基金項(xiàng)目：陜西理工學(xué)院科研計(jì)劃項(xiàng)目(SLGKYQD2-14)

收稿日期：2014-12-18

[中圖分類號(hào)]O224

[文獻(xiàn)標(biāo)識(shí)碼]A

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