Problème de complémentarité linéaire

En théorie de l'optimisation mathématique , le problème de complémentarité linéaire (LCP) apparaît fréquemment en mécanique computationnelle et englobe la programmation quadratique bien connue comme cas particulier. Il a été proposé par Cottle et Dantzig en 1968.

Formulation

Étant donné une matrice réelle M et un vecteur q , le problème de complémentarité linéaire LCP( q , M ) cherche des vecteurs z et w qui satisfont les contraintes suivantes :

${\displaystyle w,z\geqslant 0, <semantics> <mrow> <mstyle> <mi>m</mi> <mo>,</mo> <mi>j</mi> <mo>⩾</mo> <mn>0</mn> <mo>,</mo> </mstyle> </mrow> <annotation>{ displaystyle w, z geqslant 0,}</annotation> </semantics> </math><img src=$
${\displaystyle z^{T}w=0 <semantics> <mrow> <mstyle> <msup> <mi>j</mi> <mrow> <mi>T</mi> </mrow> </msup> <mi>m</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle z^{T}w=0}</annotation> </semantics> </math><img src=$ ${\displaystyle \sum olimits _{i}w_{i}z_{i}=0. <semantics> <mrow> <mstyle> <msub> <mo>∑</mo> <mrow> <mi>je</mi> </mrow> </msub> <msub> <mi>m</mi> <mrow> <mi>je</mi> </mrow> </msub> <msub> <mi>j</mi> <mrow> <mi>je</mi> </mrow> </msub> <mo>=</mo> <mn>0.</mn> </mstyle> </mrow> <annotation>{ displaystyle somme nolimits _ {i} w_ {i} z_ {i} = 0.}</annotation> </semantics> </math><img src=$ ${\displaystyle i <semantics> <mrow> <mstyle> <mi>je</mi> </mstyle> </mrow> <annotation>{\displaystyle i}</annotation> </semantics> </math><img src=$ ${\displaystyle w_{i <semantics> <mrow> <mstyle> <msub> <mi>m</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle w_{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle z_{i <semantics> <mrow> <mstyle> <msub> <mi>j</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle z_{i}}</annotation> </semantics> </math><img src=$
${\displaystyle w=Mz+q <semantics> <mrow> <mstyle> <mi>m</mi> <mo>=</mo> <mi>M</mi> <mi>j</mi> <mo>+</mo> <mi>q</mi> </mstyle> </mrow> <annotation>{\displaystyle w=Mz+q}</annotation> </semantics> </math><img src=$

Une condition suffisante pour l'existence et l'unicité d'une solution à ce problème est que M soit symétrique définie positive . Si M est tel que LCP( q , M ) a une solution pour tout q , alors M est une matrice Q. Si M est tel que LCP( q , M ) a une solution unique pour tout q , alors M est une matrice P. Ces deux caractérisations sont suffisantes et nécessaires.

Le vecteur w est une variable d'écartement , et est donc généralement rejeté une fois que z est trouvé. En tant que tel, le problème peut également être formulé comme suit :

${\displaystyle Mz+q\geqslant 0 <semantics> <mrow> <mstyle> <mi>M</mi> <mi>j</mi> <mo>+</mo> <mi>q</mi> <mo>⩾</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle Mz+q\geqslant 0}</annotation> </semantics> </math><img src=$
${\displaystyle z\geqslant 0 <semantics> <mrow> <mstyle> <mi>j</mi> <mo>⩾</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle z\geqslant 0}</annotation> </semantics> </math><img src=$
${\displaystyle z^{\mathrm {T} }(Mz+q)=0 <semantics> <mrow> <mstyle> <msup> <mi>j</mi> <mrow> <mrow> <mi>T</mi> </mrow> </mrow> </msup> <mo>(</mo> <mi>M</mi> <mi>j</mi> <mo>+</mo> <mi>q</mi> <mo>)</mo> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{ displaystyle z ^ { mathrm {T}} (Mz + q) = 0}</annotation> </semantics> </math><img src=$

Minimisation quadratique convexe : conditions minimales

La recherche d'une solution au problème de complémentarité linéaire est associée à la minimisation de la fonction quadratique

{\displaystyle f(z)=z^{T}(Mz+q) <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>j</mi> <mo>)</mo> <mo>=</mo> <msup> <mi>j</mi> <mrow> <mi>T</mi> </mrow> </msup> <mo>(</mo> <mi>M</mi> <mi>j</mi> <mo>+</mo> <mi>q</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{ displaystyle f (z) = z ^ {T} (Mz + q)}</annotation> </semantics> </math></span><img src=

sous réserve des contraintes

{\displaystyle {Mz}+q\geqslant 0 <semantics> <mrow> <mstyle> <mrow> <mi>M</mi> <mi>j</mi> </mrow> <mo>+</mo> <mi>q</mi> <mo>⩾</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle {Mz}+q\geqslant 0}</annotation> </semantics> </math></span><img src=

{\displaystyle z\geqslant 0 <semantics> <mrow> <mstyle> <mi>j</mi> <mo>⩾</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle z\geqslant 0}</annotation> </semantics> </math></span><img src=

Ces contraintes garantissent que f est toujours non négative. Le minimum de f est nul en z si et seulement si z résout le problème de complémentarité linéaire.

Si M est défini positif , tout algorithme de résolution de QP (strictement) convexes peut résoudre le LCP. Des algorithmes de pivotement d'échange de base spécialement conçus, tels que l'algorithme de Lemke et une variante de l' algorithme du simplexe de Dantzig , sont utilisés depuis des décennies. En plus d'avoir une complexité temporelle polynomiale, les méthodes de point intérieur sont également efficaces dans la pratique.

De plus, un problème de programmation quadratique énoncé comme minimisant le sujet et avec Q symétrique ${\displaystyle f(x)=c^{T}x+{ frac {1}{2}}x^{T}Qx <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>x</mi> <mo>)</mo> <mo>=</mo> <msup> <mi>c</mi> <mrow> <mi>T</mi> </mrow> </msup> <mi>x</mi> <mo>+</mo> <mrow> <mstyle> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mstyle> </mrow> <msup> <mi>x</mi> <mrow> <mi>T</mi> </mrow> </msup> <mi>Q</mi> <mi>x</mi> </mstyle> </mrow> <annotation>{\displaystyle f(x)=c^{T}x+{ frac {1}{2}}x^{T}Qx}</annotation> </semantics> </math><img src=$ ${\displaystyle Ax\geqslant b <semantics> <mrow> <mstyle> <mi>UN</mi> <mi>x</mi> <mo>⩾</mo> <mi>b</mi> </mstyle> </mrow> <annotation>{\displaystyle Ax\geqslant b}</annotation> </semantics> </math><img src=$ ${\displaystyle x\geqslant 0 <semantics> <mrow> <mstyle> <mi>x</mi> <mo>⩾</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle x\geqslant 0}</annotation> </semantics> </math><img src=$

est la même chose que de résoudre le LCP avec

{\displaystyle q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix <semantics> <mrow> <mstyle> <mi>q</mi> <mo>=</mo> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>c</mi> </mtd> </mtr> <mtr> <mtd> <mo>−</mo> <mi>b</mi> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mo>,</mo> <mspace></mspace> <mi>M</mi> <mo>=</mo> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>Q</mi> </mtd> <mtd> <mo>−</mo> <msup> <mi>UN</mi> <mrow> <mi>T</mi> </mrow> </msup> </mtd> </mtr> <mtr> <mtd> <mi>UN</mi> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}}</annotation> </semantics> </math></span><img src=

Ceci est dû au fait que les conditions de Karush-Kuhn-Tucker du problème QP peuvent s'écrire comme suit :

{\displaystyle {\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases <semantics> <mrow> <mstyle> <mrow> <mrow> <mo>{</mo> <mtable> <mtr> <mtd> <mi>v</mi> <mo>=</mo> <mi>Q</mi> <mi>x</mi> <mo>−</mo> <msup> <mi>UN</mi> <mrow> <mi>T</mi> </mrow> </msup> <mrow> <mi>λ</mi> </mrow> <mo>+</mo> <mi>c</mi> </mtd> </mtr> <mtr> <mtd> <mi>m</mi> <mo>=</mo> <mi>UN</mi> <mi>x</mi> <mo>−</mo> <mi>b</mi> </mtd> </mtr> <mtr> <mtd> <mi>x</mi> <mo>,</mo> <mrow> <mi>λ</mi> </mrow> <mo>,</mo> <mi>v</mi> <mo>,</mo> <mi>m</mi> <mo>⩾</mo> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <msup> <mi>x</mi> <mrow> <mi>T</mi> </mrow> </msup> <mi>v</mi> <mo>+</mo> <msup> <mrow> <mi>λ</mi> </mrow> <mrow> <mi>T</mi> </mrow> </msup> <mi>m</mi> <mo>=</mo> <mn>0</mn> </mtd> </mtr> </mtable> <mo></mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases}}}</annotation> </semantics> </math></span><img src=

avec v les multiplicateurs de Lagrange sur les contraintes de non-négativité, λ les multiplicateurs sur les contraintes d'inégalité et s les variables d'écart pour les contraintes d'inégalité. La quatrième condition découle de la complémentarité de chaque groupe de variables ( x , s ) avec son ensemble de vecteurs KKT (multiplicateurs de Lagrange optimaux) étant ( v , λ ) . Dans ce cas,

{\displaystyle z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix <semantics> <mrow> <mstyle> <mi>z</mi> <mo>=</mo> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>x</mi> </mtd> </mtr> <mtr> <mtd> <mi>λ</mi> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mo>,</mo> <mspace></mspace> <mi>w</mi> <mo>=</mo> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>v</mi> </mtd> </mtr> <mtr> <mtd> <mi>s</mi> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix}}}</annotation> </semantics> </math></span><img src=

Si la contrainte de non-négativité sur les x est relâchée, la dimensionnalité du problème LCP peut être réduite au nombre d'inéquations, à condition que Q soit non singulier (ce qui est garanti s'il est défini positif ). Les multiplicateurs v ne sont plus présents, et les premières conditions KKT peuvent être réécrites ainsi :

{\displaystyle Qx=A^{T}{\lambda }-c <semantics> <mrow> <mstyle> <mi>Q</mi> <mi>x</mi> <mo>=</mo> <msup> <mi>A</mi> <mrow> <mi>T</mi> </mrow> </msup> <mrow> <mi>λ</mi> </mrow> <mo>−</mo> <mi>c</mi> </mstyle> </mrow> <annotation>{\displaystyle Qx=A^{T}{\lambda }-c}</annotation> </semantics> </math></span><img src=

ou:

{\displaystyle x=Q^{-1}(A^{T}{\lambda }-c) <semantics> <mrow> <mstyle> <mi>x</mi> <mo>=</mo> <msup> <mi>Q</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>(</mo> <msup> <mi>A</mi> <mrow> <mi>T</mi> </mrow> </msup> <mrow> <mi>λ</mi> </mrow> <mo>−</mo> <mi>c</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle x=Q^{-1}(A^{T}{\lambda }-c)}</annotation> </semantics> </math></span><img src=

en prémultipliant les deux côtés par A et en soustrayant b on obtient :

{\displaystyle Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\, <semantics> <mrow> <mstyle> <mi>A</mi> <mi>x</mi> <mo>−</mo> <mi>b</mi> <mo>=</mo> <mi>A</mi> <msup> <mi>Q</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>(</mo> <msup> <mi>A</mi> <mrow> <mi>T</mi> </mrow> </msup> <mrow> <mi>λ</mi> </mrow> <mo>−</mo> <mi>c</mi> <mo>)</mo> <mo>−</mo> <mi>b</mi> <mspace></mspace> </mstyle> </mrow> <annotation>{\displaystyle Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\,}</annotation> </semantics> </math></span><img src=

Le côté gauche, en raison de la deuxième condition KKT, est s . Substitution et réorganisation :

{\displaystyle s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\, <semantics> <mrow> <mstyle> <mi>s</mi> <mo>=</mo> <mo>(</mo> <mi>A</mi> <msup> <mi>Q</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <msup> <mi>A</mi> <mrow> <mi>T</mi> </mrow> </msup> <mo>)</mo> <mrow> <mi>λ</mi> </mrow> <mo>+</mo> <mo>(</mo> <mo>−</mo> <mi>A</mi> <msup> <mi>Q</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mi>c</mi> <mo>−</mo> <mi>b</mi> <mo>)</mo> <mspace></mspace> </mstyle> </mrow> <annotation>{\displaystyle s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\,}</annotation> </semantics> </math></span><img src=

Appeler maintenant

{\displaystyle {\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned <semantics> <mrow> <mstyle> <mrow> <mtable> <mtr> <mtd> <mi>M</mi> </mtd> <mtd> <mi></mi> <mo>:=</mo> <mo>(</mo> <mi>A</mi> <msup> <mi>Q</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <msup> <mi>A</mi> <mrow> <mi>T</mi> </mrow> </msup> <mo>)</mo> </mtd> </mtr> <mtr> <mtd> <mi>q</mi> </mtd> <mtd> <mi></mi> <mo>:=</mo> <mo>(</mo> <mo>−</mo> <mi>A</mi> <msup> <mi>Q</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mi>c</mi> <mo>−</mo> <mi>b</mi> <mo>)</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned}}}</annotation> </semantics> </math></span><img src=

nous avons un LCP, dû à la relation de complémentarité entre les variables d'écart s et leurs multiplicateurs de Lagrange λ . Une fois que nous l'avons résolu, nous pouvons obtenir la valeur de x à partir de λ grâce à la première condition KKT.

Enfin, il est également possible de gérer des contraintes d’égalité supplémentaires :

{\displaystyle A_{eq}x=b_{eq <semantics> <mrow> <mstyle> <msub> <mi>A</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> </msub> <mi>x</mi> <mo>=</mo> <msub> <mi>b</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle A_{eq}x=b_{eq}}</annotation> </semantics> </math></span><img src=

Ceci introduit un vecteur de multiplicateurs de Lagrange μ , de même dimension que . ${\displaystyle b_{eq <semantics> <mrow> <mstyle> <msub> <mi>b</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle b_{eq}}</annotation> </semantics> </math><img src=$

Il est facile de vérifier que les M et Q du système LCP sont désormais exprimés comme suit : ${\displaystyle s=M{\lambda }+Q <semantics> <mrow> <mstyle> <mi>s</mi> <mo>=</mo> <mi>M</mi> <mrow> <mi>λ</mi> </mrow> <mo>+</mo> <mi>Q</mi> </mstyle> </mrow> <annotation>{\displaystyle s=M{\lambda }+Q}</annotation> </semantics> </math><img src=$

{\displaystyle {\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned <semantics> <mrow> <mstyle> <mrow> <mtable> <mtr> <mtd> <mi>M</mi> </mtd> <mtd> <mi></mi> <mo>:=</mo> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>A</mi> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <msup> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>Q</mi> </mtd> <mtd> <msubsup> <mi>A</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> <mrow> <mi>T</mi> </mrow> </msubsup> </mtd> </mtr> <mtr> <mtd> <mo>−</mo> <msub> <mi>A</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> </msub> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <msup> <mi>A</mi> <mrow> <mi>T</mi> </mrow> </msup> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>q</mi> </mtd> <mtd> <mi></mi> <mo>:=</mo> <mo>−</mo> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>A</mi> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <msup> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>Q</mi> </mtd> <mtd> <msubsup> <mi>A</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> <mrow> <mi>T</mi> </mrow> </msubsup> </mtd> </mtr> <mtr> <mtd> <mo>−</mo> <msub> <mi>A</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> </msub> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>c</mi> </mtd> </mtr> <mtr> <mtd> <msub> <mi>b</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> </msub> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mo>−</mo> <mi>b</mi> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned}}}</annotation> </semantics> </math></span><img src=

A partir de λ nous pouvons maintenant récupérer les valeurs de x et du multiplicateur de Lagrange des égalités μ :

{\displaystyle {\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix <semantics> <mrow> <mstyle> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>x</mi> </mtd> </mtr> <mtr> <mtd> <mi>μ</mi> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mo>=</mo> <msup> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <mi>Q</mi> </mtd> <mtd> <msubsup> <mi>A</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> <mrow> <mi>T</mi> </mrow> </msubsup> </mtd> </mtr> <mtr> <mtd> <mo>−</mo> <msub> <mi>A</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> </msub> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mrow> <mrow> <mo>[</mo> <mtable> <mtr> <mtd> <msup> <mi>A</mi> <mrow> <mi>T</mi> </mrow> </msup> <mi>λ</mi> <mo>−</mo> <mi>c</mi> </mtd> </mtr> <mtr> <mtd> <mo>−</mo> <msub> <mi>b</mi> <mrow> <mi>e</mi> <mi>q</mi> </mrow> </msub> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix}}}</annotation> </semantics> </math></span><img src=

En fait, la plupart des solveurs QP fonctionnent sur la formulation LCP, y compris la méthode du point intérieur , le pivotement principal/complémentarité et les méthodes des ensembles actifs . Les problèmes LCP peuvent également être résolus par l' algorithme criss-cross , inversement, pour les problèmes de complémentarité linéaire, l'algorithme criss-cross ne se termine de manière finie que si la matrice est une matrice suffisante. Une matrice suffisante est une généralisation à la fois d'une matrice définie positive et d'une matrice P , dont les principaux mineurs sont chacun positifs. De tels LCP peuvent être résolus lorsqu'ils sont formulés de manière abstraite en utilisant la théorie des matroïdes orientés .