Chapter Contents Previous Next
 Language Reference

## LCP Call

solves the linear complementarity problem

CALL LCP( rc, w, z, m, q<, epsilon> );

The inputs to the LCP subroutine are as follows:

m
is an m ×m matrix.

q
is an m ×1 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.

w and z
return the solution in an m-element column vector.

The LCP subroutine solves the linear complementarity problem:
Consider the following example:
   q={1, 1};
m={1 0,
0 1};
call lcp(rc,w,z,m,q);

The result is
         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:
If H is positive semidefinite, then a solution to the Kuhn-Tucker conditions solves QP. The Kuhn-Tucker conditions for QP are
In the linear complementarity problem, let
Then the Kuhn-Tucker conditions are expressed as finding w and z that satisfy
From the solution w and z to this linear complementarity problem, the solution to QP is obtained; namely, x is the primal structural variable, s = Gx-b the surpluses, and and are the dual variables. Consider a quadratic program with the following data:
This problem is solved 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^{\prime} ;
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
                RC            1 row       1 col     (numeric)

0

X             4 rows      1 col     (numeric)

0.0307522
0.0619692
0.0929721
0.1415983


 Chapter Contents Previous Next Top