An efficient algorithm for second-order cone linear complementarity problems
Lei‐Hong Zhang, Wei Hong Yang · Mathematics of Computation · 2013
Recently, the globally uniquely solvable (GUS) property of the linear transformation M ∈ R n × n M\in \mathbb {R}^{n\times n} in the second-order cone linear complementarity problem (SOCLCP) receives much attention and has been studied substantially. Yang and Yuan 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 M has the GUS property. By closely relying on the new characterization of the GUS property, a globally convergent bisection method is developed in which each iteration can be implemented using only 2 n 2 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 5 n 2 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.