2025-11-23T20:52:17.171893

Asymmetric Burer-Monteiro Factorization with Theoretically Sound Penalty for Semidefinite Programming

Hu, Kwok

In the solving of large-scale semidefinite programs (SDPs), the symmetric Burer-Monteiro factorization (BMF) offers an economical low-rank solution of the form $XX^\top$. However, BMF turns a convex SDP into a more difficult nonconvex optimization problem in some cases, which limits the use of off-the-shelf convex optimization algorithms. To alleviate this problem, we convert symmetric BMF to its asymmetric counterpart involving $XY^\top$, and use a penalty with parameter $Î³$ to encourage $X$ and $Y$ to be close. We show that the resultant asymmetric BMF is multi-convex, and thus convex optimization can again be used to solve the subproblems involving $X$ and $Y$ in an alternating manner. More importantly, to ensure that $X=Y$ on convergence, we derive theoretically sound conditions for exact $Î³$ that are independent of both the application problem and underlying algorithm. Experiments demonstrate that the proposed method is more advantageous over existing related approaches.

academic

Asymmetric Burer-Monteiro Factorization with Theoretically Sound Penalty for Semidefinite Programming

基本信息

论文ID: 1811.01198
标题: Asymmetric Burer-Monteiro Factorization with Theoretically Sound Penalty for Semidefinite Programming
作者: Enliang Hu (云南师范大学), James T. Kwok (香港科技大学)
分类: cs.LG math.OC stat.ML
发表时间: 2018年11月提交，2025年10月更新版本
论文链接: https://arxiv.org/abs/1811.01198

摘要

在求解大规模半定规划(SDPs)问题中，对称Burer-Monteiro分解(BMF)提供了形如 $XX^\top$ 的经济低秩解。然而，BMF将凸SDP转化为更困难的非凸优化问题，限制了现成凸优化算法的使用。为缓解此问题，本文将对称BMF转换为涉及 $XY^\top$ 的非对称形式，并使用参数 $\gamma$ 的惩罚项鼓励 $X$ 和 $Y$ 接近。研究表明，结果的非对称BMF是多凸的，因此可以再次使用凸优化以交替方式求解涉及 $X$ 和 $Y$ 的子问题。更重要的是，为确保收敛时 $X=Y$ ，文章推导了独立于应用问题和底层算法的精确 $\gamma$ 的理论充分条件。

研究背景与动机

问题背景

大规模半定规划的挑战：许多机器学习问题需要学习低秩正半定矩阵，通过求解形如 $\min_{Z \in S_n^+} f(Z)$ 的半定规划。对于大规模问题，传统内点法需要 $O(n^3)$ 时间复杂度，不具备可扩展性。
Burer-Monteiro分解的局限性：虽然对称BMF通过 $Z = XX^\top$ 分解可以自动满足正半定约束并减少变量维度，但将凸问题转化为非凸问题，限制了凸优化算法的直接应用。
现有方法的不足：
- 对称BMF中 $X$ 和 $X^\top$ 不可分离，无法使用高效的分裂或交替算法
- 现有非对称方法的惩罚参数设置缺乏理论保证，依赖启发式调整

研究动机

本文旨在通过非对称分解 $XY^\top$ 恢复凸优化算法的适用性，同时提供理论上严格的惩罚参数设置，确保方法的通用性和可靠性。

核心贡献

理论贡献：首次证明了精确惩罚参数的存在性，提供了独立于应用问题和算法的理论下界
方法创新：将对称BMF转换为多凸的非对称BMF，使得凸优化算法可以交替求解子问题
通用框架：扩展了BMF到包含正则化项 $h(X)$ 的更一般形式
收敛保证：在动态惩罚参数下提供了收敛性分析，放松了现有工作对常数惩罚参数的限制

方法详解

任务定义

原始问题： $\min_{Z \in S_n^+} f(Z)$ 其中 $S_n^+ = \{Z \in \mathbb{R}^{n \times n} | Z = Z^\top, Z \succeq 0\}$ 是 $n \times n$ 对称正半定矩阵锥。

扩展的对称BMF： $\min_{X \in \mathbb{R}^{n \times r}} f(XX^\top) + h(X)$

本文的非对称BMF： $\min_{X,Y} F(X,Y;\gamma) \equiv f(XY^\top) + \frac{1}{2}h(X) + \frac{1}{2}h(Y) + \frac{\gamma}{2}\|X-Y\|_F^2$

核心理论结果

多凸性证明

命题1：如果 $f(Z)$ 关于 $Z$ 是凸的，则 $F(X,Y;\gamma)$ 关于 $X$ 或 $Y$ 的任一子部分都是凸的。

这一性质使得可以交替优化：

$X^k = \arg\min_{X} F(X, Y^{k-1}; \gamma)$
$Y^k = \arg\min_{Y} F(X^k, Y; \gamma)$

惩罚参数的理论下界

定理1：在假设条件下，如果 $\gamma > \frac{1}{2} \frac{\text{tr}((\bar{X}-\bar{Y})^\top \partial_Z f(\bar{X}\bar{Y}^\top)(\bar{X}-\bar{Y}))}{\|\bar{X}-\bar{Y}\|_F^2} - \frac{\sigma_h}{4}$ 则临界点满足 $\bar{X} = \bar{Y}$ 。

推论1（实用形式）： $\gamma > \frac{1}{2}(\|\partial_Z f(Z_0)\|_F + L_f d_{L_f}(f(Z_0))) - \frac{\sigma_h}{4}$

推论2（强凸情况）： $\gamma > \frac{L_f}{\sqrt{\sigma_f}} \sqrt{\frac{f(Z_0) - f(\dot{Z})}{2}} - \frac{\sigma_h}{4}$

算法框架

算法1：扩展Burer-Monteiro分解的交替优化

1. 初始化: X⁰, Y⁰, γ⁰, K
2. for k = 1, ..., K do
3.   更新 Xᵏ ≈ argmin_X F(X, Yᵏ⁻¹; γᵏ⁻¹) 通过凸算法
4.   更新 Yᵏ ≈ argmin_Y F(Xᵏ, Y; γᵏ⁻¹) 通过凸算法  
5.   更新 γᵏ
6.   if 停止准则满足 then return Xᵏ or Yᵏ
7. end for

支持三种交替凸算法：

交替最小化(AM)：直接求解子问题
层次交替最小化(HAM)：逐列优化
交替加速近端梯度法(AAPG)：结合加速和近端算子

实验设置

数据集

Digit1：1500个样本，2类，维度241的人工数据
ORL：400张面部图像，40个不同人员，每人10张不同角度图像
COIL-20：1440张图像，20个物体，来自哥伦比亚大学图像库

应用场景

**对称非负矩阵分解(SNMF)**用于聚类： $\min_{X \in \mathbb{R}^{n \times r}} \|A - XX^\top\|_F^2 + \delta_+(X)$ 其中 $\delta_+(X)$ 是非负约束的指示函数。

对比方法

AMadp/HAMadp/AAPGadp：使用文献22的自适应策略
AMagd/AAPGagd：使用文献16的算法依赖设置
AMour/HAMour/AAPGour：使用本文提出的理论设置
nAPG：直接求解非凸问题的加速近端梯度法

评价指标

聚类准确率：通过 $\text{label}(i) = \arg\max_j (Y^*)_{ij}$ 获得标签
收敛性：目标函数值变化小于 $10^{-4}$ 或迭代次数超过3000次
计算时间：墙钟运行时间

实验结果

主要结果

玩具例子验证

考虑简单问题 $\min_{x \in \mathbb{R}} \frac{1}{2}(x^2 + a)^2$ ，其惩罚形式为： $\min_{x,y \in \mathbb{R}} F(x,y,\gamma) = \frac{1}{2}(xy + a)^2 + \frac{\gamma}{2}(x-y)^2$

实验表明，当 $\gamma$ 过小时，现有自适应策略可能失败（如 $a=1, y_0=-1, \gamma_0=10^{-5}$ 时收敛到错误解），而本文方法能正确处理。

聚类性能

在三个数据集上的结果显示：

Digit1：本文方法(AMour, HAMour, AAPGour)在大多数时间点都达到更高的聚类准确率
ORL：相比对应的基线方法，本文方法收敛更快，最终准确率更高
COIL-20：类似的性能提升模式

关键发现：

本文的惩罚参数更新策略比现有方法更合理，导致更快的收敛
交替凸优化比纯非凸优化(nAPG)更有效
不同算法(AM/HAM/AAPG)的选择取决于问题规模：AM复杂度 $O(n^2r + nr^2 + r^3)$ ，HAM复杂度 $O(2n^2r + nr)$

收敛性分析

引理1：在充分下降条件和可求和条件 $\sum_{k=1}^{\infty}(\gamma_{k+1} - \gamma_k)\|X^k - Y^k\|_F^2 < \infty$ 下，序列 $\{(X^k, Y^k)\}$ 收敛到极限点 $(X^{\infty}, Y^{\infty})$ 且 $X^{\infty} = Y^{\infty}$ 。