  


A new class of large neighborhood pathfollowing interior point algorithms for semidefinite optimization with $O(\sqrt{n}\log{\frac{{\rm Tr}(X^0S^0)}{\epsilon}})$ iteration complexity
Yang Li(liy99gmail.com) Abstract: In this paper, we extend the AiZhang 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 pathfollowing Interior Point Method (IPM) with the same complexity as small neighborhood pathfollowing IPMs for semidefinite optimization that use the NesterovTodd 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, pathfollowing algorithm, semidefinite optimization Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Technical Report 2007804, Advanced Optimization Lab., Department of Computing and Software, Mcmaster University, Hamilton, Ontario, Canada. Download: [PDF] Entry Submitted: 07/02/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  