劉琬純，何洪津

(杭州電子科技大學理學院，浙江 杭州 310018)

0 引 言

二次規(guī)劃(Quadratic Programs, QP)是一類經(jīng)典的數(shù)學優(yōu)化模型，在工程、管理和經(jīng)濟等領域有著廣泛的應用。在過去的幾十年中，二次規(guī)劃，尤其是凸二次規(guī)劃的相關理論和算法得到了較完善的發(fā)展，但大規(guī)模二次規(guī)劃的高效算法設計仍值得深入研究。近十年來，交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)在壓縮感知、機器學習和圖像處理等領域取得了諸多成功應用，在各領域掀起了交替方向乘子法的研究熱潮。文獻[1]給出了求解二次規(guī)劃問題的交替方向乘子法。隨后，有學者分析了交替方向乘子法求解二次規(guī)劃時具有線性收斂速率[2]；文獻[3-4]進一步分析了交替方向乘子法求解嚴格凸二次規(guī)劃時的最優(yōu)化參數(shù)選擇策略。不難發(fā)現(xiàn)，按照文獻[1]提出的交替方向乘子法框架，其線性等式約束的子問題可歸結為一個增大規(guī)模的線性方程組。當線性方程組系數(shù)矩陣無特殊結構時，文獻[1]中的處理方式降低了交替方向乘子法的執(zhí)行效率。另外，現(xiàn)有交替方向乘子法解二次規(guī)劃的相關文獻主要討論僅含等式和簡單約束，或僅含不等式約束這兩種情形。然而，現(xiàn)實生活中的案例可能同時具有等式、不等式和簡單凸集約束條件。因此，本文針對一般的混合約束凸二次規(guī)劃問題，設計新的交替方向乘子法，使得其子問題保持與原問題同規(guī)模，并且具有封閉解，從而達到提升計算效率的目的。

1 問題描述

考慮二次規(guī)劃問題：

s.t.Ax=b,Dx≤d,x∈

(1)

式中，P∈n×n為對稱半正定矩陣，q∈n,A∈m×n,b∈m,D∈r×n,d∈r,?n為簡單凸集。這里簡單凸集指投影到集合是易于計算的，其中投影由如下定義給出。

定義1對于給定的向量v∈n,v到凸集的投影由下式給出

本文重點考慮凸二次規(guī)劃問題的求解，因此假設凸二次規(guī)劃問題(1)的解集非空。

2 問題轉化和交替方向乘子法

對于可分離凸規(guī)劃模型：

minf(u)+g(v)

(2)

其中β>0為罰參數(shù)。給定迭代點(vk,λk)，由文獻[1]可得求解(2)的交替方向乘子法迭代格式為：

(3)

(4)

注意到式(4)中x-子問題是一個約束優(yōu)化問題，可采用文獻[1]給出的方法尋找(xk+1,γ)滿足如下線性方程組：

(5)

顯然，方程組(5)是一個增大規(guī)模的子問題，即由原問題的n維變成了(m+n)維。在這種情況下，即使系數(shù)矩陣是一個正定矩陣，理論上有封閉解，但隨著A的規(guī)模增大，子問題(5)的求解代價會迅速增加。這一缺陷促使我們尋找方法降低交替方向乘子法子問題求解難度。另外，若進一步考慮凸二次規(guī)劃(1)的一般形式，文獻[1]的迭代格式會變得更復雜。

考慮混合約束凸二次規(guī)劃問題(1)，引入松弛變量y∈將不等式Dx≤d轉化為Dx+y=d。此時，令模型(2)中的且

基于上述討論，不難得到交替方向乘子法求解問題(1)的迭代格式如下：

(6)

根據(jù)文獻[5]中的定理4.1可知，由迭代格式(6)所產(chǎn)生的序列{(vk,xk,λk)}收斂到問題(1)的一個解點。特別地，已有相關文獻對二次規(guī)劃問題的交替方向乘子法給出了局部線性收斂速率的估計，具體見文獻[2,6,7]。因篇幅限制，本文不再贅述收斂性證明和收斂速度的估計。

3 數(shù)值實驗

為了進一步驗證本文的交替方向乘子法(記為NADMM)在求解混合二次規(guī)劃模型的有效性，分別采用3種方法進行實驗，將NADMM、MATLAB優(yōu)化工具包中二次規(guī)劃問題的求解包quadprog(記為QUADP)和文獻[1]中的交替方向乘子法(4)(記為OADMM)進行比較。

實驗中QUADP采用默認設置，其精度為10-6，算法為內點法。為了保證算法的公平性，NADMM和OADMM算法的終止條件均設為

最大的迭代次數(shù)為1 000。另外，根據(jù)文獻[5]的分析，罰參數(shù)β可采用自適應的方式提升交替方向乘子法的計算效率。因此，本文按如下方式調節(jié)βk+1：

(7)

其中β0=10。所有數(shù)值實驗運行環(huán)境為Windows10操作系統(tǒng)下的MATLAB R2015b，電腦配置為Intel Corei5-4210U CPU和4GB內存。

例1考慮僅含等式和箱型約束的二次規(guī)劃問題(1)，即

D=0,d=0,={x∈n|0≤x≤1}

實驗中，取P=QTQ，其中Q=rand(l,n)，l取100。為了得證問題的解集非空，先隨機生成x*使其元素服從均勻分布即x*=rand(n,1)，再分別令q=-Px*和b=Ax*,其中A=rand(m,n)。

例2考慮混合約束二次規(guī)劃問題(1)，且

x=z,={z∈n|0≤z≤1}

實驗中，取P=QTQ，其中Q=rand(l,n)，l取100。為了得證問題的解集非空，先隨機生成x*,y*使其元素服從均勻分布即x*=rand(n,1),y*=rand(r,1)，再分別令q=-Px*，b=Ax*和d=Dx*+y*,其中A=rand(m,n),D=rand(r,n)。

由于例1和例2都是隨機生成的二次規(guī)劃問題，本文針對每一規(guī)模算例都進行10次測試，目的是為了觀察算法對本類問題的穩(wěn)定性。從算法的平均計算時間Time、平均迭代次數(shù)Iter和平均目標函數(shù)值Obj等3個方面進行比較，計算結果如表1和表2所示。

表1 3種算法求解例1的結果

表2 3種算法求解例2的數(shù)值結果

從表1可看出，在迭代次數(shù)方面，本文提出的NADMM算法在求解例1類型的二次規(guī)劃問題上比文獻[1]的OADMM算法更多，但NADMM的計算時間更少。而從表2可看出，對于一般混合約束凸二次規(guī)劃問題(1)NADMM在計算時間和迭代次數(shù)上都要優(yōu)于文獻[1]中的處理方式。另外，無論是NADMM還是OADMM，都比MATLAB中的quadprog求解函數(shù)更高效，這也說明交替方向乘子法在二次規(guī)劃求解中的優(yōu)勢。從表1和表2的結果可以發(fā)現(xiàn)， NADMM比其它算法需要的計算時間更短。

為了進一步觀測3種方法的穩(wěn)定性，針對例1和例2其中一種情形，對3種方法進行10次隨機測試，比較其運行時間，結果如圖1所示。

圖1 3種算法求解10組隨機問題的計算時間箱線圖

從圖1可以看出，本文的NADMM較另外2種算法有較好的穩(wěn)定性。

4 結束語

針對一般混合約束的凸二次規(guī)劃模型，本文提出一種改進的交替方向乘子法迭代格式，有效克服了文獻[1]需求解一個增大規(guī)模的線性方程組問題的缺點，保持了每個子問題都具有封閉解形式的優(yōu)勢，同時，改進算法的計算時間達到最短。下一步將對非凸二次規(guī)劃的交替方向乘子法設計展開進一步研究和探討。