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

DOI10.1137/21M1419933MaRDI QIDQ5864697zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 3163006 (Why is no real title available?)
• scientific article; zbMATH DE number 3620034 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1047682 (Why is no real title available?)
• A baby step-giant step roadmap algorithm for general algebraic sets
• A note on the existence of the Alizadeh-Haeberly-Overton direction for 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
• Algorithms in real algebraic geometry
• Algorithms in real algebraic geometry: a survey
• An exact duality theory for semidefinite programming and its complexity implications
• An introduction to polynomial and semi-algebraic optimization
• Analyticity of the central path at the boundary point in semidefinite programming
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• Asymptotic behavior of the central path for a special class of degenerate SDP problems
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Complementarity and nondegeneracy in semidefinite programming
• Error bounds and singularity degree in semidefinite programming
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• Exact algorithms for linear matrix inequalities
• Interior Point Trajectories in Semidefinite Programming
• Introduction to Smooth Manifolds
• Limiting behavior of the central path in semidefinite optimization
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• On the Convergence of the Central Path in Semidefinite Optimization
• On the complexity of following the central path of linear programs by linear extrapolation. II
• On the complexity of semidefinite programs
• On the curvature of the central path of linear programming theory
• On the identification of the optimal partition for semidefinite optimization
• On weighted linear least-squares problems related to interior methods for convex quadratic programming
• Primal central paths and Riemannian distances for convex sets
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite Programming
• Semidefinite optimization
• Singular Points of Complex Hypersurfaces. (AM-61)
• Sums of squares, moment matrices and optimization over polynomials
• Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming
• THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS
• 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
• The central curve in linear programming
• The degree of the central curve in semidefinite, linear, and quadratic programming

Cited in

(7)

• On a special class of regularized central paths for semidefinite programs
• On the Convergence of the Central Path in Semidefinite Optimization
• The degree of the central curve in semidefinite, linear, and quadratic programming
• 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)