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.
翻译:我们以跟踪低级矩阵因子化(又称Burer-Monteiro因子化)的解决方案轨迹为基础,通过路径跟踪程序,为时间变化的半无限制程序(TV-SDPs)提供了一个在线算法。在那里,预测者-更正者算法解决了线性系统序列。这需要引入横向空间限制以确保低级因子化的当地弹入。该方法为最初的TV-SDP问题生成了一系列近似解决方案,我们为此显示,如果适当初始化,它们接近于最佳解决方案路径。 用于时间变化的Max-Cut SDP放松的数值实验显示了在运行时间与离场内点方法相比跟踪电视-SDPs的拟议方法的计算优势。