二次計画法

二次計画法（にじけいかくほう、テンプレート:Lang-en-short）は、数理最適化における非線形計画法の代表例の一つであり、いくつかの変数からなる二次関数を線形制約の下で最適化（最小化ないしは最大化）する方法である。二次計画法の対象となる最適化問題を二次計画問題という。

問題の定式化

テンプレート:Mvar の変数とテンプレート:Mvar の制約からなる二次計画問題は以下のように定式化することができる^[1]。

以下を所与とする：

実数値のテンプレート:Mvar 次元ベクトルテンプレート:Math
テンプレート:Mvar 行テンプレート:Mvar 列の実数値対称行列テンプレート:Mvar
テンプレート:Mvar 行テンプレート:Mvar 列の実数値行列テンプレート:Mvar
実数値のテンプレート:Mvar 次元ベクトルテンプレート:Math

二次計画問題の目的は以下の問題の解となるテンプレート:Mvar 次元ベクトルテンプレート:Math を見つけることである。

$minimize$	$\frac{1}{2} 𝐱^{T} Q 𝐱 + 𝐜^{T} 𝐱$
$subject to$	$A 𝐱 \leq 𝐛,$

ここでテンプレート:Math はベクトルテンプレート:Math の転置を表す。テンプレート:Math という記法はベクトルテンプレート:Math の全ての要素が対応するベクトルテンプレート:Math の要素より小さいもしくは等しいことを意味する。

関係する最適化問題として、テンプレート:仮リンクがあり、二次制約付き二次計画問題では二次の制約が足されている。

解法

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

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

等式制約

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

Minimize \frac{1}{2} 𝐱^{T} Q 𝐱 + 𝐜^{T} 𝐱

,

subject to E 𝐱 = 𝐝

.

の解は次の線形システム

[\begin{matrix} Q & E^{T} \\ E & 0 \end{matrix}] [\begin{matrix} 𝐱 \\ λ \end{matrix}] = [\begin{matrix} - 𝐜 \\ 𝐝 \end{matrix}]

.

の解として与えられることが容易に示される。ここで $λ$ はラグランジュ乗数の集合でテンプレート:Math と共に計算される。

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

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

E 𝐱 = 0

.

となる。新しい変数としてテンプレート:Math を以下のように定義する。

Z 𝐲 = 𝐱

.

ここでテンプレート:Math の次元はテンプレート:Math の次元から制約の数を引いたものである。この時、

E Z 𝐲 = 0

.

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

\frac{1}{2} 𝐱^{T} Q 𝐱 + 𝐜^{T} 𝐱 \Rightarrow \frac{1}{2} 𝐲^{T} Z^{T} Q Z 𝐲 + (Z^{T} 𝐜)^{T} 𝐲 .

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

Z^{T} Q Z 𝐲 = - Z^{T} 𝐜 .

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

ラグランジュ双対

テンプレート:See also 二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、テンプレート:Math かつテンプレート:Mvar が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。

L (x, λ) = \frac{1}{2} x^{T} Q x + λ^{T} (A x - b) .

（ラグランジュ）双対関数を $g (λ)$ とし、 $g (λ) = \inf_{x} L (x, λ)$ を満たすものとすれば、 $\nabla_{x} L (x, λ) = 0$ という条件とテンプレート:Mvar の正値定符号性を用いることで、テンプレート:Mvar の下限を見つけることができる。

テンプレート:Big

ゆえに双対関数は

g (λ) = - \frac{1}{2} λ^{T} A Q^{- 1} A^{T} λ - λ^{T} b,

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

maximize - \frac{1}{2} λ^{T} A Q^{- 1} A^{T} λ - λ^{T} b

subject to λ ⩾ 0

となる。ラグランジュ双対理論の他にも他の双対性が存在する（例えばテンプレート:仮リンク）。

複雑性

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