上海理工大学学报  2019, Vol. 41 Issue (4): 321-326   PDF    
求解约束最小二乘半正定规划问题的L-BFGS方法
樊长幸, 沈春根, 王云龙     
上海理工大学 理学院,上海 200093
摘要: 对带等式和不等式约束的最小二乘半正定规划问题的求解进行了研究。在Slater约束规范条件下,对偶问题的最优解与原问题最优解相等。因此,考虑将最小二乘半正定规划问题转化为相应的对偶问题,通过求解对偶问题达到求解原问题的目的。针对最小二乘半正定规划问题的对偶问题,首先构造相应的二次模型,沿负梯度方向最小化该二次模型得到柯西点,在此基础上,利用积极约束技巧,划分积极约束集与非积极约束集,然后应用L-BFGS技巧对自由变量进行加速,从而求得对偶问题的最优解。最后,从理论上证明了算法的全局收敛性,并进行了初步的数值实验,将该算法与光滑化牛顿法作对比,结果表明该算法在计算时间上有一定的优势。
关键词: 对偶问题     梯度投影法     L-BFGS算法     柯西点     全局收敛性    
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范数下的聚类矩阵逼近框架,该框架非常灵活,可以按各种方式进行修改以适应特定应用的需要。

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

1 算法构造

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

$ \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. $

式中: ${\cal I} \!=\! \left\{ {1, \!\cdots\!, q} \right\}$ ${\cal E} \!=\! \left\{ {q \!+\! 1,\! \cdots\! ,m} \right\}$ ${{{ A}_i}} \!\in\! {{{S}}^n}$ $m \!=\! p \!+\! q$ ${{{S}}^n} = \left\{ {{{M}} \in {{\mathbb {R}}^{n \times n}}\left| {{M}} \right.{\text{是对称矩阵}}} \right\}$ ${{{S}}_ + ^n}= \left\{ {{M}} \in {{\mathbb {R}}^{n \times n}}| {{M}}{\text{是}}\right.$ $\left.{\text{对称半正定矩阵}} \right\}$ ${{b}} = {({ {b_1}}, \cdots ,{ {b_m}})^{\rm{T}}} \in {\mathbb{R}^{n \times n}}$ 是给定的向量, ${\left\| \cdot \right\|_F}$ 表示由标准内积 $\left\langle { \cdot , \cdot } \right\rangle $ 诱导的 ${\rm{Frobenius}}$ 范数。

根据文献[3]可知上述问题的对偶问题为

$ \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)

式中: ${\cal A}\left( { u} \right) = \displaystyle\sum\limits_{i = 1}^q {{{ {u_i}}}{{ {{ A}_{i}}}}} $ ${\cal B}\left( { v} \right) = \displaystyle\sum\limits_{j = 1}^p {{{{{ v}_j}}}{{ A}_{{j} + q}}} $ $\left( {{ u}^{\rm T}},{{ v}^{\rm T}} \right){{b}} = $ $\displaystyle\sum\limits_{i = 1}^q {{{{{ u}_i}}}{{{ b}_i}}} {\rm{ + }}\displaystyle\sum\limits_{j = 1}^p {{{{ v}_j}}{{ b}_{{j} + {q}}}} $ ${ {\varOmega}} = \left\{ {\left( {{ u};{ v}} \right)|{ u} \geqslant 0,{ u} \in {\mathbb{R}^q},{ v} \in {\mathbb{R}^p}} \right\}$

$\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( 1 \right)$ 可转换为极小化对偶模型

$ \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$ 个分量。

对于该问题的算法构造,分5步进行。

步骤1  计算柯西点。

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) $

步骤2  更新 ${{ B}^k}$ ${{{H}}^k}$

利用L-BFGS算法间接产生 ${{ B}^k}$ ${{{H}}^k}$ ,详情参见文献[9-10]。

步骤3  确定积极约束集与非积极约束集。

首先,先给出投影误差估计,对于给定的充分小的 $\varepsilon > 0$ ,令

$ {\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)

式中, ${P_{ {\varOmega}} }(x)$ 表示 $x$ ${ {\varOmega }}$ 上的投影。

其次,类似文献[11],可以根据 ${\varepsilon ^k}$ 定义指标集 $C\left( {{{{ z}_c^k}}} \right)$ $D\left({{{ z}_c^k}} \right)$

$ 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\left( {{{ z}_c^k}} \right)$ 中指标对应的变量被称作积极变量, $D\left( {{{ z}_c^k}} \right)$ 中指标对应的变量被称作非积极变量。为了获得积极变量的搜索方向,将积极集 $C\left({{{ z}_c^k} }\right)$ 划分为3个部分:

$ {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)

注意到 ${C_1}\left( {{{ z}_c^k}} \right)$ 中的变量符合相应的最优性条件,所以它是合理的; ${C_3}\left({{{ z}_c^k}} \right)$ 中的变量沿着最速下降方向达到或指向边界,因此,最速下降方向在子空间中应当回溯以保证其可行;而 ${C_2}\left( {{{ z}_c^k}} \right)$ 中的变量沿着最速下降方向在可行域内部移动。

步骤4  确定搜索方向。

${{{ 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)

式中, $ {{{ T}_c^k}} = {\rm{diag}}\left( {{{\left[ {{{ o}_c^k}} \right]}_1},\cdots,{{\left[ {{{ o}_c^k}} \right]}_q}} \right) $

$ {\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)

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

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

算法1

步骤1  给定初始点 ${{ z}^{0}} \in { \varOmega }$ $0 < \sigma < 1$ $0 < $ $\tau < 1$ $0 < \delta < \dfrac{1}{2}$ $\varepsilon > 0$ ,初始矩阵 ${{{H}}^0}$ ${c_0} = \varphi \left( {{{ z}^{0}}} \right)$ ${Q_0} = 1$ ${{k = 0}}$

步骤2  根据式(4)~(8),确定 $D_c^k$ $C_{ic}^k,i =$ $ 1,2,3$

步骤3  参照文献[8]中方法计算出柯西点 ${{{ z}_c^k}}$ ,如果 $\varphi \left( {{{ z}_c^k} }\right) > \varphi \left( {{{{ z}^k}}} \right)$ ,则令 ${{{ z}_c^k}} = {{{ z}^k}}$

步骤4  根据式 $\left( 9 \right)$ 计算搜索方向 ${{{ d}_c^k}}$ ,并令 $\alpha {\rm{ = 1}}$

步骤5  如果 ${{{ d}_c^k}} = 0$ ,那么停止迭代;

步骤6  如果步长因子 $\alpha $ 满足非单调线搜索条件

$ \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)

那么,令 $\alpha _c^k = \alpha $ ,否则令 $\alpha = \sigma \alpha $ ,返回步骤6;

步骤7  令 ${{ z}^{{k} + 1}} = {P_{ \varOmega} }\left( {{{{ z}_c^k}} + \alpha _c^k{{{ d}_c^k}}} \right)$

$ {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)

采用文献[9]中算法7.4更新生成 ${{{H}}^{k + 1}}$ 的信息;

步骤8   $k = k + 1$ ,返回步骤2。

2 收敛性分析

引理1  假定 $\left\{ {{{ d}_c^k}} \right\}$ $\left\{ {{{ z}_c^k}} \right\}$ 由算法1生成, ${{{H}}^k}$ 正定,则 ${{{ z}_c^k}}$ 是问题 $\left( 2 \right)$ $KKT$ 点,当且仅当 ${ d}_c^k = 0$

证明  首先假定 ${{{ z}_c^k}}$ 是式 $\left( 2 \right)$ $KKT$ 点,则存在拉格朗日乘子 ${\left[ {{{ \lambda} _c^k}} \right]_i} \geqslant 0,i = 1, \cdots ,q$ ,使得

$ \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)

由于假定 ${{{ z}_c^k}}$ 是式 $\left( 2 \right)$ $KKT$ 点,则 ${\left[ {{{ g}_c^k}} \right]_i} = 0,i =$ $ q + 1, \cdots ,m$ ,或 ${\left[ {{{ g}_c^k}} \right]_i} \geqslant 0$ $i = 1, \cdots ,q$ 。由式 $\left( 6 \right)$ $\left( 8 \right)$ 及式 $\left( {13} \right)$ 可知, $C_{2c}^k = \phi $ 。由式 $\left( 9 \right)$ 可知, ${\left[{{{ g}_c^k}} \right]_i} = 0$ $i \in D_c^k \cup C_{{\rm{3}}c}^k$ ,因此, ${ d}_c^k = 0$

反过来,假定 ${ d}_c^k = 0$ ,由式 $\left( 9 \right)$ 则有

$ \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. $

由于 ${\bar {{H}}}_c^k$ ${{{H}}^k}$ 正定,且 ${\left[ {{{ o}_c^k}} \right]_i} \ne 0$ ,那么

$ {\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$ 点。

引理2  如果 ${\bar {{H}}}_{c}^{k}$ 是正定的, ${{{ d}_c^k}}$ 是由式 $\left( 9 \right)$ 定义的,则它满足 ${\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} \leqslant 0$ ,等号成立当且仅当 ${{{ d}_c^k}} = 0$

证明  由式 $\left( 9 \right)$

$ \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} $

于是, ${\left({{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} = 0$ ,当且仅当 ${{{ d}_c^k}} = 0$ 时等号成立。

定理1  假设 $\left\{{{{ d}_c^k}} \right\}$ $\left\{{{{ z}_c^k} }\right\}$ 由算法1产生,则 ${{{ z}_c^k}}$ 是式 $\left( 2 \right)$ $KKT$ 点当且仅当 ${\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} = 0$

证明  由引理1和引理2证得。

引理3  假设 $\left\{ {{{ d}_c^k}} \right\}$ $\left\{ {{{ z}_c^k}} \right\}$ 由算法1产生, ${\varepsilon ^k}$ 是由式 $\left( 3 \right)$ 定义,且 ${{{ d}_c^k}} \ne 0$ ,则有

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

这里, $ \,{\beta ^k} = \mathop {\sup }\limits_{0 \leqslant \eta \leqslant 1} \left\{ {\eta |0 \leqslant { z}_{{c}}^{k} + \eta {{{ d}_c^k}}} \right\} $

证明  根据定义, ${{{ z}_c^k}}$ ${{{ z}_c^k}} + \beta _c^k{{{ d}_c^k}}$ 必须满足式 $\left( 2 \right)$ 的约束条件,只需证明下面式子即可:

$ {\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)

其中, $\,\bar \beta _c^k = \min \left\{ {1,\dfrac{{{\varepsilon ^k}}}{{{{\left\| {{{ d}_c^k}} \right\|}_\infty }}}} \right\}$

如果 $i \in C_{1c}^k$ ,则 ${\left[{{{ d}_c^k}} \right]_i} = 0$ ,而 ${\left[ {{{ z}_c^k}} \right]_i} \geqslant 0$ $\;\bar \beta _c^k > 0$ ,则 ${\left[ {{{ z}_c^k}} \right]_i} + {\left[ {\bar \beta _c^k} \right]_i}{\left[ {{{ d}_c^k}} \right]_i} \geqslant 0$ ;若 $i \in C_{3c}^k$ ${\left[{{{ d}_c^k}} \right]_i} \leqslant 0$ ,且 ${\left[ {{{ z}_c^k}} \right]_i} + {\left[ {{{ d}_c^k}} \right]_i} = 0$ ,则 ${\left[ {{{ z}_c^k}} \right]_i} + {\left[ {\bar \beta _c^k} \right]_i}{\left[ {{{ d}_c^k}} \right]_i} \geqslant {\left[{{{ z}_c^k}} \right]_i} + $ $ {\left[ {{{ d}_c^k}} \right]_i} = 0; $ $i \in C_{2c}^k$ ${\left[{{{ d}_c^k}} \right]_i} > 0$ ,则 ${\left[ {{{ z}_c^k}} \right]_i} + {\left[ {\bar \beta _c^k} \right]_i}{\left[ {{{ d}_c^k}} \right]_i} \geqslant 0$ ;若 $i \in D_c^k$ ${\left[ {{{ d}_c^k}} \right]_i} \ne 0$ ,当 ${\left[{{{ d}_c^k}} \right]_i} > 0$ 时,则 ${\left[ {{{ z}_c^k}} \right]_i} + {\left[ {\bar \beta _c^k} \right]_i}{\left[{{{ d}_c^k}} \right]_i}$ $ \geqslant 0$ ;当 ${\left[ {{{ d}_c^k}} \right]_i} < 0 $ ,则

$ {\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 $

因此,对任意的 $i = 1,2, \cdots ,m$ ,式 $\left( {15} \right)$ 都成立,所以式 $\left( {14} \right)$ 成立。

引理4  假设 $\left\{ {{ z}_c^k} \right\}$ 是有界的, $\left\{ {{\bar{{H}}}_{c}^{k}} \right\}$ 一致正定有界, $\left\{ {{{ d}_c^k}} \right\}$ 由算法1生成, ${\varepsilon ^k}$ 由式 $\left( 3 \right)$ 定义,则存在常数 $\,\bar \beta \in \left( {0,1} \right)$ ,使得对一切正整数 $k$ ,都有 $\,\beta _c^k \geqslant \bar \beta {\varepsilon ^k}$

证明  由于 $\left\{ {{\bar{{H}}}_c^k} \right\}$ 一致正定有界,则存在 ${m_1},{m_2} > 0$ ,使得对一切正整数 $k$ ,都有

$ \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)

因为 $\nabla \varphi $ ${\rm Lipschitz}$ 连续且 $\left\{ {{{ z}_c^k}} \right\}$ 有界,所以 $\left\{ {{{ g}_c^k}} \right\}$ 有界,即存在 ${m_3} > 0$ ,使得对一切正整数 $k$ ,都有 $\left\| {{{ g}_c^k}} \right\| \leqslant {m_3}$ 。由式 $\left( 9 \right)$ 可知

$ \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( {14} \right)$ 及式 $\left( {17} \right)$ 可知,存在 $\,\bar \beta \in \left( {0,1} \right)$ ,使得对一切正整数 $k$ ,都有 $\,\beta _c^k \geqslant \bar \beta {\varepsilon ^k}$

引理5  假设 $\left\{ {{\bar{{H}}}_{c}^{k}} \right\}$ 一致正定有界, $\left\{ {{{ d}^k}} \right\}$ 由算法1产生,则对一切正整数 $k$ ,都有

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

其中, ${m_1},{m_2}$ 来自式 $\left( {16} \right)$

证明  由式 $\left( 9 \right)$ 可知:

$ \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}} $

即式 $\left( {18} \right)$ 成立。

引理6  设 ${c^k}$ ${{{ d}_c^k}}$ 由算法1产生,则对任意 $k$

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

证明参见文献[11]中引理1。

定理2  假设 $\left\{{{{ z}_c^k}} \right\}$ 是有界的, $\left\{ {{\bar{{H}}}_{c}^{k}} \right\}$ 一致正定有界, $\left\{ {{{ d}_c^k}} \right\}$ 由算法1产生,则 $\left\{ {{{ z}_c^k}} \right\}$ 的极限点都是问题 $\left( 2 \right)$ $KKT$ 点。

证明  分两步证明该结论,第一步,先证明 $\alpha _c^k$ 是有下界的。

假定 $\alpha _c^k$ 满足式 $\left( {11} \right)$ ,如果 $\sigma \alpha _c^k \geqslant \bar \beta {\varepsilon ^k}$ ,则 $\alpha _c^k \geqslant \dfrac{{\bar \beta {\varepsilon ^k}}}{\sigma }$ ,否则, $\alpha _c^k < \dfrac{{\bar \beta {\varepsilon ^k}}}{\sigma }$

由式 $\left( {19} \right)$ $\varphi \left( {{{ z}^k}} \right) \leqslant {c^k}$ ,有

$ \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)

由于 $\nabla \varphi $ 满足 ${\rm Lipschitz}$ 连续,则

$ \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} $

由式 $\left( {20} \right)$ 可得

$ \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)

由引理5和式 $\left( {21} \right)$ 可得

$\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)

式中, $m_4=\dfrac{m^2_1}{m_2} $

第二步,证明 $ \mathop {\lim }\limits_{k \to \infty } {\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} = 0$

由式 $\left( {11} \right)$ 和式 $\left( {12} \right)$ 可得

$ {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)

由于 $\varphi $ 有下界,由引理6知 $\varphi \left( {{{ z}_{}^k} }\right) \leqslant {c^k}$ ,对任意的正整数 $k$ 都成立,结合引理2可知 $\{ {c^k}\} $ 单调减小且有下界。由式 $\left( {23} \right)$ 可得

$ \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)

假设 ${{ z}^*}$ $\{ {{{ z}_c^k}}\} $ 的任一聚点。于是,存在无限指标集 ${\cal K}$ 使得 $\mathop {\lim }\limits_{k \to \infty } {{{ z}_c^k}} = {{ z}^*}$ 。不妨设 $\mathop {\lim }\limits_{k \to \infty } {w^k} = \bar w$ ,若 $\bar w = 0$ ,则 ${{ z}^*}$ 为问题 $\left( 2 \right)$ $KKT$ 点,否则 $\bar w > 0$ 。由式 $\left( {22} \right)$ 可知, ${\left\{ {\alpha _c^k} \right\}_{\cal K}}$ 下界不会趋于零,结合式 $\left( {24} \right)$ $\mathop {\lim }\limits_{k \in {\cal K},k \to \infty } \dfrac{{{{\left( {{{ g}_c^k}} \right)}^{\rm T}}{{{ d}_c^k}}}}{{{Q_{k + 1}}}} = 0$ 。又因为 $0 < \tau < 1$ ,则有

${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 }}$

所以 $1 < {Q_{k + 1}} \leqslant \dfrac{1}{{1 - \tau }}$ ,即 ${Q_{k + 1}}$ 不会趋于零,因此, $\mathop {\lim }\limits_{k \in {\cal K},k \to \infty } {\left( {{{ g}_c^k}} \right)^{\rm T}}{{{ d}_c^k}} = 0$

由定理2知, ${{ z}^*}$ 为问题 $\left( 2 \right)$ $KKT$ 点。综上, $\left\{ {{z}}_c^k \right\}$ 的极限点均为问题 $\left( 2 \right)$ $KKT$ 点。

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} $

式中, ${{\cal B}_e}$ ${{\cal B}_l}$ ${{\cal B}_u}$ $\left\{ {\left( {i,j} \right)|1 \leqslant i \leqslant j \leqslant n} \right\}$ 的3个指标子集,满足: ${{\cal B}_e} \cap {{\cal B}_l} = \phi $ ${{\cal B}_e} \cap {{\cal B}_u} = \phi $ ${ { l}_{ij}} \leqslant { { u}_{ij}}$ $\forall \left( {i,j} \right) \in {{\cal B}_l} \cap {{\cal B}_u}$ 。用 ${p_e}$ ${q_l}$ ${q_u}$ 分别指代 ${{\cal B}_e}$ ${{\cal B}_l}$ ${{\cal B}_u}$ 的基数,所以总约束个数 $m = {p_e} + {q_l} + {q_u}$

对于上述类型测试问题,通过例1、例2分别进行了数值实验,并将算法1与文献[4]中光滑牛顿法(用ISNM表示)从迭代次数和CPU时间两个方面进行比较。采用Matlab语言(Matlab 8.6.0)编程实现算法1,并在个人电脑(配置为CPU 2.30 GHZ,RAM 8.00 GB)上运行测试问题。算法1的初始值设置为:给定初始点 ${z^0} = 0$ , $\sigma {\rm{ = 0}}{\rm{.2}}$ $\tau {\rm{ = 0}}{\rm{.85}}$ $\delta {\rm{ = 1}}{{\rm{0}}^{{\rm{ - 4}}}}$ ,初始矩阵 ${{{H}}^0}={ I}$ $\varepsilon {\rm{ = 1}}{{\rm{0}}^{{\rm{ - 5}}}}$ 。对ISNM算法,采用默认设置。

测试问题(参见文献[4])

例1  数据矩阵 ${{C}}$ 来自文献[4],它是一个随机生成的 $n \times n$ 对称矩阵,其中 ${{{C}}_{ij}}$ 按照 $\left[ { - 1,1} \right]$ 上均匀分布随机生成,且令 ${{{C}}_{ii}} = 1$ $i,j = 1,\cdots ,n$ 。生成数据矩阵 $ C$ ,细节由如下的Matlab代码具体给出:

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\}$

式中, ${n_{ z}}$ ${ X}$ 中每行设定的上(下)界约束的个数。当 $\left( {i,i} \right) \in {{\cal B}_e}$ 时, ${{ e}_{ii}} = 1$ ;当 $\left( {i,j} \right) \in {{\cal B}_l}$ 时, ${{ l}_{ij}} =$ $ - 0.1$ ;当 $\left( {i,j} \right) \in {{\cal B}_u}$ 时, ${{ u}_{ij}} =$ $ 0.1$ 。分别测试 $n =1\;000$ $1\;500$ $2\;000$ 时的实验结果。

例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的数值实验结果 Table 1 Numerical test results of example 1

例2  矩阵 ${{C}}$ ${{ e}_{{i}{i}}}$ 同例1中定义的一样,指标 ${{\cal B}_e} = \left\{ {\left( {i,i} \right)|i = 1, \cdots ,n} \right\}$ ,指标集 ${{\cal B}_l},{{\cal B}_u} \subset \left\{ \left( {i,j} \right)|1 \leqslant \right. i < $ $ \left.j \leqslant n \right\}$ ,由 ${ X}$ 的第 $i$ 行随机生成的 $\min \left( {{n_{ z}},n - i} \right)$ 个元素组成。

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


表 2 例2的数值实验结果 Table 2 Numerical test results of example 2
4 结 论

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

参考文献
[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