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

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

1.引言

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

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

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

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

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

為了求解原問題(QCQP)，本文采用一種新的參數(shù)化線性松弛技術(shù)得到原問題和其子問題的下界函數(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是一個對稱參數(shù)矩陣且ρjq∈{0，1}.對于任何的x ∈H，且j ∈{1，2，...，n}，q ∈{1，2，...，n}，jq，ρjq∈{0，1} 給出以下定義:

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

對于任何的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對于任意的x ∈H ?H0，有

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

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

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

(b) 把(xj+xq)和(xj-xq)分別看成一個單變量，則(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時，

因為

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

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

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

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

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

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

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

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

3.縮減技術(shù)

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

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

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

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

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

即

因此，原問題(QCQP)在Hk上沒有全局最優(yōu)解.接下來記x的第s個分量為xs，因為所以有當(dāng)時，對于一切的x ∈Hk1，由的定義和上面的不等式，有

也就是

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

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

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

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

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

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

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

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

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

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

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

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

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

步3(矩形區(qū)域的縮減) 對每一個子矩形Hkt∈，t = 0，1，2，利用本文所給出的區(qū)域縮減技術(shù)分別對子矩形進(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)前最好的可行點為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時線性松弛規(guī)劃問題(LRP)地逼近于原問題(QCQP).

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

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

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

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

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

因為x*是原問題(QCQP)的可行解，有

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

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

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

因為下界序列{LBk=xk)}是單調(diào)不減且有上界，且上界序列{UBk= f0(xk)}是單調(diào)不增且有下界，故原問題的上下界都是收斂的.對式(4.5)兩邊取極限可得

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

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

5.數(shù)值實驗

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

算例1[17-18]:

算例2[17-18]:

算例3[17-18]:

算例4[17]:

算例5[17]:

算例6[17]:

算例7[21]:

其中Q0∈Rn×n的每個元素在區(qū)間[0，1]隨機產(chǎn)生，Qi∈Rn×n(i = 1，2，...，m)的每個元素在區(qū)間[-1，0]隨機產(chǎn)生; d0∈Rn的每個元素在區(qū)間[0，1]隨機產(chǎn)生; di∈Rn(i = 1，2，...，m)的每個元素在區(qū)間[-1，0]隨機產(chǎn)生; 每一個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é)果

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

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

6.結(jié)論

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