二次計画法

Qが対称正定値行列である場合の特殊なケースとして、コスト関数は最小二乗法に帰着する。

ここで、 Q = R ^T R はQのコレスキー分解から導かれ、c = − R ^T dとなります。逆に、このような制約付き最小二乗計画は、一般的な非正方行列Rに対しても、二次計画問題として等価に定式化できます。

ある基準点x ₀の近傍で関数fを最小化する場合、Q はそのヘッセ行列H ( f ( x ₀ ))に設定され、c はその勾配∇ f ( x ₀ )に設定されます。関連するプログラミング問題である二次制約付き二次計画問題は、変数に二次制約を追加することで定式化できます。

二次計画法は、 Qが正定値で等式制約のみが存在する場合に特に単純であり、具体的には解法プロセスは線形です。ラグランジュ乗数法を用いてラグランジュ関数の極値を求めることで、等式制約問題の解が容易に得られることが示されます。

$\displaystyle {\text{最小化}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$

${\displaystyle {\text{ただし}}\quad E\mathbf {x} =\mathbf {d} }$

線形システムによって与えられる

${\displaystyle {\begin{bmatrix}Q&E^{\top }\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}}$

ここでλは、 xとともに解から得られるラグランジュ乗数の集合である。

このシステムに取り組む最も簡単な方法は、直接解法（例えば、LU分解）を用いることであり、小規模な問題であれば非常に実用的です。しかし、大規模な問題になると、このシステムはいくつかの特異な困難をもたらします。特に、問題が正定値行列（Qが正定値行列であっても）にならないため、適切な数値解法を見つけるのが非常に困難になる可能性があり、問題に応じて様々な解法から選択する必要があります。

制約条件が変数をあまり強く結合していない場合、比較的簡単な対処法は、制約条件が無条件に満たされるように変数を変更することです。たとえば、d = 0とします（非ゼロへの一般化は簡単です）。制約方程式を見てみましょう。

${\displaystyle E\mathbf {x} =0}$

次のように定義される新しい変数yを導入する

${\displaystyle Z\mathbf {y} =\mathbf {x} }$

ここで、yの次元はxから制約の数を引いた値である。

${\displaystyle EZ\mathbf {y} =\mathbf {0} }$

そして、EZ = 0となるようにZを選択すれば、制約方程式は常に満たされる。このようなZを見つけるには、 Eの零空間を見つける必要があるが、これはEの構造に応じて多かれ少なかれ単純である。これを二次形式に代入すると、制約のない最小化問題が得られる。

${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\top }Q\mathbf {x} +\mathbf {c} ^{\top }\mathbf {x} \quad \implies \quad {\tfrac {1}{2}}\mathbf {y} ^{\top }Z^{\top }QZ\mathbf {y} +\left(Z^{\top }\mathbf {c} \right)^{\top }\mathbf {y} }$

その解は次のように与えられる。

${\displaystyle Z^{\top }QZ\mathbf {y} =-Z^{\top }\mathbf {c} }$

Qに関する特定の条件下では、縮小行列Z ^T QZ は正定値になります。Zの明示的な計算を回避する共役勾配法の変形を記述することが可能です。^{[ 5 ]}

正定値Qの場合、最小化問題は凸問題です。したがって、楕円体法を使用して問題を (弱)多項式時間で解くことができます。これは 1979 年に Kozlov、Tarasov、Khachiyan によって明示的に示されました。^{[ 6 ]}

YeとTse ^{[ 7 ]は}、 Karmarkarのアルゴリズムを線形計画法から凸二次計画法に拡張した多項式時間アルゴリズムを発表した。n個の変数とL個の入力ビットを持つシステムでは、彼らのアルゴリズムはO(L n)回の反復を必要とし、各反復はO(L n ³ )回の算術演算で実行できるため、全体の実行時間計算量はO( L ² n ⁴ )となる。

KapoorとVaidya ^{[ 8 ]}は、O( L * log L * n ^3.67 * log n )の算術演算を必要とする別のアルゴリズムを提示している。

Q が正定値でない場合(つまり問題が非凸の場合)、二次計画法はNP 困難です。これを証明する 1 つの方法は、モツキン・ストラウスの定理を使用することです。^{[ 9 ]}この定理は、任意の無向グラフGに対して、 Gに関連付けられたある二次計画法の最大値が、Gのクリーク数の関数であると述べています。グラフのクリーク数を計算することはよく知られた NP 困難問題であるため、二次計画法を解くことも NP 困難です。いくつかの重要な特殊ケースも NP 困難です。

• Sahni ^{[ 10 ] は}、Q が負定値 ( n個の負の固有値を持つ)の場合の NP 困難性を証明しました。
• PardalosとVavasis ^{[ 11 ]}は、Qが少なくとも1つの負の固有値を持つ場合、(強い)NP困難であることを証明した。彼らは、クリーク問題から変数w、x1 ... xn、y1,2 _... y _{(n-1)、n 、z}、目的関数z - w2を持つ特定の二次計画問題への還元を示すことでこれを行った。彼らは、対応する二^次計画問題が値0の解を持つ場合に限り、入力グラフがサイズkのクリークを持つことを証明した。

さらに、非凸二次計画問題のKKT点を見つけることはCLS困難である。^{[ 12 ]}