二次計画法（にじけいかくほう、）は、数理最適化における非線形計画法の代表例の一つであり、いくつかの変数からなる二次関数を線形制約の下で最適化（最小化ないしは最大化）する方法である。二次計画法の対象となる最適化問題を二次計画問題という。
問題の定式化 の変数と の制約からなる二次計画問題は以下のように定式化することができる.。
以下を所与とする： 実数値の 次元ベクトル 行 列の実数値対称行列 行 列の実数値行列 実数値の 次元ベクトル 二次計画問題の目的は以下の問題の解となる 次元ベクトル を見つけることである。
ここで はベクトル の転置を表す。 という記法はベクトル の全ての要素が対応するベクトル の要素より小さいもしくは等しいことを意味する。
関係する最適化問題として、があり、二次制約付き二次計画問題では二次の制約が足されている。
解法 一般の問題について、多様な解法が広く用いられており、例えば 内点法 有効制約法 拡張ラグランジュ乗数法 共役勾配法 勾配射影法 シンプレックス法の拡張
などがある。行列 が正値定符号ならば、問題はより一般的な凸最適化の領域の特殊ケースとなる。
等式制約 二次計画問題は行列 が正値定符号であり、等式制約のみを含む時、特に簡単になり、解の過程は線形となる。ラグランジュの未定乗数法を用い、ラグランジアンの極値を探せば、以下の等式制約問題
,
.
の解は次の線形システム
.
の解として与えられることが容易に示される。ここで はラグランジュ乗数の集合で と共に計算される。
このシステムを解く最も簡単な方法は直接的に問題を解くこと（例えばLU分解）で、問題の規模が小さければ非常に有用である。問題の規模が大きければ、このシステムは特異な難しさに直面する。もっとも重要なのは（ が正値定符号であったとしても、）問題自体は正値定符号と決してならないことである。そのためうまくいく数値解法を見いだすことは非常に難しいので、問題に依存した様々な方法があるGoogle search.。
もしも、制約があまり多くの変数を含んでいなければ、比較的簡単な方法として制約を無条件で満たすように変数を変換する方法がある。例えば、（非ゼロの場合にも一般化できる）と仮定する。制約方程式を見ると
.
となる。新しい変数として を以下のように定義する。
.
ここで の次元は の次元から制約の数を引いたものである。この時、
.
であり、もし を となるように選べば、制約方程式は常に満たされるようになる。このような を見つけるということは の零空間を見つけることを意味し、 の構造に依存するが多かれ少なかれ単純である。二次形式に代入すると次の無制約の最小化問題が得られる。
この解は以下で与えられる。
についてのある条件の下で、退化した行列 は正値定符号となる。 の陽な計算を避けた共役勾配法のバリエーションとして書くことも可能である。
ラグランジュ双対
二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、 かつ が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。
（ラグランジュ）双対関数を とし、 を満たすものとすれば、 という条件と の正値定符号性を用いることで、 の下限を見つけることができる。
ゆえに双対関数は
であり、二次計画問題のラグランジュ双対は
となる。ラグランジュ双対理論の他にも他の双対性が存在する（例えば）。
複雑性 正値定符号行列である について楕円体法は多項式時間で二次計画問題を解くことができる Translated in: 。一方で、 の符号が不定ならば、二次計画問題はNP困難となる。実際、 のただ一つの固有値だけが負であったとしても、二次計画問題はNP困難である。
二次計画法のソルバーとプログラミング言語
名前要約 最適化とスケジューリング型問題のモデリングと計算のためのソフトウェアシステムALGLIB 二重ライセンス(GPL/proprietary)の数値ライブラリ(C++, .NET). 大規模数理最適化のための一般的なモデリング言語 LP、QP、NLP、MILP、MINLPMixed Integer Nonlinear Programming. 混合整数非線形計画問題のこと。、のための、MATLABとPython上のモデリングと最適化スイート。CGAL 二次計画法ソルバーを含むオープンソースの計算幾何パッケージ API(C,C++,Java,.Net, Python, Matlab, R)によるポピュラーなソルバー。大学向けは無料。CVXOPTPythonを元にした凸最適化のためのフリーパッケージ。softwareExcel のソルバー関数 関数の評価がセル上の再計算を元にした表計算に調整された非線形ソルバー。基本バージョンはExcelの標準アドオンとして利用できる。GALAHAD 凸、もしくは非凸二次計画法についての多様な方法を含む平滑非線形最適化のためのパッケージライブラリ。GAMS 数理最適化のためのハイレベルモデリングシステム。 大規模線形計画、二次計画、混合整数計画のための並列アルゴリズムを備えたソルバー。大学向けは無料。IMSL プログラマーが自身のソフトウェアアプリケーションに埋め込むことが可能な数学関数と統計関数のセット。IPOPT IPOPT (Interior Point OPTimizer) は大規模非線形最適化のためのソフトウェアパッケージである。JOptimizer 線形等式制約と凸不等式制約を含む最小化問題を解くためのオープンソースライブラリ（Javaで実装されている） 非線形最適化のための統合パッケージMaple 数学のための汎用的用途のプログラミング言語。Maple上で二次計画問題を解くにはQPSolveのコマンドを用いればよい。MATLAB 数値的計算のための汎用的用途の行列指向プログラミング言語。MATLAB上で二次計画法を行うにはMATLABの基本製品に加えて Optimization Toolbox が必要になる。Mathematica 数学のための汎用的用途のプログラミング言語でシンボリック計算と数値計算を含む。いくつかの言語(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は凸二次計画問題のためのオブジェクト指向の内点法ソルバーである。OpenOptPythonのためのBSDライセンスの数値最適化ライブラリ。QPのページを参照のこと。Eclipseのプラグインとして利用可能な複数のターゲットをサポートした最適化のためのJavaをベースとしたフリーのモデリング言語。qpOASESオンラインの有効制約法のオープンソースのC++実装R (Fortran)GPLライセンスのユニバーサルクロスプラットフォームの統計計算フレームワーク。quadprogページを参照のこと。MITライセンスの下でjavascriptに移植されている。LGPLの下でC#にも移植されている。/OR 線形、整数、非線形、微分不可、ネットワーク、組み合わせ、そして制約付きの最適化のためのソルバーのスイート。であるOPTMODELと特定の問題と市場を目標とした多様な垂直ソリューションはそのすべてが完全に上で統合されている。 宣言型のルールベース型言語に基づいた数理的モデリングと問題解決のためのソフトウェアシステムで Universal Technical Systems, Inc.により商品化されている。 MATLABのための、大域的最適化、整数計画問題、あらゆるタイプの最小二乗法、線形計画、二次計画、制約なし計画問題のサポート。TOMLABは、、、のようなソルバーをサポートしている。XPRESS大規模線形計画問題、二次計画問題、汎用非線形計画問題、混合整数問題のためのソルバー。いくつかのプログラミング言語のためのAPIとモデリング言語Moselを持ち合わせており、APML、GAMS上で起動する。大学向けは無料。
脚注
参考文献
A6: MP2, pg.245.
関連項目 サポートベクターマシン 逐次二次計画法 線形計画法
外部リンク 二次計画法についてのページ (英語) NEOS Optimization Guide: Quadratic Programming Solve an example Quadratic Programming (QP) problem