On the complexity of analyticity in semi-definite optimization
Saugata Basu, Ali Mohammad-Nezhad · arXiv (Cornell University) · 2023
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 $μ\mapsto μ^ρ$ 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(m^2+n^2m+n^4)}$, 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+n^2)}$ arithmetic operations.