On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate

DOI10.1137/21M1419933zbMath1490.14093arXiv2105.06630OpenAlexW3163178869MaRDI QIDQ5864697

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

quantifier eliminationsemidefinite optimizationcentral pathsemi-algebraic setsreal univariate representation

Mathematics Subject Classification ID

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

Related Items

On the complexity of analyticity in semi-definite optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A baby step-giant step roadmap algorithm for general algebraic sets
• The central curve in linear 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
• Primal central paths and Riemannian distances for convex sets
• 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
• On the complexity of semidefinite programs
• A note on the existence of the Alizadeh-Haeberly-Overton direction for semidefinite programming
• Complementarity and nondegeneracy in semidefinite programming
• An exact duality theory for semidefinite programming and its complexity implications
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• Analyticity of the central path at the boundary point in semidefinite programming
• Exact algorithms for semidefinite programs with degenerate feasible set
• Asymptotic behavior of the central path for a special class of degenerate SDP problems
• On the curvature of the central path of linear programming theory
• On Weighted Linear Least-Squares Problems Related to Interior Methods for Convex Quadratic Programming
• Exact Algorithms for Linear Matrix Inequalities
• Introduction to Smooth Manifolds
• An Introduction to Polynomial and Semi-Algebraic Optimization
• Semidefinite optimization
• 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
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Interior Point Trajectories in Semidefinite Programming
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming
• THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Algorithms in Real Algebraic Geometry: A Survey
• On the Convergence of the Central Path in Semidefinite Optimization
• Semidefinite Programming
• Semidefinite Optimization and Convex Algebraic Geometry
• The degree of the central curve in semidefinite, linear, and quadratic programming
• Limiting behavior of the central path in semidefinite optimization
• Singular Points of Complex Hypersurfaces. (AM-61)
• Error Bounds and Singularity Degree in Semidefinite Programming
• On the identification of the optimal partition for semidefinite optimization
• Algorithms in real algebraic geometry

This page was built for publication: On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate