Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
From MaRDI portal
Publication:6136653
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 48687 (Why is no real title available?)
- scientific article; zbMATH DE number 1534295 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- A New Unblocking Technique to Warmstart Interior Point Methods Based on Sensitivity Analysis
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A remark on the rank of positive semidefinite matrices subject to affine constraints
- A strengthened Barvinok-Pataki bound on SDP rank
- A warm-start approach for large-scale stochastic linear programs
- Adjoint-based predictor-corrector sequential convex programming for parametric nonlinear optimization
- An Algorithm for Degenerate Nonlinear Programming with Rapid Local Convergence
- An Interior-Point Method for Minimizing the Maximum Eigenvalue of a Linear Combination of Matrices
- Bottleneck Problems and Dynamic Programming
- Complementarity and nondegeneracy in semidefinite programming
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Introduction to Numerical Continuation Methods
- Lectures on convex optimization
- Lipschitz analysis of generalized phase retrievable matrix frames
- Local minima and convergence in low-rank semidefinite programming
- Low-rank optimization on the cone of positive semidefinite matrices
- Near optimal control of queueing networks over a finite time horizon
- On Computing the Nonlinearity Interval in Parametric Semidefinite Optimization
- On implementing a primal-dual interior-point method for conic quadratic optimization
- On interior-point warmstarts for linear and combinatorial optimization
- On parametric semidefinite programming
- On the Burer-Monteiro method for general semidefinite programs
- On the behavior of the homogeneous self-dual model for conic convex optimization
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Online learning of quantum states
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Perturbation bounds for matrix square roots and Pythagorean sums
- Problems of distance geometry and convex properties of quadratic maps
- Quotient geometry with simple geodesics for the manifold of fixed-rank positive-semidefinite matrices
- Rank optimality for the Burer-Monteiro factorization
- Reoptimization With the Primal-Dual Interior Point Method
- Scalable low-rank semidefinite programming for certifiably correct machine perception
- Separated continuous conic programming: strong duality and an approximation algorithm
- Time-Varying Semidefinite Programs
- Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems
This page was built for publication: Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136653)
