一類復(fù)矩陣變量二次規(guī)劃問題的快速算法

張宋傳，鄒長忠

（1.閩江學(xué)院數(shù)學(xué)系，福建福州350108；2.福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建福州350108）

一類復(fù)矩陣變量二次規(guī)劃問題的快速算法

張宋傳1，鄒長忠2

（1.閩江學(xué)院數(shù)學(xué)系，福建福州350108；2.福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建福州350108）

針對一類帶線性等式約束的復(fù)矩陣優(yōu)化變量的二次規(guī)劃問題，提出一類快速有效的算法，該算法擴(kuò)展了現(xiàn)有復(fù)值共軛梯度投影算法，繼承了原算法的收斂性結(jié)果，同時又避免了原算法處理矩陣優(yōu)化變量時的向量化操作。數(shù)值實驗表明了新算法的可行性和有效性，較傳統(tǒng)凸優(yōu)化方法有更快的收斂速度。

二次規(guī)劃；共軛梯度投影；復(fù)矩陣變量；線性等式約束

考慮線性等式約束的復(fù)矩陣變量二次規(guī)劃問題：

其中‖·‖F(xiàn)表示Frobenius范數(shù)，C∈Cp×n，D∈Cp×m，B∈Cq×m，A∈Cq×n，另假設(shè)C為列滿秩的且問題（1）有全局最優(yōu)解。

共軛梯度法是求解無約束優(yōu)化問題的重要方法，將共軛梯度算法推廣到約束優(yōu)化問題的求解上是一個十分自然的且很有意義的方向［1-2］。梁玉梅結(jié)合Rosen梯度投影法與共軛梯度法［3］，提出一類共軛梯度投影算法求解優(yōu)化變量為向量情形的帶線性等式約束的二次規(guī)劃問題。

問題（1）的目標(biāo)函數(shù)為復(fù)變量實值函數(shù)，不滿足柯西-黎曼條件［4］，通過拆分復(fù)值數(shù)據(jù)，將問題轉(zhuǎn)化為等價的實變量優(yōu)化問題求解是較為普遍的做法。不足在于轉(zhuǎn)化過程繁瑣，轉(zhuǎn)化后的實變量優(yōu)化問題成倍地擴(kuò)大了原問題的規(guī)模，大大增加了問題求解的復(fù)雜性。CR微分［5］是一種適用范圍更廣的復(fù)變函數(shù)微分理論，近年來被廣泛應(yīng)用到復(fù)變量優(yōu)化領(lǐng)域［3-5］。基于CR微分，ZHANG S［6］將梁玉梅的算法進(jìn)一步推廣到復(fù)值優(yōu)化變量情形，新算法稱為復(fù)值共軛梯度投影算法。

采用復(fù)值共軛梯度投影算法求解問題（1），需要將問題（1）中的矩陣向量化，該方法最大不足在于向量化后導(dǎo)致數(shù)據(jù)結(jié)構(gòu)破壞與規(guī)模的擴(kuò)大。本文提出復(fù)值共軛梯度投影算法一類擴(kuò)展，適用于問題（1）的求解，同時又避免了矩陣向量化過程。與傳統(tǒng)優(yōu)化方法相比，擴(kuò)展后的復(fù)值共軛梯度投影算法在求解速度上優(yōu)勢明顯。

1　預(yù)備知識

下面給出一些運(yùn)算的定義及其相關(guān)性質(zhì)。

定義1［7］設(shè)矩E=（eij）∈Cm×n且M∈Cp×q，稱如下mp×nq階矩陣

為E和M的Kronecker積，記為E?M。

命題1設(shè)以下矩陣運(yùn)算可以進(jìn)行，則

（1）（E?M）±（F?M）=（E±F）?M

（2）（E?F）（M?N）=（EM）?（FN）；

（3）（E?F）H=EH?FH；

（4）（E?F）+=E+?F+。

其中E+表示復(fù)矩E的Moore-Penrose逆，即滿足以下四個Penrose方程：

（ⅰ）E=EE+E；（ⅱ）（EE+）H=EE+；

（ⅲ）E+=E+EE+；（ⅳ）（E+E）H=E+E.

證明：（1）～（3）直接由Kronecker積的定義可以驗證。

（4）因為

（ⅰ）（E?F）（E+?F+）（E?F）

=EE+E?FF+F=E?F

（ⅱ）（（E?F）（E+?F+））H

=（EE+?FF+）H

=（EE+）H?（FF+）H

=EE+?FF+

=（E?F）（E+?F+）；

（ⅲ）（E+?F+）（E?F）（E+?F+）

=E+EE+?F+FF+

=E+?F+；

（ⅳ）（（E?F）（E?F））H

=（E+E?F+F）H

=（E+E）H?（F+F）H

=E+E?F+F

=（E+?F+）（E?F），

即證得E+?F+是（E?F）的Moore-Penrose逆。

定義2設(shè)矩陣E∈Cm×n，映射ψ定義為

ψ（E，p）=E?Ip

其中p為正整數(shù)。

定義3矩陣E∈Cm×n的向量化

vec（E）=［e11，…，e1n，…，em1，…，emn］T。

定義4向量c∈Cnm重組為m列矩陣

命題2任一矩陣E∈Cm×n，F(xiàn)∈Cn×q有

（1）vec（EF）=ψ（E，q）vec（F）

（2）reshape（ψ（E，q）vec（F），q）=EF。

證明：由上述運(yùn)算的定義直接得到，此處略。

2　算法導(dǎo)出

問題（1）的向量化形式為

其中d=vec（D），b=vec（B）。假設(shè)z˙是問題（2）的最優(yōu)解，則是問題（1）的最優(yōu)解。由CR微分［5］可知，問題（2）的目標(biāo)函數(shù)g（z）的復(fù)梯度為：

簡化起見，▽g（zk）記為▽gk。令投影矩陣=Imn-ψ（A，m）+ψ（A，m）。復(fù)值共軛梯度投影算法［6］求解問題（2）的框架如下：

算法1

輸入：初始可行點z0=ψ（A，m）+b。

初始化：容忍因子ε＞0，最大迭代次類K，令k=1，d0=l0=-▽g0。

步驟1：計算

步驟2：計算lk-=-▽gk，如果‖lk‖2≤ε，則輸出zk；否則，計算

再令k=k+1，轉(zhuǎn)步驟1。

定理1［6］如果φ（C，m）Hφ（C，m）是Hermitian正定陣，則算法Ⅰ在mn步內(nèi)收斂到問題（2）的最優(yōu)解。

算法1求解問題（1）不足在于向量化后原有數(shù)據(jù)結(jié)構(gòu)破壞與規(guī)模的擴(kuò)大。本節(jié)提出復(fù)值共軛梯度投影算法一類擴(kuò)展，適用于問題（1）的求解，同時又避免了算法中矩陣的向量化過程。

由映射ψ的定義及Kronecker積的性質(zhì)，有

其中Q=CHC，P=In-A+A因此，算法Ⅰ中

其中，

依據(jù)上述結(jié)果，易得算法Ⅰ的矩陣化形式，稱為算法Ⅱ。該算法是筆值共軛梯度投影算法的一類擴(kuò)展，避免了原算法Ⅰ中矩陣的向量化操作，同時保留了復(fù)值共軛梯度投影算法的收斂性結(jié)果。其求解問題（1）的框架如下：

算法Ⅱ

輸入：初始可行點Z0=A+B。

初始化：容忍因子ε＞0，最大迭代次數(shù)K，令k=1，D0=L0=-P▽G0。

步驟1：計算

步驟2：計算Lk=-P▽Gk，如果‖Lk‖F(xiàn)≤ε，則輸出Zk；否則，計算

再令k=k+1，轉(zhuǎn)步驟1。

定理2如果Q是Hermitian正定陣，則算法Ⅱ在mn步內(nèi)收斂到問題（1）的最優(yōu)解。

3　數(shù)值實驗

實驗在聯(lián)想（CPU2.1GHZ，內(nèi)存2GB）的個人計算機(jī)上進(jìn)行的，程序用MATLAB語言編寫的，并在MATLAB7.6.0的環(huán)境下執(zhí)行。

問題（1）中C∈Cp×n，D∈Cp×m，B∈Cq×m，A∈Cq×n均隨機(jī)生成，且各元素獨(dú)立同分布于均值為0，標(biāo)準(zhǔn)差為1的正態(tài)分布。實驗中，選取凸規(guī)劃軟件包CVX［8］與算法Ⅱ作比較，CVX采用默認(rèn)的參數(shù)設(shè)置，算法Ⅱ中A+采用qrginv函數(shù)［9］，容忍度ε=10-4。最大迭代數(shù)K=mn。不同規(guī)模下兩算法的運(yùn)行時間（單位：稱）列在表1中，此外，該表還包括了算法Ⅱ求解問題（1）的迭代次數(shù)。可以看出，算法Ⅱ在收斂速度上優(yōu)于傳統(tǒng)凸優(yōu)化方法，當(dāng)問題規(guī)模擴(kuò)大時，CVX因內(nèi)存溢出，無法獲得問題的最優(yōu)解。

表1　兩類算法運(yùn)行時間（秒）的比較Tab.1 Comparison of running times of two algorithms

［1］景書杰，趙海燕.等式約束優(yōu)化問題的一類混合共軛梯度投影算法［J］.安徽大學(xué)學(xué)報（自然科學(xué)版），2013，37（4）：10-13.

［2］Zhang B，Zhu Z，Li S.A modified spectral conjugate gradient projection algorithm for total variation image restoration［J］. Applied Mathematics Letters，2014，27（1）：26-35.

［3］梁玉梅，簡金寶.線性約束最優(yōu)化的一個共軛投影梯度法［J］.運(yùn)籌與管理，2003，12（2）：31-35.

［4］鐘玉泉.復(fù)變函數(shù)論［M］.3版.北京：高等教育，2006：54-57.

［5］Kreutz D K.The complex gradient operator and the CR-calculus［EB/OL］.（2016-01-10）［2016-02-14］http：//dsp.ucsd.edu/～kreutz/PEI-05%20Support%20Files/complex_derivatives. pdf，2016-01-10.

［6］Zhang S，Xia Y.Two fast complex-valued algorithms for solving complex quadratic programming problems［J］.IEEE transactions on cybernetics，2015，PP（99）：1-11.

［7］周杰.矩陣分析及應(yīng)用［M］.成都：四川大學(xué)出版社，2008：40-41.

［8］Grant M，Boyd S.CVX：matlab software for disciplined convex programming［EB/OL］.（2015-12-10）［2016-02-14］.http：// cvxr.com/cvx/，2015-12-10.

［9］Katsikis V N，Pappas D，Petralias A.An improved method for the computation of the Moore–Penrose inversematrix［J］.Applied Mathematics&Computation，2011，217（23）：9828-9834.

（責(zé)任編輯：葉麗娜）

A Fast Algorithm for Solving a Class of Quadratic Programming Problem with Complex-Valued Matrix Optimization Variables

ZHANG Songchuan1，ZOU Changzhong2
（1.Departmentof Mathematics，Minjiang University，F(xiàn)uzhou，F(xiàn)ujian 350108；2.School of Mathematics and Computer Science，F(xiàn)uzhou University，F(xiàn)uzhou，F(xiàn)ujian 350108）

A fast algorithm is presented for solving a class of linear equality constraint quadratic programming problem with complexvalued matrix optimization variables．The proposed algorithm，which can be viewed as an extension of the existing complex-valued conjugate gradient projection algorithm，retains the convergence resultof the original algorithm，and also avoids vectorizing procedure for solving programming problem with matrix optimization variables．Numerical experiments show that the proposed algorithm is feasible and effective and is faster than the traditional convex programmingmethod．

Quadratic programming problem；Conjugate gradient projection；Complex-valued matrix variables；Linear equality constraint

O221.2

A

1674-2109（2016）06-0057-04

2016-03-18

福建省中青年教師教育科研項目（NO.JA15436）；福建省中青年教師教育科研項目（NO.JA15078）。

張宋傳（1977-），男，漢族，講師，主要從事復(fù)值優(yōu)化算法的研究。