On the complexity of analyticity in semi-definite optimization

2023/01/16 by Basu, Saugata, Mohammad-Nezhad, Ali · 2 citations
#14P10 #90C22 #90C51 #Algebraic Geometry (math.AG) #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2301.06257

Abstract

It is well-known that the central path of semi-definite optimization, unlike linear optimization, has no analytic extension to μ= 0 in the absence of the strict complementarity condition. In this paper, we show the existence of a positive integer ρ by which the reparametrization μ↦ μ^ρ recovers the analyticity of the central path at μ= 0. We investigate the complexity of computing ρ using algorithmic real algebraic geometry and the theory of complex algebraic curves. We prove that the optimal ρ is bounded by 2^O(m2+n2m+n4), where n is the matrix size and m is the number of affine constraints. Our approach leads to a symbolic algorithm, based on the Newton-Puiseux algorithm, which computes a feasible ρ using 2^O(m+n2) arithmetic operations.

Cited by

• Convergence-Guaranteed Algorithms for l1/2-Regularized Quadratic Programs with Assignment Constraints
• On the convergence of critical points on real algebraic sets and applications to optimization

Related

• On the central path of semidefinite optimization: Degree and worst-case convergence rate
• Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis
• Solving rank-constrained semidefinite programs in exact arithmetic
• The degree of the central curve in semidefinite, linear, and quadratic programming
• A Lagrangian relaxation view of linear and semidefinite hierarchies