论文标题
随时间变化的半决赛编程：遵循式蒙特利罗分解后的路径
Time-Varying Semidefinite Programming: Path Following a Burer-Monteiro Factorization
论文作者
论文摘要
我们基于在路径牢固过程中的低级矩阵分解（也称为burer-montrix分解，也称为burer-monteiro分解）的跟踪，我们提出了一种用于时变半段程序（TV-SDP）的在线算法。在那里，预测型 - 校正算法解决了一系列线性化系统。这需要引入水平空间约束，以确保低级别分解的局部注射率。该方法为原始TV-SDP问题产生了一系列近似解决方案，为此，我们证明它们在适当初始化的情况下保持接近最佳解决方案路径。与现成的内部点方法相比，针对时间变化的最大切割SDP松弛的数值实验证明了根据运行时跟踪电视SDP的建议方法的计算优势。
We present an online algorithm for time-varying semidefinite programs (TV-SDPs), based on the tracking of the solution trajectory of a low-rank matrix factorization, also known as the Burer-Monteiro factorization, in a path-following procedure. There, a predictor-corrector algorithm solves a sequence of linearized systems. This requires the introduction of a horizontal space constraint to ensure the local injectivity of the low-rank factorization. The method produces a sequence of approximate solutions for the original TV-SDP problem, for which we show that they stay close to the optimal solution path if properly initialized. Numerical experiments for a time-varying max-cut SDP relaxation demonstrate the computational advantages of the proposed method for tracking TV-SDPs in terms of runtime compared to off-the-shelf interior point methods.
