LCP Call

Chapter Contents

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:

$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

         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 .$

If H 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 w and z that satisfy

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

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 ${\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 & 1... ... & 10 \ 0 & 1 & 10 & 100 ] \ G & = & [ 1 & 2 & 3 & 4 \ 10 & 20 & 30 & 40 ] \$

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