Problem Statement of LCP

书籍 《The Linear Complementarity Problem》(Richrd W. Cottle, et. al.) 的学习笔记

---

Chapter 1 Introduction 1.1 Problem Statement

The linear complementarity problem consists in finding a vector in a finite-dimensional real vector space that satisfies a certain system of inequlities.

[z geq 0 ag{1} ]

[q + Mz geq 0 ag{2} ]

[z^T(q + Ma) = 0 ag{3} ]

We say that the LCP((q,M)) is (strictly) feasible if a (strictly) feasible vector exists.

Let

[w = q + Mz ag{4} ]

A feasible vector (z) of the LCP((q,M)) satisfies condition (3) if and only if

[z_i w_i = 0 qquad ext{for all} quad i = 1, dots, n. ag{5} ]

The varibles (z_i) and (w_i) are called a complementary pair and are said to be complements of each other.

A vector (z) satisfying (5) is called complementary. The LCP is therefore to find a vector that is both feasible and complementary; such a vector is called a solution of the LCP.

The define of (w) given above is often used in another way of expressing the LCP((q,M)), namely as the problem of finding nonnegative vectors (w) and (z) in (R^n) that satisfy (4) and (5). We write the conditions as

[w geq 0, z geq 0 ag{6} ]

[w = q + Mz ag{7} ]

[z^T w = 0 ag{8} ]

This way of representing the problem is useful in discussing algorithms for the solution of the LCP.