Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


An efficient algorithm for second-order cone linear complementarity problems

Authors: Lei-Hong Zhang and Wei Hong Yang
Journal: Math. Comp. 83 (2014), 1701-1726
MSC (2010): Primary 90C33, 65K05; Secondary 65F99
Published electronically: November 7, 2013
MathSciNet review: 3194127
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Recently, the globally uniquely solvable (GUS) property of the linear transformation $ 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$ 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 $ 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C33, 65K05, 65F99

Retrieve articles in all journals with MSC (2010): 90C33, 65K05, 65F99

Additional Information

Lei-Hong Zhang
Affiliation: Department of Applied Mathematics, Shanghai University of Finance and Economics, 777 Guoding Road, Shanghai 200433, People’s Republic of China

Wei Hong Yang
Affiliation: Corresponding author. School of Mathematical Sciences, Fudan University, Shanghai, 200433, People’s Republic of China

Keywords: Second-order cone, Linear complementarity problem, globally uniquely solvable property, bisection iteration, Newton's iteration
Received by editor(s): June 30, 2010
Received by editor(s) in revised form: September 1, 2011, and October 30, 2012
Published electronically: November 7, 2013
Additional Notes: The research of the first author was supported by the Natural Science Foundation of China, NSFC-11101257.
The research of the second author was supported by the Natural Science Foundation of China, NSFC-10801040.
Article copyright: © Copyright 2013 American Mathematical Society