﻿ 求解约束最小二乘半正定规划问题的L-BFGS方法
 上海理工大学学报  2019, Vol. 41 Issue (4): 321-326 PDF

L-BFGS Method for Constrained Least Squares Semidefinite Programming
FAN Changxing, SHEN Chungen, WANG Yunlong
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: The solution of the least squares semidefinite programming problem with equality and inequality constraints was studied. Under the Slater constraint specification, the optimum solutions for the dual and original problems are the same. Therefore, the least squares semidefinite programming problem was transformed into its corresponding dual problem, and the original problem was solved by solving the dual problem. For the solution of the dual problem of the least squares semidefinite programming problem, the quadratic model was constructed, and Cauchy point was obtained by minimizing the quadratic model along the negative gradient direction. On this basis, the positive constraint set and the non-active constraint set were divided by using positive constraint technique. Then, the L-BFGS technique was applied to accelerate the free variables to obtain the optimum solution of the dual problem. Finally, the global convergence of the algorithm was proved theoretically, and a preliminary numerical experiment was carried out to compare the algorithm with the smoothed Newton method. The results show that the algorithm has certain advantages in computing time.
Key words: dual problem     gradient projection method     L-BFGS algorithm     Cauchy point     global convergence

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

1 算法构造

 $\left\{ \begin{array}{l} \min \left(\dfrac{1}{2}\left\| {{ X} - { G}} \right\|_F^2 \right)\\ {\rm{s}}{\rm{.t}}{\rm{. }}\;\bigr\langle {{{ {A_i}}},{ X}} \bigr\rangle \geqslant {{{{ b}_i}}}{\rm{, }}\;\;i \in {\cal I} \\ \;\;\;\;\;\;\bigr\langle {{{ {A_j}}},{ X}}\bigr\rangle = {{{ b}_j}}{\rm{, }}\;\;j \in {\cal E} \\ { X} \in {{S}}_ + ^n \\ \end{array} \right.$

 \left\{ \begin{aligned} & \max \left( - \dfrac{1}{2}\left\| {{{\left( {{ G} + { {\cal A}}\left( { u} \right) + {\cal B}\left( { v} \right)} \right)}_ + }} \right\|_F^2 + \right.\\ &\qquad\;\;\; \left.\dfrac{1}{2}\parallel { G}\parallel _F^2{\rm{ + }}\left( {{{ u}^{\bf{T}}},{{ v}^{\bf{T}}}} \right){{b}}\right) \\ & {\rm{s}}{\rm{.t}}{\rm{. }}\;\;\;\left( {{ u};{ v}} \right) \in { {\varOmega}} \\ \end{aligned} \right. (1)

 $\varphi ({{u}},{{v}}) = \frac{1}{2}\bigr \| {{{\left( {{ G} + {\cal A}\left( { u} \right) + {\cal B}\left( { v} \right)} \right)}_ + }} \bigr \|_F^2 - \frac{1}{2}\bigr \| { G}\bigr \| _F^2 - \left( {{{ u}^{\rm {T}}},{{ v}^{\rm {T}}}} \right){{b}}$

 $\left\{ \begin{array}{l} \min \;\;\;\;{ {\varphi}} ({ u},{ v}) \\ {\rm{s}}{\rm{.t}}{\rm{. }}\;\;\;\;\left( {{ u};{ v}} \right) \in { {\varOmega}} \end{array} \right.$ (2)

${ z} = {\left( {{{ u}^{\rm{T}}},{{ v}^{\rm{T}}}} \right)^{\rm{T}}}$ ${{{{ z}^k}}} = {\left( {{{({{{{ u}^k}}})}^{\rm{T}}},{{({{{{ v}^k}}})}^{\rm{T}}}} \right)^{\rm{T}}}$ 表示第 $k$ 步迭代点， ${ z}_c^k$ 表示第 $k$ 步柯西点[8]。令 $\varphi({ z}) = \varphi ({ u},{ v})$ ${\varphi ^k} = \varphi ({{{{ z}^k}}})$ ${{{ g}^k}} = {\left( {{\nabla _{ u}}\varphi {{\left( {{{{{ z}^k}}}} \right)}^{\rm{T}}},{\nabla _{ v}}\varphi {{\left( {{{{{ z}^k}}}} \right)}^{\rm{T}}}} \right)^{\rm{T}}}$ ${{{ g}_c^k}} = \nabla \varphi \left( { {{ z}_c^k} }\right)$ 。设 ${{{B}}^k}$ 表示 $\varphi$ 在迭代点 ${{{ z}^k}}$ 处Hessian矩阵的L-BFGS近似， ${{{H}}^k}$ 表示 ${{{B}}^k}$ 的逆矩阵。此外，用下标表示向量的分量，例如： ${{{ z}_i^k}}$ 表示 ${{{ z}^k}}$ 的第 $i$ 个分量， ${\left[ {{ z}_{{c}}^{k}}\right]_{i}}$ 表示 ${ z}_{{c}}^{k}$ 的第 $i$ 个分量。

Byrd等[8]采用柯西点估计积极约束集，结果显示柯西点能够有效探测积极约束。据此，采用柯西点处信息确定积极约束集。在 ${{ z}^k}$ 处的柯西点 ${ z}_c^k$ 是通过利用投影技术，沿着负梯度方向最小化如下二次模型而得：

 ${m^k}\left( { z} \right) = \varphi \left( { z} \right) + {\left( {{{ g}^{k}}} \right)^{\rm T}}\left( {{ z} - {{ z}^{ k}}} \right) + \frac{1}{2}{\left( {{ z} - {{ z}^{k}}} \right)^{\rm T}}{{{B}}^k}\left( {{ z} - {{ z}^{ k}}} \right)$

 ${\omega ^k} = \left\| {{{{ z}_c^k}} - {P_{ \varOmega} }\left( {{ {{ z}_c^k }}-{{{ g}_c^k}}} \right)} \right\|\;{\text{且}}\;{\varepsilon ^k} = \min \left\{ {\varepsilon ,{\omega ^k}} \right\}$ (3)

 $C\left( {{{ z}_c^k}} \right) = \left\{ {i \bigl| 0 \leqslant {{\left[ {{{ z}_c^k} }\right]}_i} \leqslant {\varepsilon ^k},i = 1, \cdots ,q} \right\}$ (4)
 $\begin{split} &\quad D\left( {{{ z}_c^k} }\right) = \left\{ {1, \cdots ,m} \right\}\backslash C\left( {{{ z}_c^k} }\right)= \\ & \qquad\left\{ {i\bigr|{{\left[ { {{ z}_c^k}} \right]}_i} > {\varepsilon ^k},i = 1, \cdots ,m} \right\}\qquad\qquad\qquad\qquad\qquad\qquad \\[-15pt] \end{split}$ (5)

 ${C_1}\left({{{ z}_c^k}} \right) = \left\{ {i \bigl|{{\left[ {{{ z}_c^k}} \right]}_i} = 0{\text{且}}{{\left[{{{ g}_c^k}} \right]}_i} \geqslant 0,\;\;i = 1, \cdots ,q} \right\}$ (6)
 ${C_2}\left( {{{ z}_c^k}} \right) = \left\{ {i \bigl|0 \leqslant {{\left[{{{ z}_c^k}} \right]}_i} \leqslant {\varepsilon ^k}{\text{且}}{{\left[ {{{ g}_c^k}} \right]}_i} < 0,\;\;i = 1,\cdots ,q} \right\}\!\!\!\!$ (7)
 ${C_3}\left( {{{ z}_c^k}} \right) = \left\{ {i\bigl|0 < {{\left[{{{ z}_c^k}} \right]}_i} \leqslant {\varepsilon ^k}{\text{且}}{{\left[ {{{ g}_c^k}} \right]}_i} \geqslant 0,\;\;i = 1, \cdots ,q} \right\}\!\!\!\!\!$ (8)

${{{ N}_c^k}}$ 表示列由 $\left\{ {{{{ e}_i}} \in {{\mathbb{R}}^m}|i \in D\left( {{ z}_c^k} \right)} \right\}$ 构成的矩阵。类似地， ${ P}_{1}^{k}$ ${ P}_{2}^{k}$ 分别表示列由 $\left\{ {{{{ e}_i} }\in {{\mathbb{R}}^m}|i \in {C_3}\left( {{{ z}_c^k} }\right)} \right\}$ $\left\{ {{{{ e}_i}} \in {{\mathbb {R}}^m}|i \in {C_2}\left( {{{ z}_c^k} }\right)} \right\}$ 构成的矩阵。为了方便起见，简记 ${\bar{{H}}}_c^k \!=\! {\left( {{{ N}_c^k}} \right)^{\rm T}}{{{H}}^k}{{{ N}_c^k}}$ $D_c^k \!\!=\!\! D\left( {{{ z}_c^k}} \right)$ $C_{ic}^k \!=\! {C_i}\left({{{ z}_c^k} }\right)$ $i \!=\! 1,2,3$

 ${\left[ {{ d}_c^k} \right]_i} = \left\{ \begin{array}{l} 0{\rm{, }}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;i \in C_{1c}^k \\ - {\left[ {{ P}_{1}^{k}{{\left( {{ P}_{1}^{k}} \right)}^{\rm{T}}}{ T}_c^k{{{ g}_c^k}}} \right]_i}{\rm{, }}\;\;\;i \in C_{3c}^k \\ - {\left[ {{ P}_{2}^{k}{{\left( {{ P}_{2}^{k}} \right)}^{\rm{T}}}{{{ g}_c^k}}} \right]_i}{\rm{, }}\;\;\;\;\;\;\;\;\;\;i \in C_{2c}^k \\ - {\left[ {{{{ N}_c^k}}{\bar {{H}}}_c^k{{\left( {{{ N}_c^k}} \right)}^{\rm{T}}}{{{ g}_c^k}}} \right]_i}{\rm{, }}\;\;\;\;i \in D_c^k \\ \end{array} \right.$ (9)

 {\left[ {{ o}_c^k} \right]_i} \!=\! \left\{ \begin{aligned} &{0,}\quad\ \ {{{i}} \notin {{\left[ {{{C}}_c^k} \right]}_3}}\\ &{\dfrac{{{{\left[ {{{ u}_c^k}} \right]}_i}}}{{{{\left[{{{ g}_c^k}} \right]}_i}}}{\rm{,}}} {{\rm{0 < }}{{\left[ {{{{ u}_c}}} \right]}_i} \!\leqslant\! \min\!\! \left\{ {{\varepsilon ^{{k}}},{{\left[ {{{ g}_c^k} }\right]}_i}} \right\},i \in {{\left[ {{{C}}_c^k} \right]}_3}}\\ &{1,}\quad\ \ {\text{其他}} \end{aligned} \right. (10)

 $\varphi \left( {{P_{ {\varOmega}} }\left( {{{{ z}_c^k}} + \alpha {{{ d}_c^k}}} \right)} \right) \leqslant {c^k} + \alpha \delta {\left( {{ g}_c^k} \right)^{\rm T}}{ d}_c^k$ (11)

 ${Q_{k + 1}} = \tau {Q_k} + 1,\;\;{c^{k + 1}} = \frac{{\tau {Q_k}{c^k} + \varphi \left( {{ z}_{c}^{{k} + 1}} \right)}}{{{Q_{k + 1}}}}$ (12)

2 收敛性分析

 $\left\{ {\begin{array}{*{20}{l}} {{{\left[ {{{ g}_c^k}} \right]}_i} - {{\left[{ {{ \lambda} _c^k}} \right]}_i} = 0,}&{i = 1,\cdots ,q}\\ {{{\left[ {{{ g}_c^k} }\right]}_i} = 0,}&{i = q + 1, \cdots ,m}\\ {{{\left[ {{{ \lambda} _c^k}} \right]}_i} \geqslant 0,{{\left[ {{{ z}_c^k}} \right]}_i} \geqslant 0,}&{{{\left[ {{{ \lambda} _c^k}} \right]}_i}{{\left[{{{ z}_c^k} }\right]}_i} = 0{\rm{,}}\;\; i = 1,\cdots ,q} \end{array}} \right.$

 $\left\{ \begin{array}{l} {\left[{{{ g}_c^k}} \right]_i} \geqslant 0{\rm{,}}\;\;{\text{如果}}{\left[{{{ z}_c^k}} \right]_i} = 0{\rm{ , }}\;\;i = 1, \cdots ,q\\ {\left[ {{{ g}_c^k}} \right]_i} = 0{\rm{,}}\;\;i = q + 1,\cdots ,m\\ {\left[ {{{ g}_c^k}} \right]_i} = 0{\rm{,}}\;\;{\text{如果}}{\left[ {{{ z}_c^k} }\right]_i} > 0,\;\;{\rm{ }}i = 1, \cdots ,q \end{array} \right.$ (13)

 $\left\{ \begin{array}{l} - {\left[ {{{P}}_1^k{{\left( {{{P}}_1^k} \right)}^{\rm T}}{ T}_c^k{{g}}_{c}^{k}} \right]_i}{\rm{ = 0,}}\;\;\;i \in C_{3c}^k\\ - {\left[ {{{P}}_2^k{{\left( {{{P}}_2^k} \right)}^{\rm T}}{{g}}_{c}^{k}} \right]_i}{\rm{ = 0,}}\;\;\;\;\;\;\;\;i \in C_{2c}^k\\ - {\left[ {{ N}_{c}^{k} {\bar{ H}}_c^k{{\left( {{{ N}_c^k} }\right)}^{\rm T}}{{g}}_{c}^{k}} \right]_i}{\rm{ = 0,}}\;\;\;i \in D_c^k \end{array} \right.$

 ${\left[ {{{\left( {{ P}_1^k} \right)}^{\rm T}}{{{ g}_c^k}}} \right]_i} = 0,\;i \in C_{3c}^k$
 ${\left[ {{{\left( {{ P}_2^k} \right)}^{\rm T}}{{ g}_c^k}} \right]_i} = 0,\;i \in C_{2c}^k$
 ${\left[ {{{\left( {{ N}_c^k} \right)}^{\rm T}}{{{ g}_c^k}}} \right]_i} = 0,\;i \in D_c^k$

$i \notin C_{1c}^k$ 时， ${\left[{{{ g}_c^k}} \right]_i} = 0$ 。因此式 $\left( {13} \right)$ 成立， ${ z}_c^k$ 是式 $\left( 2 \right)$ $KKT$ 点。

 $\begin{split}&\quad {\left( {{{ g}_c^k} }\right)^{\rm T}}{{{ d}_c^k}} = - \displaystyle\sum\limits_{i \in C_{3c}^k} {{\left[{{{ g}_c^k}} \right]}_i}{\left[ {{ P}_1^k{{\left( {{ P}_1^k} \right)}^{\rm T}}T_c^k{{{ g}_c^k}} }\right]_i} -\\ & \qquad \displaystyle\sum\limits_{i \in C_{2c}^k} {{{\left[ {{{ g}_c^k}} \right]}_i}{{\left[ {{ P}_2^k{{\left( {{ P}_2^k} \right)}^{\rm T}}{{{ g}_c^k}}} \right]}_i}} \!\!-\!\! \displaystyle\sum\limits_{i \in D_c^k} {{\left[ {{{ g}_c^k}} \right]}_i}{{\left[ {{{{ N}_c^k}}{\bar{{H}}}_{c}^{k}{{\left( {{{ N}_c^k}} \right)}^{\rm T}}{{{ g}_c^k}}} \right]}_i} \!\!\leqslant \!0 \end{split}$

 $\beta _c^k \geqslant \min \left\{ {1,\frac{{{\varepsilon ^k}}}{{{{\left\| {{{ d}_c^k}} \right\|}_\infty }}}} \right\}$ (14)

 ${\left[ {{{ z}_c^k} }\right]_i} + {\left[ {\bar \beta _c^k} \right]_i}{\left[{{{ d}_c^k}} \right]_i} \in [0, + \infty ),i = 1, \cdots ,q$ (15)

 ${\left[ {{{ z}_c^k}} \right]_i} + {\bar \beta ^k}{\left[{{{ d}_c^k}} \right]_i} \geqslant {\varepsilon ^k} + {\bar \beta ^k}{\left[ {{{ d}_c^k}}\right]_i} \geqslant {\varepsilon ^k} + \frac{{{\varepsilon ^k}}}{{{{\left\| {{{ d}_c^k}} \right\|}_\infty }}}{\left[ {{{ d}_c^k}} \right]_i} \geqslant 0$

 $\left\{ \begin{array}{l} {m_2}{\left\| {{{\left( {{{ N}_c^k}} \right)}^{\rm T}}{{{ g}_c^k}}} \right\|^2} \leqslant {\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ N}_c^k}}{\bar{{H}}}_c^k{\left( {{{ N}_c^k} }\right)^{\rm T}}{{{ g}_c^k }}\\ \left\| {{\bar{{H}}}_c^k} \right\| \leqslant {m_1} \\ \end{array} \right.$ (16)

 $\begin{split} &\quad{\left\|{{{ d}_c^k}} \right\|^2} = {\left\| {{\bar{{H}}}_c^k{{\left({{{ N}_c^k}} \right)}^{\rm T}}{{{ g}_c^k}}} \right\|^2} + {\left\| {{{\left( {{ P}_1^k} \right)}^{\rm T}}T_c^k{{{ g}_c^k}}} \right\|^2} + {\left\| {{{\left( {{ P}_2^k} \right)}^{\rm T}}{{{ g}_c^k}}} \right\|^2} \leqslant \qquad\qquad\\ &\qquad {\left\| {{\bar{{H}}}_c^k} \right\|^2}{\left\| {{{ g}_c^k}} \right\|^2} + {\left\| {T_c^k} \right\|^2}{\left\| {{{ g}_c^k}} \right\|^2} + {\left\|{{{ g}_c^k}} \right\|^2} \leqslant\\ & \qquad\left( {m_1^2 + 2} \right)m_3^2\\[-10pt] \end{split}$ (17)

 ${\left\| {{{ d}_c^k}} \right\|^2} \leqslant - {m_3}{\left( {{{ g}_c^k} }\right)^{\rm T}}{{{ d}_c^k}}$ (18)

 $\begin{split}& \quad{\left( {{{ g}_c^k} }\right)^{\rm T}}{{{ d}_c^k}} \leqslant - \left( {{\left[ {{{\left( {{{ g}_c^k} }\right)}^{\rm T}}} \right]}_i}{{\left[ {{{P}}_{1}^{k}{{\left( {{{P}}_{1}^{k}} \right)}^{\rm T}}{{{ T}_c^k}}{{g}}_{c}^{k}} \right]}_i} +\right.\qquad\qquad\qquad\qquad\qquad\\ &\qquad\left.{{\left\| {{{\left( {{{P}}_{2}^{k}} \right)}^{\rm T}}{{g}}_{c}^{k}} \right\|}^2} + {m_2}{{\left\| {{{\left({{{ N}_c^k}} \right)}^{\rm T}}{{g}}_{c}^{k}} \right\|}^2} \right) \end{split}$

${ o}_i^k \in \left[ {0,1} \right]$ ，以及式 $\left( {16} \right)$ 和式 $\left( {17} \right)$ 可以得到

 ${\left\| {{{ d}_c^k}} \right\|^2} \leqslant - \frac{{m_1^2}}{{{m_2}}}{\left({{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}}$

 $\varphi \left( {{{ z}^k}} \right) \leqslant {c^k}$ (19)

 $\begin{split} &\quad\varphi \left( {{{{ z}^{k + 1}}}} \right) = \varphi \left( {{P_{ {\varOmega}} }\left[ {{{{ z}_c^k}} + \sigma \alpha _c^k{{{ d}_c^k}}} \right]} \right) > {c^k} + \sigma \alpha _c^k\delta {\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}}\geqslant\qquad\qquad\qquad\qquad\\ &\qquad \varphi \left( {{{ z}^k}} \right) + \sigma \alpha _c^k\delta {\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}}\\[-10pt] \end{split}$ (20)

 $\begin{split} &\quad \varphi \left( {{P_{ \varOmega} }\left[ {{{{ z}_c^k}} + \sigma \alpha _c^k{{{ d}_c^k}}} \right]} \right) - \varphi \left({{{ z}_c^k}} \right) = \varphi \left( {{{{ z}_c^k}} + \sigma \alpha _c^k{{{ d}_c^k}}} \right) - \varphi \left( {{{ z}_c^k}} \right) =\\ &\qquad \sigma \alpha _c^k{\left({{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} + \displaystyle\int_0^{\sigma \alpha _c^k} {\left[ {\nabla \varphi \left( {{{{ z}_c^k}} + t{ d}_{c}^{k}} \right) - \nabla \varphi \left( {{{ z}_c^k}} \right)} \right]} {{{ d}_c^k}}{{\rm d}t} \leqslant \\ &\qquad \sigma \alpha _c^k{\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} + \dfrac{1}{2}L{\sigma ^2}{\left( {\alpha _{c}^{k}} \right)^2}{\left\| {{{ d}_c^k}} \right\|^2} \\ \end{split}$

 $\begin{split} &\quad\sigma \alpha _c^k\delta {\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} \leqslant \varphi \left( {{{ z}^{{k} + {1}}}} \right) - \varphi \left( {{{ z}^k}} \right) \leqslant \\ &\qquad \varphi \left( {{{ z}^{{k} + {1}}}} \right) - \varphi \left( {{{ z}_c^k}} \right) \leqslant \sigma \alpha _c^k{\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} + \qquad\qquad\qquad\qquad\qquad\qquad\\ &\qquad\frac{1}{2}L{\sigma ^2}{\left( {\alpha _{c}^{k}} \right)^2}{\left\| {{{ d}_c^k}} \right\|^2} \\[-15pt] \end{split}$ (21)

 $\alpha _c^k \geqslant \frac{{ - 2\left( {1 - \delta } \right){{\left( {{{ g}_c^k}} \right)}^{\rm T}}{{{ d}_c^k}}}}{{\sigma { L}{{\left\| {{{ d}_c^k}} \right\|}^2}}} \geqslant \frac{{2\left( {1 - \delta } \right)}}{{\sigma L{m_4}}}$

 $\alpha _c^k \geqslant \min \left\{ {\frac{{\bar \beta {\varepsilon ^k}}}{\sigma },\frac{{2\left( {1 - \delta } \right)}}{{\sigma L{m_4}}}} \right\}$ (22)

 ${c^{k + 1}} = \frac{{\tau {Q_k}{c^k} + \varphi \left( {{{ z}^{{k} +{1}}}} \right)}}{{{Q_{k + 1}}}} \leqslant {c^k} + \frac{{\alpha _c^k\delta {{\left({{{ g}_c^k}} \right)}^{\rm T}}{{{ d}_c^k}}}}{{{Q_{k + 1}}}}$ (23)

 $\sum\limits_{k = 0}^\infty {\frac{{\alpha _c^k\delta {{\left( {{{ g}_c^k}} \right)}^{\rm T}}{{{ d}_c^k}}}}{{{Q_{k + 1}}}}} < \infty$ (24)

 ${Q_{k + 1}} = 1 + \sum\limits_{i = 1}^k {\prod\limits_{m = 0}^i \tau } \leqslant 1 + \sum\limits_{j = 0}^k {\tau _{}^{j + 1}} \leqslant \sum\limits_{j = 0}^\infty {\tau _{}^j} = \frac{1}{{1 - \tau }}$

3 数值结果

 \begin{array}{l} \min \;\;\dfrac{1}{2}\left\| {{ X} -{ G}} \right\|_F^2\\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{\begin{aligned} & {{ X}_{{i}{j}}} = {{ e}_{{ i}{j}}},\;\;\left( {i,j} \right) \in {{\cal B}_e}\\ & {{ X}_{{ i}{j}}} \geqslant {{ l}_{{ i}{j}}},\;\;\left( {i,j} \right) \in {{\cal B}_l}\\ & {{ X}_{{i}{j}}} \leqslant {{ u}_{{i}{j}}},\;\;\left( {i,j} \right) \in {{\cal B}_u}\\ & { X} \succcurlyeq 0 \end{aligned}\right. \end{array}

C=2.0*rand（nn）-ones（nn）；C=triu（C）+ triu（C，1）’； C=C*C’；for i=1：nCii）=1；end.

 ${{\cal B}_e} = \left\{ {\left( {i,i} \right)|i = 1, \cdots ,n} \right\}$
 ${{\cal B}_l} = {{\cal B}_u} = \left\{ {\left( {i,i + j} \right)|i = 1, \cdots ,n - j,j = 1,2, \cdots ,{n_{ z}}} \right\}$

4 结　论

 [1] HIGHAM N J. Computing the nearest correlation matrix-a problem from finance[J]. IMA Journal of Numerical Analysis, 2002, 22(3): 329-343. DOI:10.1093/imanum/22.3.329 [2] MALICK J. A dual approach to semidefinite least-squares problems[J]. SIAM Journal on Matrix Analysis and Applications, 2004, 26(1): 272-284. DOI:10.1137/S0895479802413856 [3] BOYD S, XIAO L. Least-squares covariance matrix adjustment[J]. SIAM Journal on Matrix Analysis and Applications, 2005, 27(2): 532-546. DOI:10.1137/040609902 [4] GAO Y, SUN D F. Calibrating least squares semidefinite programming with equality and inequality constraints[J]. SIAM Journal on Matrix Analysis and Applications, 2009, 31(3): 1432-1457. [5] HE B S, XU M H, YUAN X M. Solving large-scale least squares semidefinite programming by alternating direction methods[J]. SIAM Journal on Matrix Analysis and Applications, 2011, 32(1): 136-152. DOI:10.1137/090768813 [6] LI Q N, LI D H. A projected semismooth newton method for problems of calibrating least squares covariance matrix[J]. Operations Research Letters, 2011, 39(2): 103-108. DOI:10.1016/j.orl.2011.01.004 [7] SAVAS B, DHILLON I S. Clustered matrix approximation[J]. SIAM Journal on Matrix Analysis and Applications, 2016, 37(4): 1531-1555. DOI:10.1137/15M1042206 [8] BYRD R H, LU P H, NOCEDAL J, et al. A limited memory algorithm for bound constrained optimization[J]. SIAM Journal on Scientific Computing, 1995, 16(5): 1190-1208. DOI:10.1137/0916069 [9] BYRD R H, NOCEDAL J, SCHNABEL R B. Representations of quasi-Newton matrices and their use in limited memory methods[J]. Mathematical Programming, 1994, 63(1/3): 129-156. [10] NOCEDAL J, WRIGHT S J. Numerical Optimization[M]. New York: Springer, 2006. [11] NI Q, YUAN Y. A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization[J]. Mathematics of Computation, 1997, 66(220): 1509-1520. DOI:10.1090/S0025-5718-97-00866-1 [12] ZHANG H C, HAGER W W. A nonmonotone line search technique and its application to unconstrained optimization[J]. SIAM Journal on Optimization, 2004, 14(4): 1043-1056. DOI:10.1137/S1052623403428208