二次計画法

二次計画法（にじけいかくほう、英: 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]。

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

名前	要約
AIMMS（英語版）	最適化とスケジューリング型問題のモデリングと計算のためのソフトウェアシステム
ALGLIB	二重ライセンス(GPL/proprietary)の数値ライブラリ(C++, .NET).
AMPL（英語版）	大規模数理最適化のための一般的なモデリング言語
APMonitor（英語版）	LP、QP、NLP、MILP、MINLP^[9]、DAE（英語版）のための、MATLABとPython上のモデリングと最適化スイート。
CGAL	二次計画法ソルバーを含むオープンソースの計算幾何パッケージ
CPLEX（英語版）	API(C,C++,Java,.Net, Python, Matlab, R)によるポピュラーなソルバー。大学向けは無料。
CVXOPT	Pythonを元にした凸最適化のためのフリーパッケージ。software
Excel のソルバー関数	関数の評価がセル上の再計算を元にした表計算に調整された非線形ソルバー。基本バージョンはExcelの標準アドオンとして利用できる。
GALAHAD	凸、もしくは非凸二次計画法についての多様な方法を含む平滑非線形最適化のためのパッケージライブラリ。
GAMS	数理最適化のためのハイレベルモデリングシステム。
Gurobi（ドイツ語版）	大規模線形計画、二次計画、混合整数計画のための並列アルゴリズムを備えたソルバー。大学向けは無料。
IMSL	プログラマーが自身のソフトウェアアプリケーションに埋め込むことが可能な数学関数と統計関数のセット。
IPOPT	IPOPT (Interior Point OPTimizer) は大規模非線形最適化のためのソフトウェアパッケージである。
JOptimizer	線形等式制約と凸不等式制約を含む最小化問題を解くためのオープンソースライブラリ（Javaで実装されている）
Artelys Knitro（英語版）	非線形最適化のための統合パッケージ
Maple	数学のための汎用的用途のプログラミング言語。Maple上で二次計画問題を解くにはQPSolveのコマンドを用いればよい。
MATLAB	数値的計算のための汎用的用途の行列指向プログラミング言語。MATLAB上で二次計画法を行うにはMATLABの基本製品に加えて Optimization Toolbox が必要になる。
Mathematica	数学のための汎用的用途のプログラミング言語でシンボリック計算と数値計算を含む。
MOSEK（英語版）	いくつかの言語(C++,java,.net, Matlab, python)のためのAPIを持つ大規模最適化のためのソルバー。
NAG数値計算ライブラリ	複数のプログラミング言語(C, C++, Fortran, Visual Basic, Java, C#)とパッケージ(MATLAB, Excel, R, LabVIEW)のためのNumerical Algorithms Groupによって開発された数学ルーチンと統計ルーチンの集まり。NAGライブラリの最適化チャプターには疎線形制約行列と非疎線形制約行列を持つ二次計画問題のルーチンが、非線形、有界、もしくは制約なしの線形ないしは非線形関数の線形、非線和、二乗和の最適化のためのルーチンとともに含まれている。NAGライブラリは局所最適化と大域的最適化のためと連続もしくは整数問題のためのルーチンが含まれている。
OOQP	OOQPは凸二次計画問題のためのオブジェクト指向の内点法ソルバーである^[10]^[11]。
OpenOpt	PythonのためのBSDライセンスの数値最適化ライブラリ。QPのページを参照のこと。
OptimJ（英語版）	Eclipseのプラグインとして利用可能な複数のターゲットをサポートした最適化のためのJavaをベースとしたフリーのモデリング言語^[12]^[13]。
qpOASES	オンラインの有効制約法のオープンソースのC++実装
R (Fortran)	GPLライセンスのユニバーサルクロスプラットフォームの統計計算フレームワーク。quadprogページを参照のこと。MIT Licenseの下でjavascriptに移植されている。LGPLの下でC#にも移植されている。
SAS（英語版）/OR	線形、整数、非線形、微分不可、ネットワーク、組み合わせ、そして制約付きの最適化のためのソルバーのスイート。algebraic modeling language（英語版）であるOPTMODELと特定の問題と市場を目標とした多様な垂直ソリューションはそのすべてが完全にSAS System（英語版）上で統合されている。
TK Solver（英語版）	宣言型のルールベース型言語に基づいた数理的モデリングと問題解決のためのソフトウェアシステムでUniversal Technical Systems, Inc.により商品化されている。
TOMLAB（英語版）	MATLABのための、大域的最適化、整数計画問題、あらゆるタイプの最小二乗法、線形計画、二次計画、制約なし計画問題のサポート。TOMLABはGurobi（ドイツ語版）、CPLEX（英語版）、SNOPT（英語版）、KNITRO（英語版）のようなソルバーをサポートしている。
XPRESS	大規模線形計画問題、二次計画問題、汎用非線形計画問題、混合整数問題のためのソルバー。いくつかのプログラミング言語のためのAPIとモデリング言語Moselを持ち合わせており、APML、GAMS上で起動する。大学向けは無料。

脚注

[脚注の使い方]

^ Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. p. 449. ISBN 978-0-387-30303-1 .
^ ^a ^b Murty, Katta G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp.. ISBN 3-88538-403-5. MR949214. オリジナルの2010年4月1日時点におけるアーカイブ。
^ Delbos, F.; Gilbert, J.Ch. (2005). “Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems”. Journal of Convex Analysis 12: 45–69.
^ Google search.
^ Gould, Nicholas I. M.; Hribar, Mary E.; Nocedal, Jorge (April 2001). On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization. 23. SIAM Journal of Scientific Computing. pp. 1376–1395. CiteSeer^x: 10.1.1.129.7555.
^ Kozlov, M. K.; S. P. Tarasov; Leonid G. Khachiyan (1979). “[Polynomial solvability of convex quadratic programming]”. Doklady Akademii Nauk SSSR 248: 1049–1051. Translated in: Soviet Mathematics - Doklady 20: 1108–1111.
^ Sahni, S. (1974). “Computationally related problems”. SIAM Journal on Computing 3: 262–279. doi:10.1137/0203021.
^ Pardalos, Panos M.; Vavasis, Stephen A. (1991). “Quadratic programming with one negative eigenvalue is NP-hard”. Journal of Global Optimization 1 (1): 15–22. doi:10.1007/bf00120662.
^ Mixed Integer Nonlinear Programming. 混合整数非線形計画問題のこと。
^ “Object-Oriented Software for Quadratic Programming (Paper)” (PDF). University of Wisconsin-Madison (2003年2月25日). 2014年7月11日閲覧。
^ “Source repository for OOQP, a quadratic programming solver (and more)”. GitHub. 2014年7月11日閲覧。
^ OptimJ used in an optimization model for mixed-model assembly lines. University of Münster.
^ OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games.

参考文献

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. MR1150683
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 A6: MP2, pg.245.