Loading AI tools
ウィキペディアから
二次計画法(にじけいかくほう、英: quadratic programming, QP)は、数理最適化における非線形計画法の代表例の一つであり、いくつかの変数からなる二次関数を線形制約の下で最適化(最小化ないしは最大化)する方法である。二次計画法の対象となる最適化問題を二次計画問題という。
n の変数と m の制約からなる二次計画問題は以下のように定式化することができる[1]。
以下を所与とする:
二次計画問題の目的は以下の問題の解となる n 次元ベクトル x を見つけることである。
ここで xT はベクトル x の転置を表す。Ax ≤ b という記法はベクトル Ax の全ての要素が対応するベクトル b の要素より小さいもしくは等しいことを意味する。
関係する最適化問題として、二次制約付き二次計画問題があり、二次制約付き二次計画問題では二次の制約が足されている。
一般の問題について、多様な解法が広く用いられており、例えば
などがある。行列 Q が正値定符号ならば、問題はより一般的な凸最適化の領域の特殊ケースとなる。
二次計画問題は行列 Q が正値定符号であり、等式制約のみを含む時、特に簡単になり、解の過程は線形となる。ラグランジュの未定乗数法を用い、ラグランジアンの極値を探せば、以下の等式制約問題
の解は次の線形システム
の解として与えられることが容易に示される。ここで はラグランジュ乗数の集合で x と共に計算される。
このシステムを解く最も簡単な方法は直接的に問題を解くこと(例えばLU分解)で、問題の規模が小さければ非常に有用である。問題の規模が大きければ、このシステムは特異な難しさに直面する。もっとも重要なのは(Q が正値定符号であったとしても、)問題自体は正値定符号と決してならないことである。そのためうまくいく数値解法を見いだすことは非常に難しいので、問題に依存した様々な方法がある[4]。
もしも、制約があまり多くの変数を含んでいなければ、比較的簡単な方法として制約を無条件で満たすように変数を変換する方法がある。例えば、d = 0(非ゼロの場合にも一般化できる)と仮定する。制約方程式を見ると
となる。新しい変数として y を以下のように定義する。
ここで y の次元は x の次元から制約の数を引いたものである。この時、
であり、もし Z を EZ = 0 となるように選べば、制約方程式は常に満たされるようになる。このような Z を見つけるということは E の零空間を見つけることを意味し、E の構造に依存するが多かれ少なかれ単純である。二次形式に代入すると次の無制約の最小化問題が得られる。
この解は以下で与えられる。
Q についてのある条件の下で、退化した行列 ZTQZ は正値定符号となる。Z の陽な計算を避けた共役勾配法のバリエーションとして書くことも可能である[5]。
二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、c = 0 かつ Q が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。
(ラグランジュ)双対関数を とし、 を満たすものとすれば、 という条件と Q の正値定符号性を用いることで、L の下限を見つけることができる。
ゆえに双対関数は
であり、二次計画問題のラグランジュ双対は
となる。ラグランジュ双対理論の他にも他の双対性が存在する(例えば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上で起動する。大学向けは無料。 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.