Language Reference: LCP Call :: SAS/IML(R) 9.2 User's Guide

Language Reference

LCP Call

solves the linear complementarity problem

CALL LCP( rc, , , , $q\lt$ , epsilon> );

The inputs to the LCP subroutine are as follows:

is an

matrix.

is an

matrix.

epsilon

is a scalar defining virtual zero. The default value of epsilon is 1.0E-8.

rc

returns one of the following scalar return codes:

0: solution found
1: no solution possible
5: solution is numerically unstable
6: subroutine could not obtain enough memory

and

return the solution in an

-element column vector.

The LCP subroutine solves the linear complementarity problem:

$w & = & {mz} + q \ w^' z & = & 0 \ w,z & \geq & 0$

Consider the following example:

  
    q={1, 1}; 
    m={1 0, 
       0 1}; 
   call lcp(rc,w,z,m,q);

The result is as follows:

  
          RC            1 row       1 col     (numeric) 
  
                                    0 
  
  
          W             2 rows      1 col     (numeric) 
  
                                    1 
                                    1 
  
  
          Z             2 rows      1 col     (numeric) 
  
                                    0 
                                    0

The next example shows the relationship between quadratic programming and the linear complementarity problem. Consider the linearly constrained quadratic program:

$\min c^' x & + & \frac{1}2{x}^'{hx} \ {st. } {gx} & \geq & b ({qp}) \ x & \geq & 0$

is positive semidefinite, then a solution to the Kuhn-Tucker conditions solves QP. The Kuhn-Tucker conditions for QP are

$c + {hx} & = & \mu + g^' {\lambda} \ \lambda ^' ({gx}- b) & = & 0 \ {\mu }^' x & = & 0 \ {gx} & \geq & b \ {x, \mu ,\lambda } & \geq & 0$

In the linear complementarity problem, let

$m & = & [ h & -g^' \ g & 0 \ ] \ w^' & = & ({\mu }^'s^') \ z^' & = & (x^'{\lambda}^') \ q^' & = & (c^' - b)$

Then the Kuhn-Tucker conditions are expressed as finding

and

that satisfy

$w & = & {mz} + q \ w^'z & = & 0 \ w,z & \geq & 0$

From the solution

and

to this linear complementarity problem, the solution to QP is obtained; namely,

is the primal structural variable,

the surpluses, and ${\mu}$ and ${\lambda}$ are the dual variables. Consider a quadratic program with the following data:

$c^' & = & (1 2 4 5) b^' = ( 1 1 ) \ h & = & [ 100 & 10 & 1 & 0 \ 10 & 100 ... ... 0 & 1 & 10 & 100 ] \ g & = & [ 1 & 2 & 3 & 4 \ 10 & 20 & 30 & 40 ] \$

This problem is solved by using the LCP subroutine in PROC IML as follows:

  
       /*---- Data for the Quadratic Program -----*/ 
    c={1,2,3,4}; 
    h={100 10 1 0, 10 100 10 1, 1 10 100 10, 0 1 10 100}; 
    g={1 2 3 4, 10 20 30 40}; 
    b={1, 1}; 
  
       /*----- Express the Kuhn-Tucker Conditions as an LCP ----*/ 
    m=h||-g`; 
    m=m//(g||j(nrow(g),nrow(g),0)); 
    q=c//-b ; 
  
       /*----- Solve for a Kuhn-Tucker Point --------*/ 
    call lcp(rc,w,z,m,q); 
  
       /*------ Extract the Solution to the Quadratic Program ----*/ 
    x=z[1:nrow(h)]; 
    print rc x;

The printed solution is as follows:

  
                 RC            1 row       1 col     (numeric) 
  
                                           0 
  
                 X             4 rows      1 col     (numeric) 
  
                                   0.0307522 
                                   0.0619692 
                                   0.0929721 
                                   0.1415983

Top of Page