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

central pathquantifier eliminationreal univariate representationsemi-algebraic setssemidefinite optimization

Mathematics Subject Classification ID

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

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

• 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
• Complementarity and nondegeneracy in semidefinite programming
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• 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
• 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?)
• 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 complexity of following the central path of linear programs by linear extrapolation. II
• On the complexity of semidefinite programs
• On the Convergence of the Central Path in Semidefinite Optimization
• 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
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite Programming
• 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 curve in linear programming
• THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS
• The degree of the central curve in semidefinite, linear, and quadratic 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

Cited in

(9)

• On the existence and convergence of the central path for convex programming and some duality results
• On the Convergence of the Central Path in Semidefinite Optimization
• The degree of the central curve in semidefinite, linear, and quadratic programming
• On the complexity of analyticity in semi-definite optimization
• On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz
• Improved effective Łojasiewicz inequality and applications
• Semi-algebraic structure and central paths in nonlinear optimization
• Three different views on barrier functions in conic optimization
• On a special class of regularized central paths for semidefinite programs

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)