一类复矩阵变量二次规划问题的快速算法

张宋传，邹长忠

（1.闽江学院数学系，福建福州350108；2.福州大学数学与计算机科学学院，福建福州350108）

一类复矩阵变量二次规划问题的快速算法

张宋传1，邹长忠2

（1.闽江学院数学系，福建福州350108；2.福州大学数学与计算机科学学院，福建福州350108）

针对一类带线性等式约束的复矩阵优化变量的二次规划问题，提出一类快速有效的算法，该算法扩展了现有复值共轭梯度投影算法，继承了原算法的收敛性结果，同时又避免了原算法处理矩阵优化变量时的向量化操作。数值实验表明了新算法的可行性和有效性，较传统凸优化方法有更快的收敛速度。

二次规划；共轭梯度投影；复矩阵变量；线性等式约束

考虑线性等式约束的复矩阵变量二次规划问题：

其中‖·‖F表示Frobenius范数，C∈Cp×n，D∈Cp×m，B∈Cq×m，A∈Cq×n，另假设C为列满秩的且问题（1）有全局最优解。

共轭梯度法是求解无约束优化问题的重要方法，将共轭梯度算法推广到约束优化问题的求解上是一个十分自然的且很有意义的方向［1-2］。梁玉梅结合Rosen梯度投影法与共轭梯度法［3］，提出一类共轭梯度投影算法求解优化变量为向量情形的带线性等式约束的二次规划问题。

问题（1）的目标函数为复变量实值函数，不满足柯西-黎曼条件［4］，通过拆分复值数据，将问题转化为等价的实变量优化问题求解是较为普遍的做法。不足在于转化过程繁琐，转化后的实变量优化问题成倍地扩大了原问题的规模，大大增加了问题求解的复杂性。CR微分［5］是一种适用范围更广的复变函数微分理论，近年来被广泛应用到复变量优化领域［3-5］。基于CR微分，ZHANG S［6］将梁玉梅的算法进一步推广到复值优化变量情形，新算法称为复值共轭梯度投影算法。

采用复值共轭梯度投影算法求解问题（1），需要将问题（1）中的矩阵向量化，该方法最大不足在于向量化后导致数据结构破坏与规模的扩大。本文提出复值共轭梯度投影算法一类扩展，适用于问题（1）的求解，同时又避免了矩阵向量化过程。与传统优化方法相比，扩展后的复值共轭梯度投影算法在求解速度上优势明显。

1　预备知识

下面给出一些运算的定义及其相关性质。

定义1［7］设矩E=（eij）∈Cm×n且M∈Cp×q，称如下mp×nq阶矩阵

为E和M的Kronecker积，记为E⊗M。

命题1设以下矩阵运算可以进行，则

（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+表示复矩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设矩阵E∈Cm×n，映射ψ定义为

ψ（E，p）=E⊗Ip

其中p为正整数。

定义3矩阵E∈Cm×n的向量化

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

定义4向量c∈Cnm重组为m列矩阵

命题2任一矩阵E∈Cm×n，F∈Cn×q有

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

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

证明：由上述运算的定义直接得到，此处略。

2　算法导出

问题（1）的向量化形式为

其中d=vec（D），b=vec（B）。假设z˙是问题（2）的最优解，则是问题（1）的最优解。由CR微分［5］可知，问题（2）的目标函数g（z）的复梯度为：

简化起见，▽g（zk）记为▽gk。令投影矩阵=Imn-ψ（A，m）+ψ（A，m）。复值共轭梯度投影算法［6］求解问题（2）的框架如下：

算法1

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

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

步骤1：计算

步骤2：计算lk-=-▽gk，如果‖lk‖2≤ε，则输出zk；否则，计算

再令k=k+1，转步骤1。

定理1［6］如果φ（C，m）Hφ（C，m）是Hermitian正定阵，则算法Ⅰ在mn步内收敛到问题（2）的最优解。

算法1求解问题（1）不足在于向量化后原有数据结构破坏与规模的扩大。本节提出复值共轭梯度投影算法一类扩展，适用于问题（1）的求解，同时又避免了算法中矩阵的向量化过程。

由映射ψ的定义及Kronecker积的性质，有

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

其中，

依据上述结果，易得算法Ⅰ的矩阵化形式，称为算法Ⅱ。该算法是笔值共轭梯度投影算法的一类扩展，避免了原算法Ⅰ中矩阵的向量化操作，同时保留了复值共轭梯度投影算法的收敛性结果。其求解问题（1）的框架如下：

算法Ⅱ

输入：初始可行点Z0=A+B。

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

步骤1：计算

步骤2：计算Lk=-P▽Gk，如果‖Lk‖F≤ε，则输出Zk；否则，计算

再令k=k+1，转步骤1。

定理2如果Q是Hermitian正定阵，则算法Ⅱ在mn步内收敛到问题（1）的最优解。

3　数值实验

实验在联想（CPU2.1GHZ，内存2GB）的个人计算机上进行的，程序用MATLAB语言编写的，并在MATLAB7.6.0的环境下执行。

问题（1）中C∈Cp×n，D∈Cp×m，B∈Cq×m，A∈Cq×n均随机生成，且各元素独立同分布于均值为0，标准差为1的正态分布。实验中，选取凸规划软件包CVX［8］与算法Ⅱ作比较，CVX采用默认的参数设置，算法Ⅱ中A+采用qrginv函数［9］，容忍度ε=10-4。最大迭代数K=mn。不同规模下两算法的运行时间（单位：称）列在表1中，此外，该表还包括了算法Ⅱ求解问题（1）的迭代次数。可以看出，算法Ⅱ在收敛速度上优于传统凸优化方法，当问题规模扩大时，CVX因内存溢出，无法获得问题的最优解。

表1　两类算法运行时间（秒）的比较Tab.1 Comparison of running times of two algorithms

［1］景书杰，赵海燕.等式约束优化问题的一类混合共轭梯度投影算法［J］.安徽大学学报（自然科学版），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］梁玉梅，简金宝.线性约束最优化的一个共轭投影梯度法［J］.运筹与管理，2003，12（2）：31-35.

［4］钟玉泉.复变函数论［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］周杰.矩阵分析及应用［M］.成都：四川大学出版社，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.

（责任编辑：叶丽娜）

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，Fuzhou，Fujian 350108；2.School of Mathematics and Computer Science，Fuzhou University，Fuzhou，Fujian 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-），男，汉族，讲师，主要从事复值优化算法的研究。