On the central path of semidefinite optimization: degree and worst-case convergence rate
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 and a complexity bound $O(m+n^2)2^{(m+n^2)}$ for describing the limit point, where $m$ and $n$ denote the number of affine constraints and size of the symmetric matrix, respectively. Furthermore, we provide an upper bound $O(\mu^{1/\gamma})$, with $\gamma=2^{O(m+n^2)}$, on the worst-case convergence rate of the central path.