二次計画法

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

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

以下を所与とする：
 実数値の  次元ベクトル 
  行  列の実数値対称行列 
  行  列の実数値行列 
 実数値の  次元ベクトル 
二次計画問題の目的は以下の問題の解となる  次元ベクトル  を見つけることである。

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

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

解法 
一般の問題について、多様な解法が広く用いられており、例えば
 内点法
 
 
 共役勾配法
 勾配射影法
 シンプレックス法の拡張

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

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

の解は次の線形システム

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

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

もし、制約が変数をそう含んでないのであれば、相対的に簡単な方法として変数を変換し制約を無条件で満たすようにすることがある。例えば、（非ゼロの場合にも一般化できる）と仮定する。制約方程式を見ると

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

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

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

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

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

ラグランジュ双対 

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

（ラグランジュ）双対関数を  とし、 を満たすものとすれば、 という条件と  の正値定符号性を用いることで、 の下限を見つけることができる。

ゆえに双対関数は

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

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

複雑性 
正値定符号行列である  については多項式時間で二次計画問題を解くことができる。一方で、 の符号が不定ならば、二次計画問題はNP困難となる。実際、 のただ一つの固有値だけが負であったとしても、二次計画問題はNP困難である。

二次計画法のソルバーとプログラミング言語

関連項目 
サポートベクターマシン
逐次二次計画法
線形計画法

参照文献

脚注

書籍 
 
  A6: MP2, pg.245.

外部リンク 
二次計画法についてのページ (英語)
NEOS Optimization Guide: Quadratic Programming
Solve an example Quadratic Programming (QP) problem

最適化
数学に関する記事