二次計画法

二次計画法（Quadratic Programming, QP）

二次計画法は、数理最適化における非線形計画法の代表的な手法の一つです。これは、複数の変数からなる二次関数を、線形制約の下で最適化（最小化または最大化）する問題を扱う方法です。二次計画法の対象となる最適化問題は、二次計画問題と呼ばれます。

問題の定式化

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

与えられるもの:
実数値のn次元ベクトル c
n行n列の実数値対称行列 Q
m行n列の実数値行列 A
実数値のm次元ベクトル b

目的:
次の問題を解くn次元ベクトル x を見つけること。


Minimize 1/2 x^T Q x + c^T x
subject to A x <= b


ここで、x^T はベクトルxの転置を表します。また、Ax <= b は、ベクトルAxのすべての要素が対応するベクトルbの要素以下であることを意味します。

関連する最適化問題として、二次制約付き二次計画問題があります。これは、上記の制約に加えて、二次形式による制約が追加されたものです。

解法

一般の二次計画問題に対して、以下のような多様な解法が用いられています。

内点法
有効制約法
拡張ラグランジュ乗数法
共役勾配法
勾配射影法
シンプレックス法の拡張

特に、行列Qが正定値行列である場合、問題はより一般的な凸最適化の特殊ケースとなり、効率的な解法が利用できます。

等式制約の場合

二次計画問題において、行列Qが正定値であり、制約が等式のみで構成される場合、問題は特に簡単になり、解法も線形になります。ラグランジュの未定乗数法を用いると、以下の等式制約問題を解くことができます。


Minimize 1/2 x^T Q x + c^T x
subject to E x = d


この問題の解は、次の線形システムの解として得られます。


[Q E^T] [x] = [-c]
[E 0 ] [λ] = [ d]


ここで、λはラグランジュ乗数の集合であり、xと共に計算されます。このシステムを解くには、直接的に解く方法（例えばLU分解）が有効ですが、問題の規模が大きい場合には、特異な難しさが生じることがあります。そのため、問題に依存した様々な解法が存在します。

制約があまり多くの変数を含んでいない場合、制約を無条件で満たすように変数を変換する方法があります。例えば、制約方程式が `E x = 0` の場合、新しい変数yを `Z y = x` と定義します。ここで、yの次元はxの次元から制約の数を引いたものです。この時、`E Z y = 0` となり、Zを `EZ = 0` となるように選べば、制約方程式は常に満たされるようになります。二次形式に代入すると、次の無制約の最小化問題が得られます。


1/2 x^T Q x + c^T x ⇒ 1/2 y^T Z^T Q Z y + (Z^T c)^T y


この解は、以下で与えられます。


Z^T Q Z y = -Z^T c

ラグランジュ双対

二次計画問題のラグランジュ双対問題もまた二次計画問題となります。`c = 0` かつ `Q` が正定値の場合を考えると、ラグランジュ関数は以下のように書けます。


L(x, λ) = 1/2 x^T Q x + λ^T (A x - b)


双対関数 `g(λ) = inf_x L(x, λ)` を求めると、`∇_x L(x, λ) = 0` から、`x = -Q^-1 A^T λ` が得られます。したがって、双対関数は次のようになります。


g(λ) = -1/2 λ^T A Q^-1 A^T λ - λ^T b


二次計画問題のラグランジュ双対問題は、以下のように定式化されます。


maximize -1/2 λ^T A Q^-1 A^T λ - λ^T b
subject to λ >= 0

複雑性

行列Qが正定値の場合、楕円体法を用いることで二次計画問題を多項式時間で解くことができます。しかし、Qの符号が不定の場合、二次計画問題はNP困難となります。実際、Qの固有値が一つでも負の値を持つ場合、問題はNP困難になります。

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

二次計画問題を解くためのソルバーやプログラミング言語は多数存在します。具体的なツールとしては、以下のようなものが挙げられます。

CVX (MATLAB, Python)
MOSEK
Gurobi
CPLEX
SciPy (Python)

これらのツールを利用することで、様々な二次計画問題を効率的に解くことができます。

関連項目

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

参考文献

Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc.. pp. xxiv+762 pp.. ISBN 0-12-192350-9.
Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5

外部リンク

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

もう一度検索