This document discusses several applications that can be formulated as linear complementarity problems (LCPs), including:
1) Optimality conditions for linear programs (LPs) and quadratic programs (QPs) can be written as LCPs.
2) Nash equilibria in bimatrix games correspond to solutions of a related LCP.
3) Market equilibrium problems can be formulated as LCPs under suitable conditions on demand functions.
4) Finding the breakpoints of the lower envelope of a convex hull in the plane can be formulated as an LCP.
This document discusses several applications that can be formulated as linear complementarity problems (LCPs), including:
1) Optimality conditions for linear programs (LPs) and quadratic programs (QPs) can be written as LCPs.
2) Nash equilibria in bimatrix games correspond to solutions of a related LCP.
3) Market equilibrium problems can be formulated as LCPs under suitable conditions on demand functions.
4) Finding the breakpoints of the lower envelope of a convex hull in the plane can be formulated as an LCP.
This document discusses several applications that can be formulated as linear complementarity problems (LCPs), including:
1) Optimality conditions for linear programs (LPs) and quadratic programs (QPs) can be written as LCPs.
2) Nash equilibria in bimatrix games correspond to solutions of a related LCP.
3) Market equilibrium problems can be formulated as LCPs under suitable conditions on demand functions.
4) Finding the breakpoints of the lower envelope of a convex hull in the plane can be formulated as an LCP.
This document discusses several applications that can be formulated as linear complementarity problems (LCPs), including:
1) Optimality conditions for linear programs (LPs) and quadratic programs (QPs) can be written as LCPs.
2) Nash equilibria in bimatrix games correspond to solutions of a related LCP.
3) Market equilibrium problems can be formulated as LCPs under suitable conditions on demand functions.
4) Finding the breakpoints of the lower envelope of a convex hull in the plane can be formulated as an LCP.
The Linear Complementarity Problem (LCP) (q, M ) is defined as
follows: Given a real n n matrix M and an n-vector q, find z Rn such that z 0, q + M z 0, z T(q + M z) = 0. Define the mapping F (z) := q + M z. Then F is an affine transformation from Rn into itself.
Some notation
Given the LCP (q, M ) we write
FEA(q, M ) = {z : q + M z 0,
z 0}
and SOL(q, M ) = {z : q + M z 0,
z 0,
z T(q + M z) = 0.}
These are the feasible set (region) and solution set of the LCP (q, M ), respectively. Note that if FEA(q, M ) 6= , it is a closed polyhedral set.
How do such problems arise?
Optimality criterion for Linear Programming (LP) Consider the LP (P)
minimize cTx subject to Ax b x 0.
According to the theory of linear programming, a vector x is optimal
for (P) if and only if it is feasible and there exists a vector y such that yTA cT,
y 0,
yT(A x b) = 0,
( y TA cT) x = 0.
Now arrange these conditions as follows:
u =
ATy 0
c +
v = b + Ax x 0, xTu = 0, Next define " # u w= , v
q=
"
c b
0 y0 y Tv = 0.
M=
"
0 A A
z=
"
x y
The optimality conditions of the LP then become the LCP (q, M ).
Optimality conditions for Quadratic Programming (QP)
Consider the QP (P)
minimize cTx + 12 xTQx
subject to Ax b x 0.
According to the Karush-Kuhn-Tucker (KKT) Theorem, if the vector
x is a local minimizer for (P), there exists a vector y such that c+Q xATy 0,
y 0,
yT(A xb) = 0,
xT(c+Q xATy) = 0.
If we assemble these conditions along with the feasibility of the vector
x, we obtain the LCP (q, M ) where " # # " # " # " T u x c Q A w= , z= , q= . , M= A 0 v y b Remark. The above necessary conditions of optimality for QP are also
sufficient for (global) optimality when Q is positive semi-definite.
Note that if Q is positive semi-definite, then so is " # T Q A M= . A 0
Bimatrix Games as LCPs
The initial set up
Let A and B denote two m n matrices.
These are payoff matrices for Players I and II, respectively. m n Let m = {x R+ : eTx = 1} and n = {y R+ : eTy = 1}.
If x m and y n , the expected losses of Players I and II are,
respectively: xTAy and xTBy. Let (A, B) denote the corresponding two person game.
Nash Equilibrium Point of (A, B)
The pair (x, y ) m n is a Nash Equilibrium Point (NEP) for
(A, B) if (x)TAy xTAy
for all x m
(x)TBy (x)TBy for all y n
It is crucial to note that given (x, y ) m n, each of the vectors x, y is optimal in a simple linear program defined in terms of the other. The LPs are: minimize (Ay )Tx subject to eTx = 1, x 0 and minimize (B Tx)Ty subject to eTy = 1, y 0
Let E be the m n matrix whose entries are all 1. For a suitable
scalar > 0, all the entries of the matrices A + E and B + E are positive. It is easy to see that (A, B) and (A + E, B + E) have the same equilibrium points (if any). Thus, it is not restrictive to assume that A and B are (elementwise) positive matrices.
Now consider the LCP
u = em + Ay 0, x 0, xTu = 0 v = en + B Tx 0, y 0, y Tv = 0 In this case, we have " # # " u em w= , , q= en v
M=
"
0 A BT 0
z=
"
where em = (1, . . . , 1) Rm
en = (1, . . . , 1) Rn .
We wish to show that
to every solution of this LCP, there corresponds a Nash equilibrium point of (A, B)and vice versa.
The correspondences are as follows:
If (x, y ) is a Nash equilibrium of (A, B), then (x0, y 0) = (x/(x)TBy , y /(x)TAy ) solves the LCP (q, M ) given above. If (x0, y 0) solves the LCP (above), then (x, y ) = (x0/eTmx0, y 0/eTn y 0 ) is a Nash equilibrium point for (A, B).
A Market Equilibrium Problem
Here we seek to determine prices at which there is a balance between
supplies and demands. The supply side minimize cTx subject to Ax b Bx r x0 The demand side r = Q(p) = Dp + d Equilibration p =
Formulation as an Equilibrium Problem
y = c ATv B T 0, xT 0, (x)Ty = 0 u = b + Ax 0,
v 0, (v )Tu = 0
= r + Bx 0,
0, ( )T = 0
Substitute Dp + d for r and for p.
Then we get the LCP (q, M ) with
c x 0 AT B T q = b M =A 0 0 and z = v B 0 D d
What sort of matrix is D? Having it be negative (semi)definite and
symmetric would be nice.
Convex Hulls in the Plane
2 Given {(xi, yi)}n+1 i=0 R find the extreme points and the facets of their convex hull and the order in which they appear.
First find the lower envelope of the convex hull.
If xi = xj and yi yj , we can ignore (xj , yj ) without changing the lower envelope. Thus, assume x0 < x1 < < xn < xn+1. In practice, this would require sorting. The lower envelope is a piecewise linear convex function f (x), the pointwise maximum of all convex functions g(x) such that g(xi) yi for i = 0, 1, . . . , n + 1.
Define ti = f (xi) and let zi = yi ti, for i = 0, 1, . . . , n + 1.
Note that z0 = zn+1 = 0. If (xi, yi) is a breakpoint, then ti = yi and zi = 0. The segment of the lower envelope between (xi1, ti1) and (xi, ti) has a different slope than the segment between (xi, ti ) and (xi+1, ti+1). Since f (x) is convex, the former (left-hand) segment must have a smaller slope than the latter (right-hand) segment. Hence strict inequality holds in ti ti1 ti+1 ti
. xi xi1 xi+1 xi If zi > 0, then (xi, yi) cannot be a breakpoint of f (x). In that case, equality holds in the inequality above.
The vector z = {zi}ni=1 must solve the LCP (q, M )
and M Rnn are defined by
i1 + i
i and mij = qi = i i1
where q Rn if j = i, if j = i + 1, if j = i 1, otherwise,
and where i = 1/(xi+1 xi) and i = i(yi+1 yi) for i = 0, . . . , n. This LCP has a unique solution. The matrix M associated with this LCP has several nice properties which can be exploited to produce very efficient solution procedures.
