半定规划的平滑梯度方法

《Journal of Computational and Applied Mathematics》：A smoothing gradient method for semidefinite programs

　　

摘要

受线性与非线性规划中投影梯度方法的启发，本文提出了一种用于半定规划问题的投影梯度方法。在直接应用投影梯度方法求解标准半定规划之前，我们首先利用Fischer-Burmeister函数对标准半定规划问题及其对偶问题的最优性条件进行了修正。该修正不需要求解任何矩阵不等式约束。在适当步长的条件下，新方法的全球收敛性和线性收敛性得到了证明。针对无向图问题的数值实验表明了所提方法的可行性和效率。

引言

半定规划是一类特殊的线性规划，其中非负实向量被实对称半正定矩阵所替换。由于对称正定矩阵的性质，它在信息工程[1][2]以及凸二次问题（如控制理论[3][4]和组合优化[5]）中被广泛应用。内点法是求解半定规划（SDP）问题最常见的方法（参见[6][7][8][9][10]）。由于内点法在每次迭代中都需要处理分支定界，并且对初始点有严格要求，因此许多针对SDP问题的高效方法被提出以克服这些局限性。Toh[11]讨论了增广系统上的迭代求解器以解决大规模SDP问题；Jarre和Rendl[12]给出了一种基于最小化凸函数的增广原始对偶方法；Malick、Povh、Rendl和Wiegele在[13]中讨论了利用二次正则化技术和增广拉格朗日技术的正则化方法；Zhao、Sun和Toh[14]讨论了利用近似半光滑牛顿算法的牛顿-共轭梯度增广拉格朗日方法；Liu和Pataki在[15]中通过基本重构讨论了精确对偶性的性质；Klerk、Glineur和Taylor[16]讨论了不精确梯度和牛顿方法；Tang和Toh[17]讨论了利用黎曼优化的秩-支撑自适应可行方法；Ding、Yurtsever、Cevher等人在[18]中讨论了基于近似互补性框架的新存储最优方法。还存在许多用于求解大规模半定规划的替代数值算法，例如算子分裂方案[19][20]、条件梯度方法[21]以及当需要更高精度时的增广拉格朗日半光滑牛顿-CG方法[22]。近期参考文献可参见[23][24][25][26]。

标准SDP问题表示为
(??) min{??·?? | ??(??) = ??, ?? ? 0}

其对偶问题形式为：
(??) max{??^?? ?? | ?? ? ∑_{??=1}^{??} ??_?? ??_?? = ??, ?? ? 0}

其中??_??是n×n实对称矩阵的空间，??_??^+是??_??中由正定矩阵组成的子集，?^??是m维实向量空间，??, ??_?? ∈ ??_?? (?? = 1, …, ??)是给定数据。?? = (??_1, …, ??_??)^?? ∈ ?^??，?? = (??_1, …, ??_??)^?? ∈ ?^??，?? ? 0表示?? ∈ ??_??^+。此外，?? ? 0表示?? ∈ ??_??且??是正定矩阵。我们用??·?? = ???, ??? = ????(??^?? ??)表示矩阵C和X的标量积，其中????(·)是矩阵的迹。我们定义

??(??) = (??_1·??, ??_2·??, …, ??_??·??)^?? = (??_1, ??_2, …, ??_??)^?? = ??

我们还定义?为实数集，?^+为正实数集。对于??_1, ??_2 ∈ ??_??，??_1 ? ??_2表示??_1 ? ??_2 ∈ ??_??^+，??_1 ? ??_2表示??_1 ? ??_2是对称正定矩阵，‖??_1‖ = √???_1, ??_1?。由于SDP问题(1.1)及其对偶问题(1.2)中的目标函数和约束条件（如??·??, ??^?? ??, ??(??) = ??以及?? ? ∑_{??=1}^{??} ??_?? ??_?? = ??）是线性的，而矩阵不等式约束?? ? 0和?? ? 0是非光滑凸的，因此SDP问题(1.1)及其对偶问题(1.2)是非光滑凸优化问题。

在本文中，我们考虑一种用于求解SDP问题(1.1)及其对偶问题(1.2)的投影梯度方法。半定优化中的投影方法在2012年的第[27]章（书系列[28]的一部分）中进行了综述。由于SDP问题(1.1)及其对偶问题(1.2)是凸的，如果(1.1)和(1.2)有严格可行点，则强对偶条件成立。由此可得，(??, ??, ??) ∈ ??_?? × ?^?? × ??_??是(1.1)和(1.2)的最优解当且仅当

{ ??·?? = ??^?? ??
{ ??(??) = ??
{ ?? ? ∑_{??=1}^{??} ??_?? ??_?? = ??
{ ?? ? 0, ?? ? 0, ??·?? = 0

在我们分析SDP问题(1.1)及其对偶问题(1.2)在适当假设下的最优性条件(1.3)之前，我们首先利用Fischer-Burmeister函数和普通最小二乘法对最优性条件(1.3)进行修正。该重构基于光滑Fischer-Burmeister函数，不需要在每次迭代中求解任何矩阵不等式约束。此外，新方法对初始点没有要求。

本文的组织结构如下：在第2节中，我们利用Fischer-Burmeister函数和普通最小二乘法给出SDP问题(1.1)及其对偶问题(1.2)最优性条件的修正。在第3节中，我们提出了一种用于SDP问题的投影梯度方法。在第4节中，我们讨论了在不同假设和新方法下全局收敛性和收敛速率。在第5节中，展示了一些针对无向图问题和随机生成SDP问题的数值实验。最后，在第6节中给出本文的结论。

各节摘要

最优性条件的修正

在本节中，我们希望给出SDP问题(1.1)及其对偶问题(1.2)最优性条件(1.3)的修正。这些修正可以将SDP问题(1.1)及其对偶问题(1.2)转化为无约束优化问题。我们首先给出Fischer-Burmeister函数的一些基本性质，并建立其变换的一些新性质。关于Fischer-Burmeister函数的更多信息可参见[29][30]。

引理2.1（参见Fischer [29]）对任意??, ?? ∈ ?，令

??(??, ??) := ?? + ?? ? √(??^2 + ??^2)

投影梯度方法的描述

在本节中，我们建立了一种用于求解(2.13)的投影梯度方法。为此，我们给出函数H(X, y, S, τ)的一些性质，并回顾投影的一些基本性质。由引理2.3可知，由(2.11)给出的函数H(X, y, S, τ)对于任意??, ?? ∈ ??_??, ?? ∈ ?^??和τ > 0是连续可微的，因此我们得到以下定理。

定理3.1 对任意??, ?? ∈ ??_??, ?? ∈ ?^??, τ > 0，设ψ(X, S, τ)由引理2.2给出，H(X, y, S, τ)由(2.11)给出。如果??^2 + ??^2 + 2τ^2 ?? ? 0，则H(X, y, S, τ)

收敛性分析

在本节中，我们研究算法1在不同假设和步长下的全局收敛性和收敛速率。我们首先给出一个有用的引理，该引理将在后续算法收敛性分析中发挥重要作用。

引理4.1（参见[38]）设D为凸集，f(x)在D上连续可微。则f(x)在D上是凸函数当且仅当

??(??) ? ??(??) ≥ ???(??)^?? (?? ? ??)

对任意x, y ∈ D成立。

以下定理给出了算法1全局收敛性的性质。

定理4.1 假设

数值算例

在本节中，我们展示了不同SDP算例的数值结果。这些结果由算法1的MATLAB实现获得，包括求解无向图算例（无环）的结果以及在大规模随机生成SDP问题上的性能。我们给出算法1的框架如下所示的算法2，将在本部分的数值实验中使用。

对于数值实验，我们在算法2中使用以下参数：
• ??_0 = ??_??

结论

在本文中，我们提出了一种用于SDP问题的投影梯度方法。利用Fischer-Burmeister函数和普通最小二乘法，将标准SDP问题及其对偶问题的最优性条件重构为无约束优化问题。如果重构问题是Lipschitz连续的，则新方法的阶为??(1/??)；如果重构问题是梯度Lipschitz连续的，则阶为??(1/??)。此外，新方法……

伦理审批与参与同意

不适用。

出版同意

不适用。

人体与动物伦理

不适用。

利益冲突声明

作者声明他们没有已知的竞争性财务利益或个人关系可能会影响本文报告的工作。

黄爱群

华中科技大学，数学与统计学院，数学与应用科学交叉研究院，湖北工程建模与科学计算重点实验室，武汉，430074，中国