- AN EFFICIENT ALGORITHM FOR SECOND-ORDER CONE LINEAR COMPLEMENTARITY PROBLEMS Lei-Hong Zhang(longzlh163.com) Weihong Yang(whyangfudan.edu.cn) Abstract: Recently, the globally uniquely solvable (GUS) property of the linear transformation $M\in R^{n\times n}$ in the second-order 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 linear-algebra-related 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 bisection-Newton method. Numerical testing is carried out and very encouraging computational experiments are reported. Keywords: Second-order 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 (Second-Order Cone Programming ) Citation: Mathematics of Computation, to appear. Download: [PDF]Entry Submitted: 01/28/2013Entry Accepted: 01/28/2013Entry Last Modified: 01/28/2013Modify/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 Optimization Online is supported by the Mathematical Optmization Society.