LCP Call :: SAS/IML(R) 12.1 User's Guide

LCP Call

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

The LCP subroutine solves the linear complementarity problem:

$\displaystyle \mb {w}$	$\displaystyle =$	$\displaystyle \mb {Mz} + \mb {q}$
$\displaystyle \mb {w}^{\prime } \mb {z}$	$\displaystyle =$	$\displaystyle 0$
$\displaystyle \mb {w},\mb {z}$	$\displaystyle \geq$	$\displaystyle 0$

That is, given a matrix $\mb {M}$ and a vector $\mb {q}$ , the LCP subroutine computes orthogonal, nonnegative vectors $\mb {w}$ and $\mb {z}$ which satisfy the previous equations.

The input arguments to the LCP subroutine are as follows:

m

is an $m \times m$ matrix.

q

is an $m \times 1$ matrix.

epsilon

is a scalar that defines virtual zero. The default value of epsilon is 1E8.

The LCP subroutine returns the following matrices:

rc

returns one of the following scalar return codes:

rc	Termination
0	A solution is found.
1	No solution is possible.
5	The solution is numerically unstable.
6	The subroutine could not obtain enough memory.

w

returns an -element column vector

z

returns an -element column vector

The following statements give a simple example:

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

Figure 23.164: Solution to a Linear Complementarity Problem

rc
0

w
1
1

z
0
0

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

$\displaystyle \min \mb {c}^{\prime } \mb {x}$	$\displaystyle +$	$\displaystyle \frac{1}{2}\mb {x}^{\prime }\mb {Hx}$
$\displaystyle \mbox{st. } \mb {Gx}$	$\displaystyle \geq$	$\displaystyle \mb {b} ~ ~ ~ ~ ~ (\mbox{QP})$
$\displaystyle \mb {x}$	$\displaystyle \geq$	$\displaystyle 0 ~$

If $\mb {H}$ is positive semidefinite, then a solution to the Kuhn-Tucker conditions solves QP. The Kuhn-Tucker conditions for QP are

$\displaystyle \mb {c} + \mb {Hx}$	$\displaystyle =$	$\displaystyle \mu + \mb {G}^{\prime } { \lambda }$
$\displaystyle \lambda ^{\prime } (\mb {Gx}- \mb {b})$	$\displaystyle =$	$\displaystyle 0$
$\displaystyle {\mu }^{\prime } \mb {x}$	$\displaystyle =$	$\displaystyle 0$
$\displaystyle \mb {Gx}$	$\displaystyle \geq$	$\displaystyle \mb {b}$
$\displaystyle {x, \mu ,\lambda }$	$\displaystyle \geq$	$\displaystyle 0 ~$

In the linear complementarity problem, let

$\displaystyle \mb {M}$	$\displaystyle =$	$\displaystyle \left[ \begin{array}{cc} H & -G^{\prime } \\ G & 0 \\ \end{array} \right]$
$\displaystyle \mb {w}^{\prime }$	$\displaystyle =$	$\displaystyle ({\mu }^{\prime }\mb {s}^{\prime })$
$\displaystyle \mb {z}^{\prime }$	$\displaystyle =$	$\displaystyle (\mb {x}^{\prime }{ \lambda }^{\prime })$
$\displaystyle \mb {q}^{\prime }$	$\displaystyle =$	$\displaystyle (\mb {c}^{\prime } - \mb {b}) ~$

Then the Kuhn-Tucker conditions are expressed as finding $\mb {w}$ and $\mb {z}$ that satisfy

$\displaystyle \mb {w}$	$\displaystyle =$	$\displaystyle \mb {Mz} + \mb {q}$
$\displaystyle \mb {w}^{\prime }\mb {z}$	$\displaystyle =$	$\displaystyle 0$
$\displaystyle \mb {w},\mb {z}$	$\displaystyle \geq$	$\displaystyle 0 ~$

From the solution $\mb {w}$ and $\mb {z}$ to this linear complementarity problem, the solution to QP is obtained; namely, $\mb {x}$ is the primal structural variable, $\mb {s}= \mb {Gx}-\mb {b}$ the surpluses, and $\bmu$ and $\blambda$ are the dual variables. Consider a quadratic program with the following data:

$\displaystyle \mb {C}^{\prime }$	$\displaystyle =$	$\displaystyle (1 2 4 5) ~ ~ ~ ~ ~ \mb {B}^{\prime } = ( 1 1 )$
$\displaystyle \mb {H}$	$\displaystyle =$	$\displaystyle \left[ \begin{array}{rrrr} 100 & 10 & 1 & 0 \\ 10 & 100 & 10 & 1 \\ 1 & 10 & 100 & 10 \\ 0 & 1 & 10 & 100 \end{array} \right]$
$\displaystyle \mb {G}$	$\displaystyle =$	$\displaystyle \left[ \begin{array}{rrrr} 1 & 2 & 3 & 4 \\ 10 & 20 & 30 & 40 \end{array} \right]$

This problem is solved by using the LCP subroutine 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;

Figure 23.165: Solution to a Quadratic Programming Problem

rc	x
0	0.0307522
	0.0619692
	0.0929721
	0.1415983