二次計画法
二次計画問題は行列 Q が正値定符号であり、等式制約のみを含む時、特に簡単になり、解の過程は線形となる。ラグランジュの未定乗数法を用い、ラグランジアンの極値を探せば、以下の等式制約問題
Minimize 1 2 x T Q x + c T x {\displaystyle {\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }
subject to E x = d {\displaystyle {\text{subject to}}\quad E\mathbf {x} =\mathbf {d} }
の解は次の線形システム
[ Q E T E 0 ] [ x λ ] = [ − c d ] {\displaystyle {\begin{bmatrix}Q&E^{T}\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}}
正値定符号行列である Q について楕円体法(英語版)は多項式時間で二次計画問題を解くことができる。一方で、Q の符号が不定ならば、二次計画問題はNP困難となる。実際、Q のただ一つの固有値だけが負であったとしても、二次計画問題はNP困難である。