Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization

DOI10.1137/22M1529762arXiv2210.08387OpenAlexW4390540407MaRDI QIDQ6136653FDOQ6136653

Authors: Mareike Dressler, Vyacheslav Kungurtsev, Jakub Mareček, André Uschmajew 

Publication date: 17 January 2024

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2210.08387

zbMATH Keywords

nonlinear programmingsemidefinite programmingparametric optimizationNewton type methodstime-varying constrained optimization

Mathematics Subject Classification ID

Nonlinear programming (90C30) Semidefinite programming (90C22) Sensitivity, stability, parametric optimization (90C31) Newton-type methods (49M15)

Cites Work

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Conic optimization via operator splitting and homogeneous self-dual embedding
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems
• On interior-point warmstarts for linear and combinatorial optimization
• A New Unblocking Technique to Warmstart Interior Point Methods Based on Sensitivity Analysis
• Introduction to Numerical Continuation Methods
• Handbook of semidefinite programming. Theory, algorithms, and applications
• On implementing a primal-dual interior-point method for conic quadratic optimization
• Local minima and convergence in low-rank semidefinite programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Problems of distance geometry and convex properties of quadratic maps
• Complementarity and nondegeneracy in semidefinite programming
• On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
• Reoptimization With the Primal-Dual Interior Point Method
• A warm-start approach for large-scale stochastic linear programs
• An Algorithm for Degenerate Nonlinear Programming with Rapid Local Convergence
• Title not available (Why is that?)
• Low-rank optimization on the cone of positive semidefinite matrices
• Bottleneck Problems and Dynamic Programming
• Title not available (Why is that?)
• Near optimal control of queueing networks over a finite time horizon
• A remark on the rank of positive semidefinite matrices subject to affine constraints
• Adjoint-Based Predictor-Corrector Sequential Convex Programming for Parametric Nonlinear Optimization
• On parametric semidefinite programming
• Lectures on convex optimization
• An Interior-Point Method for Minimizing the Maximum Eigenvalue of a Linear Combination of Matrices
• Separated continuous conic programming: strong duality and an approximation algorithm
• On the behavior of the homogeneous self-dual model for conic convex optimization
• Perturbation bounds for matrix square roots and Pythagorean sums
• Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
• Quotient Geometry with Simple Geodesics for the Manifold of Fixed-Rank Positive-Semidefinite Matrices
• On the Burer-Monteiro method for general semidefinite programs
• A strengthened Barvinok-Pataki bound on SDP rank
• Online learning of quantum states
• Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception
• Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem
• Time-Varying Semidefinite Programs
• Rank Optimality for the Burer--Monteiro Factorization
• Lipschitz Analysis of Generalized Phase Retrievable Matrix Frames
• On Computing the Nonlinearity Interval in Parametric Semidefinite Optimization

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)