Linear complementarity problem

Key takeaways

Linear complementarity problem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Linear complementarity problem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Linear complementarity problem from memory before moving on to harder problems.

Reference excerpt

In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.

Formulation Given a real matrix M and vector q, the linear complementarity problem LCP(q, M) seeks vectors z and w which satisfy the following constraints:

w , z ⩾ 0 , {\displaystyle w,z\geqslant 0,} (that is, each component of these two vectors is non-negative)

z T w = 0 {\displaystyle z^{T}w=0} or equivalently ∑ i w i z i = 0. {\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.} This is the complementarity condition, since it implies that, for all i {\displaystyle i} , at most one of w i {\displaystyle w_{i}} and z i {\displaystyle z_{i}} can be positive.

w = M z + q {\displaystyle w=Mz+q}

A sufficient condition for existence and uniqueness of a solution to this problem is that M be symmetric positive-definite. If M is such that LCP(q, M) has a solution for every q, then M is a Q-matrix. If M is such that LCP(q, M) have a unique solution for every q, then M is a P-matrix. Both of these characterizations are sufficient and necessary. The vector w is a slack variable, and so is generally discarded after z is found. As such, the problem can also be formulated as:

M z + q ⩾ 0 {\displaystyle Mz+q\geqslant 0}

z ⩾ 0 {\displaystyle z\geqslant 0}

z T ( M z + q ) = 0 {\displaystyle z^{\mathrm {T} }(Mz+q)=0} (the complementarity condition)

Convex quadratic-minimization: Minimum conditions Finding a solution to the linear complementarity problem is associated with minimizing the quadratic function

f ( z ) = z T ( M z + q ) {\displaystyle f(z)=z^{T}(Mz+q)}

subject to the constraints

M z + q ⩾ 0 {\displaystyle {Mz}+q\geqslant 0}

z ⩾ 0 {\displaystyle z\geqslant 0}

These constraints ensure that f is always non-negative. The minimum of f is 0 at z if and only if z solves the linear complementarity problem. If M is positive definite, any algorithm for solving (strictly) convex QPs can solve the LCP. Specially designed basis-exchange pivoting algorithms, such as Lemke's algorithm and a variant of the simplex algorithm of Dantzig have been used for decades. Besides having polynomial time complexity, interior-point methods are also effective in practice. Also, a quadratic-programming problem stated as minimize f ( x ) = c T x + 1 2 x T Q x {\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx} subject to A x ⩾ b {\displaystyle Ax\geqslant b} as well as x ⩾ 0 {\displaystyle x\geqslant 0} with Q symmetric is the same as solving the LCP with

q = [ c − b ] , M = [ Q − A T A 0 ] {\displaystyle q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}}

This is because the Karush–Kuhn–Tucker conditions of the QP problem can be written as:

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Linear complementarity problem

Start with the simplest possible case. Write down what Linear complementarity problem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Linear complementarity problem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Linear complementarity problem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Linear complementarity problem

In research: Linear complementarity problem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Linear complementarity problem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Linear complementarity problem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Linear algebra, Mathematical optimization, so understanding it makes those chapters shorter.
In everyday life: Look for Linear complementarity problem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Linear complementarity problem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Linear complementarity problem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Linear complementarity problem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Linear complementarity problem in simple terms?

In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.

Why does Linear complementarity problem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Linear complementarity problem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Linear complementarity problem.