Return to Article Details Linear complementarity problems solvable as linear programs

Linear complementarity problems solvable as linear programs

Zakia Kebbiche $^{*}$

July 14, 2018. Accepted: December 5, 2018. Published online: February 17, 2019.

$^{*}$ LMFN, Department of Mathematics, Faculty of Sciences, University of Ferhat Abbas, Sétif1, Algeria., e-mail: kebbichez@yahoo.fr.

In this paper, we present a theoretical and numerical study of linear complementary problems solvable as linear programs. We give several examples of linear complementarity problems which can be solved as linear programs using linear programming approaches. Also, we propose two examples solved by the simplex and Karmarkar’s method, while the most widely know method for solving linear complementarity problems “the complementarity pivoting algorithm due to Lemke" has failed to find a solution.

MSC. 90C05, 90C33.

Keywords. Linear programming, linear complementarity problem, Lemke’s algorithm, Karmarkar’s algorithm, Simplex algorithm, Hidden Z-matrix.

1 Introduction

Complementarity plays a central role in all constrained optimization problems. The linear complementarity problem is an ideal model for the development and analysis of algorithms through its different practical applications. Indeed, linear programming, convex quadratic programming, variational inequalities, partial differential equations, can be transformed into complementarity problems. In addition, many problems in mechanics, economics, chemistry and meteorology, can be modeled by complementarity.

Most algorithms proposed for the resolution of the linear complementarity problem are based on the assumption that the matrix $M$ belongs to a particular class of matrices. In 1975, Mangasarian demonstrated that the resolution of the linear complementarity problem with the class of $Z$ -matrices “real square matrix whose off-diagonal entries are nonpositive" is equivalent to that of a well-defined linear program. Moreover, in 1976 he proposed another more general class, Pang (1979) proposed to call this generalization of the class $Z$ as the class of hidden $Z$ -matrices since many of the properties which hold for the class $Z$ are preserved for the class hidden $Z$ .

As a result, some problems in mathematics and mechanics: finding the smallest element in a polyhedron, finding the convex hull of a set of points in space, the theory of optimal stopping time, problems with free boundaries, can be solved using a linear programs associated with the linear complementarity problem. Therefore, any method designed for linear programming can be used. It is known that the Lemke’s algorithm solves the linear complementarity problem only for special classes of the matrix $M$ . This problem may admit a solution but the algorithm is unable to find it. So, the goal of this work is to get more information and results from the linear complementarity problem by solving the associated linear program.

The paper is organized as following. In Section 2, we starts by defining the problem, then we give definitions and some notations. In Section 3, we discuss about existence of the solution of the linear complementarity problem where $M$ is a hidden $Z$ -matrix. Section 4 is devoted to defining the linear program associated with the linear complementarity problem. Section 5 presents special cases of hidden $Z$ -matrices. We establish in this section the conditions that the linear program must satisfy in order that each solution of the linear program is also a solution of the linear complementarity problem. In Section 6, we present several numerical examples for linear complementarity solvable as linear programs. We also present two examples when Lemke’s method has failed to find a solution to the linear complementarity problem. Finally, in Section 7 we give a conclusion of this work.

2 The problem

The linear complementarity problem, denoted $L C P (q, M),$ is that of finding a vector $z \in R^{n}$ satisfying

(L C P) {\begin{array}{r} M z + q \geq 0, \\ z \geq 0, \\ z^{t} (M z + q) = 0, \end{array}

or to show that no such vector $z$ exists. $M$ is a given $n \times n$ real matrix and $q \in R^{n} .$

Definition 1

A matrix $M \in R^{n \times n}$ is said to be a semidefinite if $\forall z \in R^{n}$ $z^{t} M z \geq 0.$

Definition 2

$M \in R^{n \times n}$ is said to be a $Z$ -matrix if its off diagonal entries are nonpositive.

Definition 3

$M \in R^{n \times n}$ is said to be a $P$ -matrix if its principal minors are positive.

Definition 4

$M \in R^{n \times n}$ is said to be a $K$ -matrix if $M$ is a $Z$ -matrix and a $P$ -matrix $.$

Definition 5

$M \in R^{n \times n}$ is said to be a $h i d d e n$ $Z$ -matrix if there exist $Z$ -matrices $X$ , $Y \in R^{n \times n}$ and two vectors $r$ and $s$ in $R_{+}^{n}$ satisfying the following conditions

{\begin{array}{r} M X = Y \\ r^{T} X + s^{T} Y > 0. \end{array}

The class of hidden $Z$ -matrices is denoted by hidden $Z$ .

Notation 6

Given a matrix $M \in R^{n \times n}$ and a vector $q \in R^{n},$ we define the feasible set of $L C P (q, M)$ by

F (q, M) = {z \in R^{n} : z \geq 0, M z + q \geq 0}

and the solution set is denoted by

S (q, M) = {z \in F (q, M) : z^{t} (M z + q) = 0} .

3 Existence of the solution of the $L C P (\lowercase q, M)$

Theorem 7

Let $M \in R^{n \times n}$ be a $h i d d e n$ $Z$ -matrix, and $F (q, M) \neq \emptyset,$ then the $L C P (q, M)$ has a solution.

To prove this theorem, we construct an equivalent linear complementarity problem as following

Lemma 8

Consider the $L C P (\tilde{q}, M)$ where $M = (\begin{array}{cc} 0 & - M^{t} \\ M & 0 \end{array}),$ $\tilde{q} = (\binom{p}{q})$ , $M \in R^{n \times n}$ is a $h i d d e n$ $Z$ -matrix, $p$ , $q \in R^{n},$ where $p = r + M^{t} s,$ $r$ and $s$ are as in Definition 5. If $(\binom{x}{y})$ $\in F (\tilde{q}, M)$ then $(I - M^{t}) y + p > 0$ .

Proof â–¼

Suppose

(\binom{x}{y}) \in F (\tilde{q}, M),

M

is a

h i d d e n

Z

-matrix, there exist

X,

Y \in Z

such that

M X = Y

and

r^{t} X + s^{t} Y > 0

where

r, s \in R_{+}^{n} .

Let

X = D - U

and

Y = D - V

where

U

and

V

are nonnegative matrices and

D

is a positive diagonal matrix. We have

\begin{aligned} 0 & < r^{t} X + s^{t} Y = (r^{t} + s^{t} M) X \\ = p^{t} (D - U) = p^{t} (D - U) + y^{t} (Y - M X) \\ = p^{t} (D - U) + y^{t} [(D - V) - M (D - U)] \\ = (- y^{t} M + p^{t}) (D - U) + y^{t} (D - V) \\ \leq (y^{t} (I - M) + p^{t}) D, \end{aligned}

since $(\binom{x}{y}) \in F (\tilde{q}, M)$ and $U, V \geq 0$ . Moreover, $[y^{t} (I - M) + p^{t}] D > 0$ lead to

(I - M^{t}) y + p > 0,

as $D$ is a positive diagonal matrix.

Proof â–¼

In the following lemma, we study the relationship between the solution of the $L C P (\tilde{q}, M)$ and the $L C P (q, M) .$

Lemma 9

The $L C P (q, M)$ has a solution if and only if the $L C P (\tilde{q}, M)$ has a solution.

Proof â–¼

Necessity. Suppose

\bar{x} \in R^{n}

solves the

L C P (q, M)

and we show that

\overset{―}{z} = (\binom{\bar{x}}{\overset{―}{y}})

is a feasible solution for the

L C P (\tilde{q}, M)

where

\overset{―}{y} = s

(

s

as in Definition 5 is a feasible solution for the

L C P (\tilde{q}, M)) .

Note that

p - M^{t} \overset{―}{y} = r + M^{t} s - M^{t} \overset{―}{y} = r + M^{t} s - M^{t} s \geq 0.

Therefore, the

L C P (\tilde{q}, M)

is feasible, further,

M

is semidefinite matrix then the

L C P (\tilde{q}, M)

has a feasible solution implies it has a complementarity solution. So the

L C P (\tilde{q}, M)

has a solution.

Sufficiency. Suppose the $L C P (\tilde{q}, M)$ has a solution. Let $\tilde{z} = (\binom{\tilde{x}}{\tilde{y}}) \in$ $S (\tilde{q}, M) .$ From the complementarity condition it follow that ${\tilde{x}}^{t} (p - M^{t} \tilde{y}) + {\tilde{y}}^{t} (q + M \tilde{x}) = 0.$ Since both terms are nonnegative, we get ${\tilde{x}}^{t} (p - M^{t} \tilde{y}) = 0$ and ${\tilde{y}}^{t} (q + M \tilde{x}) = 0.$ From Lemma 8, it follow that $\tilde{y} + (p - M^{t} \tilde{y}) > 0,$ this implies for all $i \in {1, . ., n}$ , either $(p - M^{t} \tilde{y})_{i} > 0$ or ${\tilde{y}}_{i} > 0$ . Now, if $(p - M^{t} \tilde{y})_{i} > 0$ then ${\tilde{x}}_{i} = 0$ which implies ${\tilde{x}}_{i} (q + M \tilde{x})_{i} = 0.$ If $y_{i} > 0$ then $(q + M$ $\tilde{x})_{i} = 0.$ This implies ${\tilde{x}}_{i} (q + M$ $\tilde{x})_{i} = 0$ for all $i = 1, . ., n .$ Hence, we get ${\tilde{x}}^{t} (q + M \tilde{x}) = 0$ . Therefore $\tilde{x}$ solves the $L C P (q, M) .$

Proof â–¼

[Proof of Theorem 7]

Note that feasibility of the $L C P (q, M)$ implies the feasibility of the $L C P (\tilde{q}, M)$ . Further, $M$ is semidefinite matrix implies the $L C P (\tilde{q}, M)$ has a solution. By Lemma 9, the $L C P (q, M)$ has a solution if and only if the $L C P (\tilde{q}, M)$ has a solution. Therefore feasibility of the $L C P (\tilde{q}, M)$ implies solvability of the $L C P (q, M)$ .

4 Characterization of the $L C P (\lowercase q, M)$ as a linear program

In his study of solving linear complementarity problems as linear programs, Mangasarian [ 3 ] proved the following result.

Theorem 10

Let $M \in R^{n \times n}$ be a $h i d d e n$ - $Z$ matrix and $F (q, M) \neq \emptyset,$ then the $L C P (q, M)$ has a solution which can be obtained by solving the linear program

(L P) {\begin{array}{r} min p^{t} z, \\ M z + q \geq 0, \\ z \geq 0, \end{array}

where $p = r + M^{t} s,$ $r$ and $s$ are as in Definition 5.

In order to prove this theorem, first we define the dual linear program of $(L P)$

(D) {\begin{array}{r} max - q^{t} y, \\ - M^{t} y + p \geq 0, \\ y \geq 0, \end{array}

and then we need to the following lemma.

Lemma 11

If $z$ solves the linear program $(L P)$ and if the corresponding optimal dual variable $y$ of $(D)$ satisfies $(I - M^{t}) y + p > 0,$ then $z$ solves the $L C P (q, M)$ .

Proof â–¼

We have

y^{t} (M z + q) + z^{t} (- M^{t} y + p) = y^{t} q + z^{t} p = 0

, since

y \geq 0,

M z + q \geq 0,

z \geq 0

and

(- M^{t} y + p) \geq 0,

then

y_{i} (M z + q)_{i} = 0,

z_{i} (- M^{t} y + p)_{i} = 0,

i = 1. . . n

, but

y_{i} + (- M^{t} y + p)_{i} > 0,

i = 1. . . n .

So, either

y_{i} > 0

(- M^{t} y + p)_{i} > 0,

i = 1. . . n,

and therefore

z_{i} = 0

(M z + q)_{i} = 0,

from where

z

solves the

L C P (q, M)

Proof â–¼

[Proof of Theorem 10] Since

y = s

is a dual feasible point, then,

(L P)

and

(D)

have an optimal solutions noted by

z

and

y

respectively. Let

X = D - V

and

Y = D - U,

where

V

and

U

are nonnegative matrices and

D

is a positive diagonal matrix, then

\begin{aligned} 0 < & r^{t} X + s^{t} Y = (r^{t} + s^{t} M) X \\ = & p^{t} (D - V) \\ = & p^{t} (D - V) + y^{t} (- M D + M V + D - U) (since M (D - V) = D - U) \\ = & (- y^{t} M + p^{t}) (D - V) + y^{t} (D - U) \\ \leq & (y^{t} (I - M) + p^{t}) D . \end{aligned}

Also, $(I - M^{t}) y + p > 0$ , as $- y^{t} M + p^{t} \geq 0$ , $V \geq 0,$ $y \geq 0,$ $U \geq 0)$ and $D$ is a positive diagonal matrix. According to the Lemma 11, $z$ solves the $L C P (q, M)$ .

5 Special cases of hidden Z-matrices

We establish in this section the conditions that $p$ of the linear program $(L P)$ must satisfy in order that each solution of the $(L P)$ is also a solution of the $L C P (q, M) .$

Theorem 12

(See [ 5 ] ). If $F (q, M) \neq \emptyset$ and there exist $r, s, c \in R^{n}, X, Y \in R^{n \times n}$ such that

{\begin{cases} M X = Y + q c^{t} \\ r^{t} X + s^{t} Y \geq 0 \\ r^{t} (X + C) + s^{t} (Y + C) > 0, C = diag (c) \\ X, Y \in Z, s, r, c \geq 0. \end{cases}

then the $L C P (q, M)$ has a solution which can be obtained by solving the linear program (LP) with $p = r + M^{t} s .$

Setting $c = δ e, C = δ I$ in the above where $δ$ is some positive number, we obtain

Corollary 13

(See [ 5 ] ). If $F (q, M) \neq \emptyset$ and there exist $δ \in R,$ $r, s \in R^{n}, X, Y \in R^{n \times n}$ such that

{\begin{matrix} M X = Y + δ q e^{t} \\ r^{t} X + s^{t} Y \geq 0 \\ r + s > 0, δ > 0 \\ X, Y \in Z, s, r \geq 0. \end{matrix}

then the $L C P (q, M)$ has a solution which can be obtained by solving the linear program (LP) with $p = r + M^{t} s .$

We give in Table 1 a convenient summary of some of the cases for which the $L C P (q, M)$ is solvable as linear program together with the conditions that $M$ and $p$ must satisfy.

Matrix $M$

Conditions on $M$

Vector $p$

Conditions on $p$

${M = Y X}^{- 1}$

$X, Y \in Z$ ,

$r^{t} {X + s}^{t} Y > 0$

${p = r + M}^{t} s$

$r, s \geq 0$

${M = Y X}^{- 1}$

$X \in K, Y \in Z$

$p \geq 0$

$p^{t} X > 0$

${M = Y X}^{- 1}$

$X \in Z, Y \in K$

${p = M}^{t} s \geq 0$

$s \geq 0,$

$s^{T} Y > 0$

$M$

$M \in Z$

$p$

$p > 0$

$M$

$M^{- 1} \in Z$

${p = M}^{t} s$

$s > 0$

$M$

$- M \in K$

$p = - e$ or

${p = M}^{T} e$

$e > 0$

$M$

${- M}^{- 1} \in K$

${p = - M}^{T} e$ or

$p = e$

$e > 0$

$M X = Y + δ q e^{t}$

$r^{t} {X + s}^{t} Y \geq 0,$

$X, Y \in Z, δ > 0$

${p = r + M}^{t} s$

$r + s > 0,$

$r, s \geq 0$

Table 1 Summary of some of the cases for which the

L C P (q, M)

is solvable as linear program.

6 Numerical examples

We give now some examples for which the $L C P (q, M)$ can be solved by a linear program.

Example 14

Let $M = (\begin{array}{cc} 1 & 1 \\ - 2 & - 3 \end{array})$ and $q = (\begin{matrix} - 1 \\ 6 \end{matrix}) .$ $M$ is a hidden $Z$ -matrix with $X = (\begin{array}{cc} 3 & - 3 \\ - 2 & \ 3 \end{array}) \in K$ and $Y = (\begin{array}{cc} 1 & 0 \\ 0 & - 3 \end{array}) \in Z$ . â–¡

Example 15

Consider $M = (\begin{array}{ccc} 2 & - 2 & - 2 \\ - 1 & 2 & 1 \\ - 1 & 0 & 2 \end{array})$ and $q = (\begin{matrix} 1 \\ - 3 \\ 2 \end{matrix}) .$ $M$ is a hidden $Z$ -matrix with $X = (\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & - 1 \\ - 1 & 0 & 1 \end{array}) \in K$ and $Y = (\begin{array}{ccc} 4 & - 2 & \ 0 \\ - 2 & 2 & - 1 \\ - 3 & 0 & 2 \end{array}) \in Z .$ â–¡

Example 16

Let $M = (\begin{array}{ccc} 0 & - 1 & 1 \\ - 2 & 6 & - 5 \\ 0 & - 3 & 2 \end{array})$ and $q = (\begin{matrix} 2 \\ - 1 \\ 1 \end{matrix}) .$ $M$ is a hidden $Z$ -matrix with $X = (\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & - 1 \\ 0 & 0 & - 1 \end{array}) \in$ $Z$ and $Y = (\begin{array}{ccc} 0 & - 1 & 0 \\ - 2 & 6 & - 1 \\ 0 & - 3 & 1 \end{array}) \in$ $Z .$ â–¡

Example 17

Consider $M = (\begin{array}{ccc} 0 & - 2 & - 2 \\ - 1 & 2 & 1 \\ - 1 & 0 & 2 \end{array})$ and $q = (\begin{matrix} 7 \\ - 4 \\ 1 \end{matrix}) .$ $M$ is a hidden $Z$ -matrix with $X = (\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & - 1 \\ - 1 & 0 & 1 \end{array}) \in K$ and $Y = (\begin{array}{ccc} 0 & - 2 & 0 \\ - 2 & 2 & - 1 \\ - 3 & 0 & 2 \end{array}) \in Z .$ â–¡

Example 18

Let

M = (\begin{array}{rrrrr} 2 & - 1 \\ - 1 & 2 & - 1 \\ - 1 & ⋱ & ⋱ \\ ⋱ & 2 & - 1 \\ - 1 & 2 \end{array}) \in R^{10 \times 10}, and q = (- 1, \dots, - 1)^{T} \in R^{10} .

The table below summarizes the results obtained in number of iterations $K$ and calculation time $T$ by Lemke’s algorithm (Alg. 1), the Simplex algorithm (Alg. 2) and that of Karmarkar (Alg. 3).

	Alg. 1		Alg. 2		Alg. 3
Examples	$K$	$T$	$K$	$T$	$K$	$T$
Example 14	$2$	$0.00$	$1$	$0.00$	$62$	$0.00$
Example 15	$3$	$0.00$	$2$	$0.00$	$82$	$0.01$
Example 16	$2$	$0.00$	$1$	$0.00$	$50$	$0.00$
Example 17	$2$	$0.00$	$1$	$0.00$	$72$	$0.00$
Example 18	$10$	$0.00$	$12$	$0.01$	$178$	$0.01$

Table 2 Number of iterations and computation time.

Remark 19

1) The number of iterations recorded by Alg. 1 and that of Alg. 2 is significantly lower than that obtained by the Alg. 3.

2) The calculation time obtained by the three algorithms is almost the same. â–¡

We give now two examples for which the $L C P (q, M)$ can be solved by the simplex and Karmarkar’s methods but not by Lemke’s method.

Example 20

Let $M = (\begin{array}{cc} - 1 & 1 \\ 2 & - 1 \end{array})$ and $q = (\begin{matrix} 1 \\ - 2 \end{matrix}) .$

This example satisfies the conditions of theorem $(12)$ with $r = (0, 1)^{t},$ $s = (1, 0)^{t}$ and $c = (0, 2)^{t}$ where $X = (\begin{array}{cc} - \frac{1}{2} & 0 \\ 0 & 2 \end{array}) \in Z$ and $Y = (\begin{array}{cc} \frac{1}{2} & 0 \\ - 1 & 2 \end{array}) \in Z$ .

Hence $p = r + M^{t} s = (- 1, 2)^{t},$ then the linear program associated with the $L C P (q, M)$ is

(L P) {\begin{matrix} min - z_{1} + 2 z_{2} \\ - z_{1} + z_{2} + 1 \geq 0 \\ 2 z_{1} - z_{2} - 2 \geq 0 \\ (z_{1}, z_{2}) \geq 0. \end{matrix}

The solution is $(z_{1}, z_{2})^{t} = (1, 0)^{t}$ which also solves the $L C P (q, M) .$ â–¡

Example 21

Let $M = (\begin{array}{ccc} 0 & 3 & 4 \\ 1 & - 1 & 0 \\ 0 & - 1 & - 3 \end{array})$ and $q = (\begin{matrix} - 2 \\ 0 \\ 1 \end{matrix}),$ we have

M X = Y + δ q e^{t}

with $X = (\begin{array}{ccc} - 1 & 0 & 0 \\ 0 & - 1 & 0 \\ 0 & 0 & - 1 \end{array}), Y = (\begin{array}{ccc} 2 & - 1 & - 2 \\ - 1 & 1 & 0 \\ - 1 & 0 & 2 \end{array}), δ = 1, s = e, r = 0$ .

According to Corollary 13, $p = r + M^{t} s = M^{t} e = (1, 1, 1)^{t},$ then the linear program associated with $L C P (q, M)$ is

(L P) {\begin{matrix} min z_{1} + z_{2} + z_{3} \\ \  \ 3 z_{2} + 4 z_{3} - 2 \geq 0 \\ z_{1} - z_{2} \geq 0 \\ - z_{2} - 3 z_{3} + 1 \geq 0 \\ (z_{1}, z_{2}, z_{3}) \geq 0. \end{matrix}

The optimal solution is $(z_{1}, z_{2}, z_{3})^{t} = (0.4, 0.4, 0.2)^{t}$ . â–¡

The following table summarizes the number of iterations obtained by the three algorithms ( $R$ means that Lemke’s algorithm ends with a secondary ray).

	Alg. 1	Alg. 2	Alg. 3
Example 20	$R$	$1$	$48$
Example 21	$R$	$2$	$59$

Table 3 Number of iterations obtained by the three algorithms.

Remark 22

Through the tested examples, the results obtained give a particular value to the simplex method and Karmarkar’s method. â–¡

7 Conclusion

In this paper, we have presented a class of linear complementarity problems which can be solved via linear programming approaches. From a practical point of view, we have used methods designed for linear programming (the simplex and the Karmarkar’s methods) to solve the linear program associated with the linear complementarity problem. This idea has offered us a new horizon of research concerning the resolution of a linear complementarity problem with specific classes of matrices, especially when Lemke’s algorithm has failed to find a solution.

The following questions arise: 1) The conditions assumed to test if $M$ is a hidden $Z$ -matrix are not easy to check because of the nonlinearity in the condition $r^{t} X + s^{t} Y > 0$ for unknowns $X, Y, r$ and $s$ . 2) Can we characterize all classes of matrices for which the linear complementarity problems can be solved by a linear program?