Linear complementarity problem: Difference between revisions

Revision as of 14:05, 29 January 2011

Revision as of 02:55, 30 January 2011

Line 40:

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

* <math>\mathbf{v} = \mathbf{Q} \mathbf{x} - \mathbf{A}^{T} \mathbf{mu\lambda} + \mathbf{c}</math>

* <math>\mathbf{s} = \mathbf{A} \mathbf{x} - \mathbf{b}</math>

* <math>\mathbf{x}, \mathbf{\mulambda}, \mathbf{v}, \mathbf{s} \ge \mathbf{0}</math>

* <math>\mathbf{x}^{T}\mathbf{v} + \mathbf{\mulambda}^{T}\mathbf{s} = \mathbf{0}</math>

...being <math> \mathbf{v} </math> the multipliers on the non-negativity constraints,<math> \mathbf{\mulambda} </math> the multipliers on the inequality constraints, and <math> \mathbf{s} </math> the slack variables for the inequality constraints. The fourth condition derives from the complementarity of each group of variables (<math>\mathbf{x}, \mathbf{s}</math>) with its set of KKT multipliers (<math>\mathbf{v}, \mathbf{\mulambda}</math>).

In that case,

*: <math>\mathbf{z} = \left[\begin{array}{c}\mathbf{x}\\ \mathbf{\mulambda}\end{array}\right]</math>

*: <math>\mathbf{w} = \left[\begin{array}{c}\mathbf{v}\\ \mathbf{s}\end{array}\right]</math>

If the non-negativity constraint on the <math>\mathbf{x}</math> is relaxed, the dimensionality of the LCP problem can be reduced to the number of the inequalities, as long as <math>\mathbf{Q}</math> is non-singular (which is guaranteed if it is [[Positive-definite matrix|positive definite]]). The multipliers <math>\mathbf{v}</math> are no longer present, and the first KKT conditions can be rewritten as:

* <math>\mathbf{Q} \mathbf{x} = \mathbf{A}^{T} \mathbf{\lambda} - \mathbf{c}</math>

or:

: <math> \mathbf{x} = \mathbf{Q}^{-1}(\mathbf{A}^{T} \mathbf{\lambda} - \mathbf{c})</math>

pre-multiplying the two sides by <math>\mathbf{A}</math> and subtracting <math>\mathbf{b}</math> we obtain:

: <math> \mathbf{A} \mathbf{x} - \mathbf{b} = \mathbf{A} \mathbf{Q}^{-1}(\mathbf{A}^{T} \mathbf{\lambda} - \mathbf{c}) -\mathbf{b} </math>

The left side, due to the second KKT condition, is <math>\mathbf{s}</math>. Substituting and reordering:

: <math> \mathbf{s} = (\mathbf{A} \mathbf{Q}^{-1} \mathbf{A}^{T}) \mathbf{\lambda} + (- \mathbf{A} \mathbf{Q}^{-1} \mathbf{c} - \mathbf{b} )</math>

Calling now <math> \mathbf{M} = (\mathbf{A} \mathbf{Q}^{-1} \mathbf{A}^{T})</math> and <math> \mathbf{q} = (- \mathbf{A} \mathbf{Q}^{-1} \mathbf{c} - \mathbf{b})</math> we have an LCP, due to the relation of complementarity between the slack variables <math>\mathbf{s}</math> and their multipliers <math>\mathbf{\lambda}</math>. Once we solve it, we may obtain the value of <math>\mathbf{x}</math> from <math>\mathbf{\lambda}</math> through the first KKT condition.

Finally, it is also possible to handle additional equality constraints:

: <math>\mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq} </math>

This introduces a vector of Lagrange multipliers <math>\mathbf{\mu}</math>, with the same dimension as <math>\mathbf{b}_{eq}</math>.

It is easy to verify that the <math>\mathbf{M}</math> and <math>\mathbf{q}</math> for the LCP system <math> \mathbf{s} = \mathbf{M} \mathbf{\lambda} + \mathbf{q} </math> are now expressed as:

: <math> \mathbf{M} = (\left[\begin{array}{cc}\mathbf{A} & \mathbf{0}\end{array}\right] \left[\begin{array}{cc} \mathbf{Q} & \mathbf{A}_{eq}^{T}\\ -\mathbf{A}_{eq} & \mathbf{0}\end{array}\right]^{-1} \left[\begin{array}{cc}\mathbf{A}^{T} \\ \mathbf{0}\end{array}\right])</math>

: <math> \mathbf{q} = (- \left[\begin{array}{cc}\mathbf{A} & \mathbf{0}\end{array}\right] \left[\begin{array}{cc} \mathbf{Q} & \mathbf{A}_{eq}^{T}\\ -\mathbf{A}_{eq} & \mathbf{0}\end{array}\right]^{-1} \left[\begin{array}{c}\mathbf{c}\\ \mathbf{b}_{eq}\end{array}\right] - \mathbf{b})</math>

From <math>\mathbf{\lambda}</math> we can now recover the values of both <math>\mathbf{x}</math> and the multiplier of equalities <math>\mathbf{\mu}</math>:

<math>\left[\begin{array}{c}\mathbf{x}\\ \mathbf{\mu}\end{array}\right] = \left[\begin{array}{cc} \mathbf{Q} & \mathbf{A}_{eq}^{T}\\ -\mathbf{A}_{eq} & \mathbf{0}\end{array}\right]^{-1} \left[\begin{array}{c} \mathbf{A}^{T}\mathbf{\lambda}-\mathbf{c}\\-\mathbf{b}_{eq}\end{array}\right] </math>

In fact, most QP solvers work on the LCP formulation, including the [[interior point method]], principal / complementarity pivoting and [[active set]] methods.