  


An $O(\sqrt{n}\log \frac{(x^0)^Ts^0}{\epsilon})$ iteration primaldual pathfollowing method, based on wide neighborhoods and large updates, for monotone linear complementarity problems
Wenbao Ai (wenbaoaivip.sina.com) Abstract: In this paper we propose a new class of primaldual pathfollowing interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by adaptively choosing the step sizes, which are e.g.\ the largest possible steps before leaving a neighborhood that is even wider than a given ${\cal N}^_{\infty}$ neighborhood. The only deviation from the classical approach is that we treat the classical Newton direction as the sum of two other directions, corresponding to respectively the negative part and the positive part of the righthandside. We show that if these two directions are equipped with different and appropriate step sizes then the method enjoys the low iteration bound of $O(\sqrt{n}\log \frac{(x^0)^Ts^0}{\epsilon})$, with $n$ the dimension of the problem, $\epsilon$ the required precision, and $(x^0,s^0)$ the initial interior solution. For a predictorcorrector variant of the method, we further prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of $11/O(\sqrt{n})$. Additionally, if the problem has a strict complementarity solution then each predictor step achieves a Qquadratic convergence rate. Keywords: Monotone LCP, primaldual interior point method, wide neighborhood Category 1: Linear, Cone and Semidefinite Programming Citation: Technical Report SEEM200401, Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong Download: [PDF] Entry Submitted: 02/26/2004 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  