二次計画法

二次計画法（にじけいかくほう、英: quadratic programming, QP）は、数理最適化における非線形計画法の代表例の一つであり、いくつかの変数からなる二次関数を線形制約の下で最適化（最小化ないしは最大化）する方法である。二次計画法の対象となる最適化問題を二次計画問題という。

問題の定式化[編集]

$n$ の変数と $m$ の制約からなる二次計画問題は以下のように定式化することができる^[1]。

以下を所与とする：

実数値の $n$ 次元ベクトル $c$
$n$ 行 $n$ 列の実数値対称行列 $Q$
$m$ 行 $n$ 列の実数値行列 $A$
実数値の $m$ 次元ベクトル $b$

二次計画問題の目的は以下の問題の解となる $n$ 次元ベクトル $x$ を見つけることである。

${\text{minimize}}$	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
${\text{subject to}}$	$A\mathbf {x} \leq \mathbf {b} ,$

ここで $x T$ はベクトル $x$ の転置を表す。 $A x \leq b$ という記法はベクトル $A x$ の全ての要素が対応するベクトル $b$ の要素より小さいもしくは等しいことを意味する。

関係する最適化問題として、二次制約付き二次計画問題（英語版）があり、二次制約付き二次計画問題では二次の制約が足されている。

解法[編集]

一般の問題について、多様な解法が広く用いられており、例えば

などがある。行列 $Q$ が正値定符号ならば、問題はより一般的な凸最適化の領域の特殊ケースとなる。

等式制約[編集]

二次計画問題は行列 $Q$ が正値定符号であり、等式制約のみを含む時、特に簡単になり、解の過程は線形となる。ラグランジュの未定乗数法を用い、ラグランジアンの極値を探せば、以下の等式制約問題

{\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x}

,

{\text{subject to}}\quad E\mathbf {x} =\mathbf {d}

.

の解は次の線形システム

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

.

の解として与えられることが容易に示される。ここで $\lambda$ はラグランジュ乗数の集合で $x$ と共に計算される。

このシステムを解く最も簡単な方法は直接的に問題を解くこと（例えばLU分解）で、問題の規模が小さければ非常に有用である。問題の規模が大きければ、このシステムは特異な難しさに直面する。もっとも重要なのは（ $Q$ が正値定符号であったとしても、）問題自体は正値定符号と決してならないことである。そのためうまくいく数値解法を見いだすことは非常に難しいので、問題に依存した様々な方法がある^[4]。

もしも、制約があまり多くの変数を含んでいなければ、比較的簡単な方法として制約を無条件で満たすように変数を変換する方法がある。例えば、 $d = 0$ （非ゼロの場合にも一般化できる）と仮定する。制約方程式を見ると

E\mathbf {x} =0

.

となる。新しい変数として $y$ を以下のように定義する。

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

.

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

EZ\mathbf {y} =0

.

であり、もし $Z$ を $EZ = 0$ となるように選べば、制約方程式は常に満たされるようになる。このような $Z$ を見つけるということは $E$ の零空間を見つけることを意味し、 $E$ の構造に依存するが多かれ少なかれ単純である。二次形式に代入すると次の無制約の最小化問題が得られる。

{\tfrac {1}{2}}\mathbf {x} ^{T}Q\mathbf {x} +\mathbf {c} ^{T}\mathbf {x} \quad \Rightarrow \quad {\tfrac {1}{2}}\mathbf {y} ^{T}Z^{T}QZ\mathbf {y} +(Z^{T}\mathbf {c} )^{T}\mathbf {y} .

この解は以下で与えられる。

Z^{T}QZ\mathbf {y} =-Z^{T}\mathbf {c} .

$Q$ についてのある条件の下で、退化した行列 $Z T QZ$ は正値定符号となる。 $Z$ の陽な計算を避けた共役勾配法のバリエーションとして書くことも可能である^[5]。

ラグランジュ双対[編集]

「双対問題」も参照

二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、 $c = 0$ かつ $Q$ が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。

L(x,\lambda )={\tfrac {1}{2}}x^{T}Qx+\lambda ^{T}(Ax-b).

（ラグランジュ）双対関数を $g(\lambda )$ とし、 $g(\lambda )=\inf _{x}L(x,\lambda )$ を満たすものとすれば、 $\nabla _{x}L(x,\lambda )=0$ という条件と $Q$ の正値定符号性を用いることで、 $L$ の下限を見つけることができる。

x^{*}=-Q^{-1}A^{T}\lambda .

ゆえに双対関数は

g(\lambda )=-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b,

であり、二次計画問題のラグランジュ双対は

{\text{ maximize}}\quad -{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b

\,\,{\text{subject to}}\quad \lambda \geqslant 0

となる。ラグランジュ双対理論の他にも他の双対性が存在する（例えばWolfe双対（英語版））。

複雑性[編集]

正値定符号行列である $Q$ について楕円体法（英語版）は多項式時間で二次計画問題を解くことができる^[6]。一方で、 $Q$ の符号が不定ならば、二次計画問題はNP困難となる^[7]。実際、 $Q$ のただ一つの固有値だけが負であったとしても、二次計画問題はNP困難である^[8]。