On the central path of semidefinite optimization: degree and worst-case convergence rate

DOI10.1137/21M1419933zbMATH Open1490.14093arXiv2105.06630OpenAlexW3163178869MaRDI QIDQ5864697FDOQ5864697

Authors: Saugata Basu, Ali Mohammad Nezhad 

Publication date: 8 June 2022

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Abstract: In this paper, we investigate the complexity of the central path of semidefinite optimization through the lens of real algebraic geometry. To that end, we propose an algorithm to compute real univariate representations describing the central path and its limit point, where the limit point is described by taking the limit of central solutions, as bounded points in the field of algebraic Puiseux series. As a result, we derive an upper bound $2^{O(m+n^2)}$ on the degree of the Zariski closure of the central path, when $mu$ is sufficiently small, and for the complexity of describing the limit point, where $m$ and $n$ denote the number of affine constraints and size of the symmetric matrix, respectively. Furthermore, by the application of the quantifier elimination to the real univariate representations, we provide a lower bound $1/gamma$, with $gamma=2^{O(m+n^2)}$, on the convergence rate of the central path.

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

Recommendations

• On the Convergence of the Central Path in Semidefinite Optimization
• Limiting behavior of the central path in semidefinite optimization
• The degree of the central curve in semidefinite, linear, and quadratic programming
• Analyticity of the central path at the boundary point in semidefinite programming
• Limiting behavior of the Alizadeh–Haeberly–Overton weighted paths in semidefinite programming

zbMATH Keywords

semidefinite optimizationcentral pathquantifier eliminationsemi-algebraic setsreal univariate representation

Mathematics Subject Classification ID

Interior-point methods (90C51) Semidefinite programming (90C22) Semialgebraic sets and related spaces (14P10)

Cites Work

• Title not available (Why is that?)
• Semidefinite Programming
• Title not available (Why is that?)
• Introduction to Smooth Manifolds
• Title not available (Why is that?)
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Primal central paths and Riemannian distances for convex sets
• An exact duality theory for semidefinite programming and its complexity implications
• Semidefinite optimization
• Sums of squares, moment matrices and optimization over polynomials
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Semidefinite Optimization and Convex Algebraic Geometry
• Singular Points of Complex Hypersurfaces. (AM-61)
• Algorithms in real algebraic geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of following the central path of linear programs by linear extrapolation. II
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• Complementarity and nondegeneracy in semidefinite programming
• A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
• The central curve in linear programming
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• An Introduction to Polynomial and Semi-Algebraic Optimization
• A note on the existence of the Alizadeh-Haeberly-Overton direction for semidefinite programming
• On the Convergence of the Central Path in Semidefinite Optimization
• On the curvature of the central path of linear programming theory
• Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
• Title not available (Why is that?)
• A baby step-giant step roadmap algorithm for general algebraic sets
• Analyticity of the central path at the boundary point in semidefinite programming
• Interior Point Trajectories in Semidefinite Programming
• On weighted linear least-squares problems related to interior methods for convex quadratic programming
• Asymptotic behavior of the central path for a special class of degenerate SDP problems
• Limiting behavior of the central path in semidefinite optimization
• On the complexity of semidefinite programs
• THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS
• Algorithms in Real Algebraic Geometry: A Survey
• Exact algorithms for linear matrix inequalities
• On the identification of the optimal partition for semidefinite optimization
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Error Bounds and Singularity Degree in Semidefinite Programming
• Exact algorithms for semidefinite programs with degenerate feasible set
• The degree of the central curve in semidefinite, linear, and quadratic programming

Cited In (6)

• On a special class of regularized central paths for semidefinite programs
• On the Convergence of the Central Path in Semidefinite Optimization
• On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz
• On the existence and convergence of the central path for convex programming and some duality results
• Improved effective Łojasiewicz inequality and applications
• On the complexity of analyticity in semi-definite optimization

This page was built for publication: On the central path of semidefinite optimization: degree and worst-case convergence rate

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5864697)