  It is well-known that the central path of semi-definite optimization, unlike
linear optimization, has no analytic extension to $\mu = 0$ in the absence of
the strict complementarity condition. In this paper, we show the existence of a
positive integer $\rho$ by which the reparametrization $\mu \mapsto \mu^{\rho}$
recovers the analyticity of the central path at $\mu = 0$. We investigate the
complexity of computing $\rho$ using algorithmic real algebraic geometry and
the theory of complex algebraic curves. We prove that the optimal $\rho$ 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 $\rho$ using
$2^{O(m+n^2)}$ arithmetic operations.

Algebraic Geometry;Optimization and Control