  


AN EFFICIENT ALGORITHM FOR SECONDORDER CONE LINEAR COMPLEMENTARITY PROBLEMS
LeiHong Zhang(longzlh163.com) Abstract: Recently, the globally uniquely solvable (GUS) property of the linear transformation $M\in R^{n\times n}$ in the secondorder cone linear complementarity problem (SOCLCP) receives much attention and has been studied substantially. Yang and Yuan [30] contributed a new characterization of the GUS property of the linear transformation, which is formulated by basic linearalgebrarelated properties. In this paper, we consider efficient numerical algorithms to solve the SOCLCP where the linear transformation M has the GUS property. By closely relying upon the new characterization of the GUS property, a globally convergent bisection method is developed in which each iteration can be implemented using only $2n^2$ flops. Moreover, we also propose an efficient Newton method to accelerate the bisection algorithm. An attractive feature of this Newton method is that each iteration only requires $5n^2$ flops and converges quadratically. These two approaches make good use of the special structure contained in the SOCLCP and can be effectively combined to yield a fast and efficient bisectionNewton method. Numerical testing is carried out and very encouraging computational experiments are reported. Keywords: Secondorder cone, Linear complementarity problem, Globally uniquely solvable property, Bisection iteration, Newton's iteration Category 1: Complementarity and Variational Inequalities Category 2: Linear, Cone and Semidefinite Programming (SecondOrder Cone Programming ) Citation: Mathematics of Computation, to appear. Download: [PDF] Entry Submitted: 01/28/2013 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  