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/2013
Entry Accepted: 01/28/2013
Entry Last Modified: 01/28/2013

Modify/Update this entry