Content deleted Content added
→External links: Added external reference to LCPSolve.py in OpenOpt >= 0.32 |
→Relation to quadratic programming: added clarification on the conversion QP -> LCP |
||
Line 31:
If '''M''' is [[Positive-definite matrix|positive definite]], any algorithm for solving (convex) [[Quadratic programming|QPs]] can of course be used to solve the LCP. However, there also exist more efficient, specialized algorithms, such as [[Lemke's algorithm]] and [[Simplex algorithm | Dantzig's algorithm]].
Also, a quadratic programming problem stated as minimize <math>f(\mathbf{x})=\mathbf{c}^T\mathbf{x}+\frac{1}{2}\mathbf{x}^T\mathbf{Qx}</math> subject to <math>\mathbf{Ax} \geq \mathbf{b} </math> as well as <math>\mathbf{x} \ge \mathbf{0}</math>
is the same as solving the LCP with
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>
In that case,
* <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.
| |||