In this paper, we extend the Ai-Zhang direction to the class of semidefinite optimization problems. We define a new wide neighborhood $\N(\tau_1,\tau_2,\eta)$ and, as usual, we utilize symmetric directions by scaling the Newton equation with special matrices. After defining the ``positive part'' and the ``negative part'' of a symmetric matrix, we solve the Newton equation with its right hand side replaced first by its positive part and then by its negative part, respectively. In this way, we obtain a decomposition of the usual Newton direction and use different step lengths for each of them. Starting with a feasible point $(X^0,y^0,S^0)$ in $\N(\tau_1,\tau_2,\eta)$, the algorithm terminates in at most $O(\eta \sqrt{\kappa_{\infty}n}\log \frac{{\rm Tr}(X^0S^0)}{\epsilon})$ iterations, where $\kappa_{\infty}$ is a parameter associated with the scaling matrix $P$ and $\epsilon$ is the required precision. To our best knowledge, when the parameter $\eta$ is a constant, this is the first large neighborhood path-following Interior Point Method (IPM) with the same complexity as small neighborhood path-following IPMs for semidefinite optimization that use the Nesterov-Todd direction. In the case when $\eta$ is chosen to be in the order of $\sqrt{n}$, our result coincides with the results for the classical large neighborhood IPMs.
Citation
Technical Report 20078-04, Advanced Optimization Lab., Department of Computing and Software, Mcmaster University, Hamilton, Ontario, Canada.