黃小利，高岳林，謝金宵，谷劍峰

(1.北方民族大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，寧夏 銀川750021;2.寧夏科學(xué)計(jì)算與智能信息處理協(xié)同創(chuàng)新中心，寧夏 銀川750021)

1.引言

本文主要考慮以下形式的二次約束二次規(guī)劃問(wèn)題:

這里fi(x)，i = 0，1，...，M是非凸二次函數(shù).()n×n是n × n階實(shí)對(duì)稱矩陣，，εi∈R，i = 0，1，...，M，j = 1，...，n，q = 1，...，n，A ∈Rm×n，b ∈Rm，l0= (，...，T，u0=(，...，)T，X0為非空有界閉集，記H0= [l0，u0]，H0是超矩形.非凸二次約束二次規(guī)劃(QCQP)問(wèn)題在實(shí)際生活中應(yīng)用范圍廣泛[1-4]，并且通常是全局優(yōu)化問(wèn)題，但在解決過(guò)程中往往存在許多局部最優(yōu)解而不是全局最優(yōu)解，且(QCQP)問(wèn)題是一個(gè)NP-hard問(wèn)題[5]，這就使得在理論和計(jì)算方面存在巨大的挑戰(zhàn).因此，尋找一種有效的算法全局求解(QCQP)問(wèn)題是十分有必要的.從(QCQP)問(wèn)題的研究歷程來(lái)看，已經(jīng)有許多算法都適用于求解全局(QCQP)問(wèn)題，現(xiàn)如今分支定界算法已成為求解該問(wèn)題最常用的工具之一.根據(jù)分支定界算法的框架，基于對(duì)(QCQP)問(wèn)題的松弛，在分支定界樹(shù)的每個(gè)節(jié)點(diǎn)求解松弛子問(wèn)題的下界，得到一個(gè)高質(zhì)量的下界對(duì)原問(wèn)題起著至關(guān)重要的作用.目前的(QCQP)松弛方法建立在多種松弛技術(shù)上，包括基于凹凸包絡(luò)的線性規(guī)劃松弛[6-7]，拉格朗日對(duì)偶松弛[6，8]，基于二階錐規(guī)劃(SOCP)的松弛[9]，基于半定規(guī)劃(SDP)的松弛[10].在求解盒約束非凸二次規(guī)劃時(shí)，文[11]在有限分支中使用半定規(guī)劃松弛技術(shù).在求解帶線性約束的非凸二次規(guī)劃問(wèn)題(LCQP)時(shí)，文[12]基于一階KKT條件的有限分支和多面體半定松弛求解(LCQP).在求解帶球和線性約束的非凸二次規(guī)劃問(wèn)題時(shí)，文[13]利用了半定規(guī)劃松弛逼近非凸二次規(guī)劃問(wèn)題.在求解帶一個(gè)非凸二次約束的二次規(guī)劃問(wèn)題時(shí)，文[14]將問(wèn)題轉(zhuǎn)化為一個(gè)無(wú)非凸約束的參數(shù)二次規(guī)劃問(wèn)題，通過(guò)迭代求解并在每次迭代中更新參數(shù).在求解帶多個(gè)二次約束的非凸二次規(guī)劃問(wèn)題時(shí)，文[15]給出了非凸二次約束二次規(guī)劃(QCQP)問(wèn)題的新的凸松弛方法，將每個(gè)非凸約束分解，并松弛為兩個(gè)二階錐約束，將這些非凸約束與線性約束的乘積線性化，以構(gòu)造一些新的有效約束; 文[16]基于特征值分解的分支定界算法來(lái)求解(QCQP)問(wèn)題，在特征值分解中，非凸分量由負(fù)特征值和相應(yīng)的特征向量表示，提出了一種基于半定松弛的分支定界算法來(lái)求解(QCQP); 文[17]用一種線性化方法將初始非凸規(guī)劃問(wèn)題化為一系列線性松弛規(guī)劃問(wèn)題; 文[8]將(QCQP)問(wèn)題轉(zhuǎn)化為拉格朗日對(duì)偶優(yōu)化問(wèn)題，并在更新拉格朗日乘子的同時(shí)連續(xù)求解子問(wèn)題; 文[18-20]提出了一種參數(shù)線性化方法來(lái)生成(QCQP)的參數(shù)線性松弛規(guī)劃，通過(guò)對(duì)可行域和目標(biāo)函數(shù)的線性松弛，將初始非凸問(wèn)題化為一系列線性規(guī)劃問(wèn)題; 文[21]利用重構(gòu)線性化技術(shù)在分支樹(shù)內(nèi)通過(guò)連續(xù)線性化來(lái)估計(jì)所有二次項(xiàng); 文[22]基于二次約束線性規(guī)劃的半定松弛，引入了一種特殊的懲罰方法，得到了所謂的條件擬凸松弛，證明了條件擬凸松弛比標(biāo)準(zhǔn)半定松弛能提供更緊的界.

非凸(QCQP)問(wèn)題的困難源于二次項(xiàng)的非凸分量，松弛過(guò)程中只需對(duì)目標(biāo)和約束函數(shù)中的二次項(xiàng)的非凸分量部分進(jìn)行操作.本文給出了求解非凸二次約束二次規(guī)劃(QCQP)問(wèn)題的全局優(yōu)化算法.該算法結(jié)合分支定界操作和區(qū)域縮減技術(shù)，通過(guò)對(duì)非凸二次項(xiàng)進(jìn)行新的參數(shù)化線性松弛，使用線性松弛技術(shù)將非凸(QCQP)問(wèn)題轉(zhuǎn)化為線性松弛規(guī)劃問(wèn)題，提出的線性化技術(shù)在不增加新的變量和約束的情況下，將線性松弛規(guī)劃問(wèn)題嵌入到分支定界操作中.為了加快算法的收斂速度，在分支和定界過(guò)程中采用了區(qū)域縮減技術(shù)，為當(dāng)前不存在全局最優(yōu)解的區(qū)域提供了理論可能性，可以顯著減少松弛間隙.最后，數(shù)值實(shí)驗(yàn)結(jié)果表明，該方法能較好地解決所有存在于全局最優(yōu)解中的(QCQP)問(wèn)題.

本文的組成結(jié)構(gòu)如下: 第一部分提出了二次約束二次規(guī)劃問(wèn)題，并且概述了在不同的約束條件下求解二次規(guī)劃問(wèn)題的相關(guān)算法.第二部分提出了新的參數(shù)化線性松弛技術(shù)從而得到含參數(shù)的線性松弛規(guī)劃問(wèn)題.第三部分為了加快算法收斂速度從而提出區(qū)域縮減技術(shù).第四部分將第二部分得到的參數(shù)化線性松弛規(guī)劃，以及第三部分的區(qū)域縮減技術(shù)嵌套在分支定界框架內(nèi)，得到參數(shù)化線性松弛分支定界算法以求解非凸二次約束二次規(guī)劃(QCQP).第五部分通過(guò)實(shí)例證明算法的有效性和可行性.第六部分得出相關(guān)結(jié)論.

2.新的參數(shù)化線性松弛技術(shù)

為了求解原問(wèn)題(QCQP)，本文采用一種新的參數(shù)化線性松弛技術(shù)得到原問(wèn)題和其子問(wèn)題的下界函數(shù).令H ={x=(x1，x2，...，xn)T∈Rn，l ≤x ≤u}?H0，其中l(wèi) =(l1，...，ln)T，u=(u1，...，un)T.與文[18]類似，我們定義ρ=(ρjq)n×n是一個(gè)對(duì)稱參數(shù)矩陣且ρjq∈{0，1}.對(duì)于任何的x ∈H，且j ∈{1，2，...，n}，q ∈{1，2，...，n}，jq，ρjq∈{0，1} 給出以下定義:

對(duì)于非凸二次函數(shù)的非線性項(xiàng)，接下來(lái)我們提出新的線性松弛技術(shù)，定義如下:

對(duì)于任何的x ∈H，且j ∈{1，2，...，n}，q ∈{1，2，...，n}，j =q，ρjj∈{0，1}，

顯然，xj(0)=lj，xj(1)=uj，xq(0)=lq，xq(1)=uq.

定理1對(duì)于任意的x ∈H ?H0，有

(a) 對(duì)任意xj∈[lj，uj]，j ∈{1，2，...，n}，有

(b) 對(duì)任意j ∈{1，2，...，n}，q ∈{1，2，...，n}，jq，有

證(a) 在每一個(gè)區(qū)間[lj，uj]，j ∈{1，2，...，n}對(duì)單變量函數(shù)φ(xj) =進(jìn)行線性縮放可得φ(xj)的上下界逼近函數(shù)，進(jìn)而

(b) 把(xj+xq)和(xj-xq)分別看成一個(gè)單變量，則(xj+xq)2和(xj-xq)2分別是在區(qū)間[lj+lq，uj+uq]和[lj-uq，uj-lq]上關(guān)于(xj+xq)以及(xj-xq)的凸函數(shù)，則由(a)

結(jié)合式(2.1)-(2.4)，

由(2.5)和(2.6)式可知，當(dāng)|lj-uj|→0時(shí)，

因?yàn)?/p>

根據(jù)(2.9)及(2.12)式得，當(dāng)‖l-u‖ →0時(shí)，有?(xj，xq) →0.和以上證明方法類似，當(dāng)‖lu‖→0時(shí)，我們可以得到證畢.

對(duì)于任意xj∈[lj，uj]，j ∈{1，...，n}，我們得到(x)，i=0，1，...，M.即

通過(guò)以上討論，我們得到原問(wèn)題(QCQP)在子矩形H上的線性松弛規(guī)劃問(wèn)題如下:

定理2對(duì)于任意的x ∈H =[l，u]?H0，有

(a)fi(x)≥(x)，i=0，1，...，M;

(b) 當(dāng)‖l-u‖→0時(shí)，fi(x)-(x)→0，i=0，1，...，M.

證(a) 由(2.13)式我們很容易得到fi(x)≥(x)，i=0，1，...，M;

由定理2可以知道，對(duì)每一個(gè)子矩形H來(lái)講，線性松弛規(guī)劃問(wèn)題(LRP)的目標(biāo)函數(shù)和約束條件函數(shù)是小于等于原問(wèn)題(QCQP)的目標(biāo)函數(shù)和約束條件函數(shù)的，也就是說(shuō)定理2保證了問(wèn)題(LRP)的最優(yōu)值為原問(wèn)題(QCQP)能夠提供可靠的下界，當(dāng)‖l-u‖ →0時(shí)，線性松弛規(guī)劃問(wèn)題(LRP)限逼近原問(wèn)題(QCQP)，這說(shuō)明了算法是全局收斂的.

3.縮減技術(shù)

為了加快算法的收斂速度和計(jì)算速度，在這一部分，基于文[17-18]，提出適用于本算法的區(qū)域縮減技術(shù).當(dāng)算法迭代到第k步時(shí)我們需要判斷在矩形區(qū)域H上原問(wèn)題(QCQP)是否存在全局最優(yōu)解.此處縮減技術(shù)的前提是未刪掉在矩形區(qū)域H 上原問(wèn)題(QCQP)的全局最優(yōu)解，進(jìn)而對(duì)區(qū)域進(jìn)行縮減，具體見(jiàn)定理3和定理4.

不失一般性，假設(shè)線性松弛規(guī)劃問(wèn)題LRP中的每一個(gè)線性函數(shù)φi(x)，i=0，1，...，M，M+1，...，M +m，可以表示為

設(shè)UBk是算法迭代到第k步原問(wèn)題(QCQP)當(dāng)前已知的最好上界，并令

定理3對(duì)于任何的子矩形Hk?H ?H0且Hk= [lk，uk].如果存在s ∈{1，2，...，n}使得則在子矩形Hk上原問(wèn)題(QCQP)沒(méi)有全局最優(yōu)解; 否則，如果存在s ∈{1，2，...，n}使得當(dāng)且則原問(wèn)題(QCQP)在子矩形上沒(méi)有全局最優(yōu)解; 當(dāng)且則原問(wèn)題(QCQP)在子矩形上沒(méi)有全局最優(yōu)解.其中，

證如果存在s ∈{1，2，...，n}使得則

即

因此，原問(wèn)題(QCQP)在Hk上沒(méi)有全局最優(yōu)解.接下來(lái)記x的第s個(gè)分量為xs，因?yàn)樗杂挟?dāng)時(shí)，對(duì)于一切的x ∈Hk1，由的定義和上面的不等式，有

也就是

因此，對(duì)于任意x ∈Hk1，線性松弛函數(shù)φ0(x)要大于原問(wèn)題(QCQP)的上界UBk，所以在Hk1上不存在原問(wèn)題(QCQP)的全局最優(yōu)解.

類似地，對(duì)于所有的x ∈Hk2，存在s ∈{1，2，...，n}使得＜0且時(shí)，在Hk2這個(gè)子矩形上也不存在原問(wèn)題(QCQP)的全局最優(yōu)解.證畢.

定理4對(duì)于任何的子矩形Hk?H0且Hk= [lk，uk].如果1，...，M，M+1，...，M+m，則原問(wèn)題在Hk上沒(méi)有全局最優(yōu)解.否則，若存在s ∈{1，2，...，n}使得且...，M，M+1，...，M+m，則原問(wèn)題在子矩形Hk3上沒(méi)有全局最優(yōu)解; 若存在s ∈{1，2，...，n} 使得＜0且則原問(wèn)題在子矩形Hk4上沒(méi)有全局最優(yōu)解.其中，

證使用與證明定理3類似的方法，我們可以得到此定理成立.

由定理3和定理4，采用縮減技術(shù)刪掉不含有原問(wèn)題(QCQP)全局最優(yōu)解的區(qū)域.令H =(Hj)n×1是H0任一子矩形，其中Hj=[lj，uj].得到縮減規(guī)則如下:

4.分支定界算法及其收斂性分析

為了得到原問(wèn)題(QCQP)的全局最優(yōu)解，提出了參數(shù)化線性松弛分支定界算法.在矩形H ?H0被剖分后的子集上求解對(duì)應(yīng)的線性松弛規(guī)劃問(wèn)題.分支過(guò)程中，需要依據(jù)一定的剖分規(guī)則將初始超矩形H0分成兩個(gè)新的子矩形.本文所采用的是標(biāo)準(zhǔn)矩形二分方法.考慮任一通過(guò)H ={x ∈Rn|lj≤xj≤uj，j =1，...，n}?H0所確定的子節(jié)點(diǎn)問(wèn)題.分支規(guī)則如下所示:

通過(guò)以上分支規(guī)則，將矩形區(qū)域H剖分成了兩個(gè)子矩形H1和H2.

為了方便起見(jiàn)，我們把縮減后產(chǎn)生新的矩形區(qū)域仍然記為Hk，它是初始超矩形區(qū)域的子集.記LBk是線性松弛規(guī)劃問(wèn)題(LRP)在子矩形Hk上的最優(yōu)值，xk= x(Hk)是相對(duì)應(yīng)的最優(yōu)解.結(jié)合前面所提到的線性松弛規(guī)劃問(wèn)題，區(qū)域縮減技術(shù)以及分支規(guī)則，為求解問(wèn)題(QCQP)提出分支定界算法，步驟如下:

步0(初始化) 設(shè)置誤差精度?＞0，初始迭代次數(shù)k =0，Q表示剪支后所有矩形的集合，初始的可行集為W =?，初始上界UB0=+∞.

在初始矩形H0上求解線性規(guī)劃問(wèn)題LRP(H0)，如果不可行，則原問(wèn)題(QCQP)無(wú)解; 否則將求得的最優(yōu)值和最優(yōu)解分別記為L(zhǎng)B0和x0.如果x0對(duì)(QCQP)可行，置可行集為W =W ∪{x0}，則初始上界UB0=f0(x0)，Q=Q ∪{H0}，置k =1，轉(zhuǎn)步1;

步1(終止準(zhǔn)則) 如果UBk-LBk＜?，則迭代終止，xk是問(wèn)題(QCQP)的?-全局最優(yōu)解.否則，轉(zhuǎn)步2;

步2(矩形區(qū)域的分支) 在Q中選擇出當(dāng)前最小下界所對(duì)應(yīng)的矩形Hk，通過(guò)本文所提出的分支規(guī)則將矩形區(qū)域Hk剖分為兩個(gè)新的子矩形Hk1和Hk2，用表示新剖分的矩形集合;

步3(矩形區(qū)域的縮減) 對(duì)每一個(gè)子矩形Hkt∈，t = 0，1，2，利用本文所給出的區(qū)域縮減技術(shù)分別對(duì)子矩形進(jìn)行縮減;

步4(剪支規(guī)則) 令Q=Q{Hk:LBk-UBk＞ε，Hk∈Q}，轉(zhuǎn)步5;

步5(更新上界) 如果W = ?，那么UBk保持不變; 如果W?，則更新上界，UBk=min{f0(x):x ∈W}，當(dāng)前最好的可行點(diǎn)為x*:=arg minx∈Wf0(x);

步6(更新下界) 如果Q = ?，那么LBk保持不變; 如果Q?，那么LBk= min{LRP :Hk∈Q}，置k =k+1，返回步1繼續(xù)執(zhí)行.

為了證明本文的分支定界算法是全局收斂的，故給出下面的定理5，以保證當(dāng)‖l-u‖→0時(shí)線性松弛規(guī)劃問(wèn)題(LRP)地逼近于原問(wèn)題(QCQP).

定理5假設(shè)(QCQP)問(wèn)題的可行域是非空的，且矩形的剖分是耗盡的，則以下兩個(gè)結(jié)論成立:

(a)如果算法迭代在有限步終止，則(QCQP)問(wèn)題的全局最優(yōu)解將在算法終止時(shí)得到;

(b)如果算法迭代在有限步不能終止，并且產(chǎn)生無(wú)窮多個(gè)可行點(diǎn)的序列{xk}，則{xk}的任何一個(gè)聚點(diǎn)x*都是問(wèn)題(QCQP)的全局最優(yōu)解.

證(a)如果算法迭代在有限步終止，那么我們假設(shè)算法是在第k次迭代終止，k ≥0.根據(jù)算法的步1得到UBk-LBk≤?，表示原問(wèn)題(QCQP)存在可行解并設(shè)為x*，使得UBk=f0(x*)，同時(shí)有

假設(shè)v是原問(wèn)題(QCQP)的全局最優(yōu)值，由下界的計(jì)算過(guò)程表明

因?yàn)閤*是原問(wèn)題(QCQP)的可行解，有

聯(lián)立式(4.1)-(4.3)得

所以，x*是問(wèn)題(QCQP)的?-全局最優(yōu)解.

(b) 如果算法的迭代是無(wú)限的，則通過(guò)求解一系列問(wèn)題(LRP)可產(chǎn)生原問(wèn)題的可行解序列{xk}∈H0.根據(jù)分支定界算法的結(jié)構(gòu)，隨著可行域的不斷剖分加細(xì)我們有

因?yàn)橄陆缧蛄衶LBk=xk)}是單調(diào)不減且有上界，且上界序列{UBk= f0(xk)}是單調(diào)不增且有下界，故原問(wèn)題的上下界都是收斂的.對(duì)式(4.5)兩邊取極限可得

不失一般性，假設(shè)超矩形序列{Hk= [lk，uk]}滿足xk∈Hk以及Hk+1?Hk.在算法進(jìn)行迭代過(guò)程中，最終矩形的剖分是耗盡的，即根據(jù)函數(shù)f0(x)的連續(xù)性，我們有

所以，序列{xk}的每一個(gè)聚點(diǎn)x*都是問(wèn)題(QCQP)的全局最優(yōu)解.

5.數(shù)值實(shí)驗(yàn)

給出以下幾個(gè)算例證明本文算法的有效性.本文算法中所有的線性規(guī)劃問(wèn)題均選用對(duì)偶單純形法求解，算法所有測(cè)試過(guò)程均用MATLAB9.2.0.538062 (R2017a)在Inter(R)Core(TM)i5-8250U，CPU@1.60GHz，8GB內(nèi)存，64位Windows10操作系統(tǒng)的計(jì)算機(jī)上運(yùn)行.

算例1[17-18]:

算例2[17-18]:

算例3[17-18]:

算例4[17]:

算例5[17]:

算例6[17]:

算例7[21]:

其中Q0∈Rn×n的每個(gè)元素在區(qū)間[0，1]隨機(jī)產(chǎn)生，Qi∈Rn×n(i = 1，2，...，m)的每個(gè)元素在區(qū)間[-1，0]隨機(jī)產(chǎn)生; d0∈Rn的每個(gè)元素在區(qū)間[0，1]隨機(jī)產(chǎn)生; di∈Rn(i = 1，2，...，m)的每個(gè)元素在區(qū)間[-1，0]隨機(jī)產(chǎn)生; 每一個(gè)bi∈R(i=1，2，...，m)在區(qū)間[-300，-90]產(chǎn)生.

算例8[17-18]:

表5.1 算例1-6利用本文算法產(chǎn)生的數(shù)值結(jié)果

表5.2 算例7 利用本文算法產(chǎn)生的數(shù)值結(jié)果

表5.3 算例8 利用本文算法產(chǎn)生的數(shù)值結(jié)果

為方便起見(jiàn)，表5.1-5.3 的具體符號(hào)表示如下: E: 算例編號(hào); Refs: 文獻(xiàn); Matrix ρ: 對(duì)稱參數(shù)矩陣; f0(x*): 最優(yōu)值; x*: 最優(yōu)解; m: 二次約束的個(gè)數(shù); n: 目標(biāo)函數(shù)的維數(shù); Iters: 平均迭代次數(shù); Time(s): 平均運(yùn)行時(shí)間，算法運(yùn)行過(guò)程中的精度為10-6.算例1-6的計(jì)算結(jié)果如表5.1所示，利用文[17-18]和本算法進(jìn)行比較，從總體上看本文要優(yōu)于文[17-18]的計(jì)算效果，而從算例3和算例5的結(jié)果來(lái)看，本文計(jì)算時(shí)間要比文[18]長(zhǎng)，但比文[17]用時(shí)短，證明了我們提出的算法是可行有效的.

為了進(jìn)一步證明我們的算法能夠解決帶有多個(gè)二次約束的二次規(guī)劃問(wèn)題，對(duì)算例7 進(jìn)行了如表5.2 結(jié)果所示的中高維度的偽隨機(jī)試驗(yàn)，在表5.2 中，我們把參數(shù)矩陣ρ ∈Rn×n固定成ρ = (0)n×n.當(dāng)約束條件個(gè)數(shù)固定，維數(shù)逐漸增大的情況下，迭代次數(shù)沒(méi)有明顯的增加，且運(yùn)行時(shí)間較少; 當(dāng)維數(shù)固定，二次約束的個(gè)數(shù)不斷增加時(shí)，迭代次數(shù)增大且運(yùn)行時(shí)間越長(zhǎng).表5.3 中，列出了我們的算法和文[17-18]中算法的數(shù)值結(jié)果，參數(shù)矩陣ρ的元素是全為0的對(duì)稱矩陣，通過(guò)比較數(shù)值結(jié)果，不管從迭代次數(shù)還是從CPU運(yùn)行時(shí)間，都可以看出我們的算法是優(yōu)于文[17-18]的，隨著維數(shù)的增加，運(yùn)行時(shí)間在增加，但迭代次數(shù)只有1次，說(shuō)明本算法對(duì)算例8的維數(shù)大小不是很敏感.數(shù)值結(jié)果表明我們的算法是有效的.

6.結(jié)論

針對(duì)一般的二次約束二次規(guī)劃問(wèn)題，本文基于參數(shù)化方法求解關(guān)于二次項(xiàng)以及雙變量的線性松弛問(wèn)題.為了加快算法的收斂速度，利用參數(shù)化線性松弛分支定界算法，以及結(jié)合區(qū)域縮減技術(shù)，解決了二次約束二次規(guī)劃問(wèn)題.通過(guò)剖分矩形區(qū)域并解決參數(shù)化線性子問(wèn)題，提出的算法最終收斂到原問(wèn)題(QCQP)的全局最優(yōu)解，在第五部分?jǐn)?shù)值實(shí)驗(yàn)中，驗(yàn)證了在求解二次約束二次規(guī)劃問(wèn)題時(shí)本文算法是有效可行的.