AN EFFICIENT ALGORITHM FOR SECOND-ORDER CONE LINEAR COMPLEMENTARITY PROBLEMS

作者：Zhang, Lei-Hong; Yang, Wei Hong^*

来源：Mathematics of Computation, 2014, 83(288): 1701-1726.

DOI：10.1090/s0025-5718-2013-02795-0

• Second-order cone
• Linear complementarity problem
• globally uniquely solvable property
• bisection iteration
• Newton's iteration

Recently, the globally uniquely solvable (GUS) property of the linear transformation M is an element of R-nxn 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 linearalgebra- 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.

• 出版日期2014-7
• 单位复旦大学; 上海财经大学