求解约束最小二乘半正定规划问题的L-BFGS方法

（上海理工大学 理学院，上海 200093）

Frobenius范数矩阵逼近问题是近年来学者们研究的热门课题，在图像处理、统计、金融与保险等领域有着十分广泛的应用。多年以来许多国内外学者一直致力于研究矩阵逼近问题，并取得了丰硕的成果。Higham[1]使用一种加权Frobenius范数研究了相关系数矩阵最佳逼近问题，并提出使用修改的交替投影法来计算该问题。Malick[2]提出了一种基于拉格朗日对偶的算法来解决等式约束最小二乘问题。Boyd等[3]研究了Frobenius范数意义下的最小二乘协方差矩阵逼近问题，并通过对偶的方法来求解此问题。Gao等[4]考虑具有等式和不等式约束的最小二乘半正定规划，通过将对偶问题转化为带有投影算子的半光滑方程组来解决。他们设计一个非精确的光滑牛顿法来解决产生的半光滑系统，在每次迭代中，使用BiCGStab迭代求解器来获得光滑牛顿线性系统的近似解，数值实验验证了该方法的高效性。He等[5]证明了交替方向法在解决最小二乘半定规划问题上的适用性，并检验了交替方向法的有效性。Li等[6]提出了一种利用投影半光滑牛顿法求解带有等式不等式约束的最佳相关系数矩阵逼近问题，该方法在适当的假设下具有全局收敛性和二次收敛速度。Savas等[7]提出了一种新的Frobenius范数下的聚类矩阵逼近框架，该框架非常灵活，可以按各种方式进行修改以适应特定应用的需要。

本文考虑应用对偶技术研究Frobenius范数意义下的矩阵逼近问题。对偶问题是带非负约束的凸优化问题，在Slater的条件下，对偶问题的最优解与原问题最优解相等。因此，考虑将原问题转化为相应的对偶问题，通过求解对偶问题可以达到求解原问题的目的。为了处理大规模对偶问题，本文利用积极约束技巧估计非负约束，运用L-BFGS方法对自由变量进行加速，并证明了算法的全局收敛性。

1 算法构造

考虑Frobenius范数意义下的矩阵逼近问题

步骤5运用非单调线搜索确定步长。

在确定好搜索方向后，还需确定搜索步长。Zhang等[12]提出并分析了一种新的非单调线搜索算法，证明了非凸光滑函数的全局收敛性和强凸函数的线性收敛性。与单调或传统的非单调方法相比，该非单调线搜索技术一般需要较少的函数和梯度计算次数。因此，本文采用文献[12]中非单调线搜索技术确定迭代步的步长。

2 收敛性分析

3 数值结果

例1的数值实验结果见表1，从表1可以看出，当矩阵维数固定时，增加约束个数，两种方法迭代次数都有所增加，但算法1迭代次数增加较慢，CPU时间比ISNM算法明显少很多。当约束条件固定时，矩阵维数增加，两种方法迭代次数都有所增加，但算法1算法迭代次数增加较慢，而且CPU时间比ISNM算法仍然少很多。这样的结果符合预期，因为算法1只需要储存有限个修正对，而ISNM需要求解牛顿方程，因此，算法1在CPU时间上要比ISNM好一些。另外,ISNM算法默认设置的最大迭代次数是500，表1给出了ISNM在迭代500次时所需CPU时间，对于超过最大迭代次数的情况在表中用*进行标识。算法1成功地解决了例1的所有情况，而ISNM由于达到最大迭代次数500而未能解决例1的3个实例（标记为*），且ISNM的CPU时间已经远超过算法1所需时间。

表1 例 1 的数值实验结果Tab.1 Numerical test results of example 1

例2矩阵C及eii同例1中定义的一样，指标Be={(i,i)|i=1,···,n}，指标集Bl,Bu⊂{(i,j)|1≤i＜j≤n}，由X的第i行随机生成的min(nz,n-i)个元素组成。

分别测试n=1 000,1 500,2 000的情形，数值实验结果如表2所示。从表2可以看出当矩阵维数固定时，增加约束个数，两种方法迭代次数都有所增加，但算法1迭代次数增加较慢，CPU时间比ISNM算法明显少很多。可能的原因是，在m很大的情况下，ISNM需要更多的计算工作来解决广义牛顿方程。当约束条件固定时，矩阵维数增加，两种方法迭代次数都有所增加，但算法1算法迭代次数增加较慢，而且CPU时间比ISNM算法仍然少很多，这个结果是和表1有点相似的。但表2的迭代次数略微比表1多一些，这和测试问题有关。例1中的约束条件位置呈现带状，而例2约束条件位置是随机生成的，这或许是迭代多一些的原因。

表2 例 2 的数值实验结果Tab.2 Numerical test results of example 2

4 结 论

对于该最小二乘半正定规划问题，提出了一种基于柯西点信息的L-BFGS算法。首先将最小二乘半正定规划问题转化为对偶问题，然后构造相应二次模型，再沿着负梯度方向最小化该二次模型得到柯西点，并在此基础上，利用积极约束技巧，划分积极约束集与非积极约束集，然后再运用L-BFGS方法对自由变量进行加速。对于步长的选取，采用非单调搜索技巧确定步长，与单调或传统的非单调方案相比，非单调线搜索算法平均使用较少的函数和梯度计算次数。对于算法1，在一定的条件下，从理论上证明了算法的全局收敛性。最后，进行了初步的数值实验，数值实验表明所提算法1在处理较多约束优化问题时更为有效，与ISNM算法相比，在CPU时间上有一定的优势。