-

 

 

 




Optimization Online





 

AN EFFICIENT ALGORITHM FOR SECOND-ORDER CONE LINEAR COMPLEMENTARITY PROBLEMS

Lei-Hong Zhang(longzlh***at***163.com)
Weihong Yang(whyang***at***fudan.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


  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
Mathematical Optimization Society