- | ||||
|
![]()
|
AN EFFICIENT ALGORITHM FOR SECOND-ORDER CONE LINEAR COMPLEMENTARITY PROBLEMS
Lei-Hong Zhang(longzlh 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 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 | |
![]() |