Linear complementarity problem: Difference between revisions

Revision as of 03:36, 29 January 2011

Revision as of 14:03, 29 January 2011

Line 37:

* <math>\mathbf{q} = \left[\begin{array}{c}\mathbf{c}\\-\mathbf{b}\end{array}\right]</math>

* <math>\mathbf{M} = \left[\begin{array}{cc} \mathbf{Q} & -\mathbf{A}^{T}\\ \mathbf{A} & 0\end{array}\right]</math>

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} + \mathbf{c}</math>

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

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

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

...being <math> \mathbf{\muv} </math> the multipliers on the inequalitynon-negativity constraints, <math> \mathbf{v\mu} </math> the multipliers on the non-negativityinequality constraints, and <math> \mathbf{s} {=}</math> \mathbf{A}the slack variables for the inequality constraints. The forth condition derives from the complementarity of each group of variables (<math>\mathbf{x} -, \mathbf{bs} </math>) thewith slackits variablesset forof theKKT inequalitymultipliers constraints(<math>\mathbf{v}, \mathbf{\mu}</math>).

In that case,

Line 42 ⟶ 55:

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

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

...being <math>\mathbf{\mu}</math> the multipliers on the inequality constraints, <math>\mathbf{v}</math> the multipliers on the non-negativity constraints, and <math> \mathbf{s} {=} \mathbf{A}\mathbf{x} - \mathbf{b} </math> the slack variables for the inequality constraints.

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