Content deleted Content added
→Formulation: - rephrased to w = Mz+q, standard notation |
→Relation to Quadratic Programming: - added bit about how to convert QP program to LCP |
||
Line 30:
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 0</math>
is the same as solving the LCP with
* <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>
== See also ==
| |||