## 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

Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.