A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with $O(\sqrt{n}\log{\frac{{\rm Tr}(X^0S^0)}{\epsilon}})$ iteration complexity

Yang Li(liy99gmail.com)
Tamas Terlaky(terlakymcmaster.ca)

Abstract: 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.

Keywords: interior point methods, large neighborhood, path-following algorithm, semidefinite optimization

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical Report 20078-04, Advanced Optimization Lab., Department of Computing and Software, Mcmaster University, Hamilton, Ontario, Canada.

Download: [PDF]

Entry Submitted: 07/02/2008
Entry Accepted: 07/09/2008
Entry Last Modified: 07/02/2008

Modify/Update this entry