二次計画法のソースを表示

'''二次計画法'''（にじけいかくほう、{{lang-en-short|quadratic programming, QP}}）は、[[数理最適化]]における[[非線形計画法]]の代表例の一つであり、いくつかの変数からなる[[二次関数]]を線形制約の下で最適化（最小化ないしは最大化）する方法である。二次計画法の対象となる[[最適化問題]]を'''二次計画問題'''という。

== 問題の定式化 ==
{{mvar|n}} の変数と {{mvar|m}} の制約からなる二次計画問題は以下のように定式化することができる<ref>{{Cite book 
| last1=Nocedal 
| first1=Jorge 
| last2=Wright 
| first2=Stephen J. 
| title=Numerical Optimization 
| publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-0-387-30303-1 | year=2006 | page=449 | postscript=<!--None--> }}.</ref>。

以下を所与とする：
* 実数値の {{mvar|n}} 次元ベクトル {{math|'''c'''}}
* {{mvar|n}} 行 {{mvar|n}} 列の実数値[[対称行列]] {{mvar|Q}}
* {{mvar|m}} 行 {{mvar|n}} 列の実数値行列 {{mvar|A}}
* 実数値の {{mvar|m}} 次元ベクトル {{math|'''b'''}}
二次計画問題の目的は以下の問題の解となる {{mvar|n}} 次元ベクトル {{math|'''x'''}} を見つけることである。

{| cellspacing="10"
|-
| <math>\text{minimize}</math>
| <math>\tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}</math>
|-
| <math>\text{subject to}</math>
| <math> A \mathbf{x} \leq \mathbf{b},</math>
|}

ここで {{math|'''x'''<sup>T</sup>}} はベクトル {{math|'''x'''}} の[[転置行列|転置]]を表す。{{math|''A'''''x''' ≤ '''b'''}} という記法はベクトル {{math|''A'''''x'''}} の全ての要素が対応するベクトル {{math|'''b'''}} の要素より小さいもしくは等しいことを意味する。

関係する最適化問題として、{{仮リンク|二次制約付き二次計画問題|en|quadratically constrained quadratic program}}があり、二次制約付き二次計画問題では二次の制約が足されている。

== 解法 ==
一般の問題について、多様な解法が広く用いられており、例えば
:* [[内点法]]
:* [[有効制約法]]<ref name="ioe.engin.umich">{{cite book|last=Murty|first=Katta G.|title=Linear complementarity, linear and nonlinear programming|series=Sigma Series in Applied Mathematics|volume=3|publisher=Heldermann Verlag|location=Berlin|year=1988|pages=xlviii+629 pp.|isbn=3-88538-403-5|url=http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|mr=949214|archiveurl=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archivedate=2010年4月1日|deadlinkdate=2017年9月}}</ref>
:* [[拡張ラグランジュ乗数法]]<ref>{{cite journal | first1 = F. | last1 = Delbos | first2 = J.Ch. | last2 = Gilbert | year = 2005 | title = Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems | journal = Journal of Convex Analysis | volume = 12 | pages = 45–69 |url=http://www.heldermann-verlag.de/jca/jca12/jca1203_b.pdf}}</ref>
:* [[共役勾配法]]
:* 勾配射影法
:* [[シンプレックス法]]の拡張<ref name="ioe.engin.umich" />

などがある。行列 {{mvar|Q}} が[[定符号二次形式|正値定符号]]ならば、問題はより一般的な[[凸最適化]]の領域の特殊ケースとなる。

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

:<math>\text{Minimize} \quad \tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}</math>,

:<math>\text{subject to} \quad E\mathbf{x} =\mathbf{d}</math>.

の解は次の線形システム

:<math>
\begin{bmatrix}
   Q & E^T \\
   E & 0
\end{bmatrix} 
\begin{bmatrix}
   \mathbf x \\
   \lambda
\end{bmatrix}
= 
\begin{bmatrix}
   -\mathbf c \\
   \mathbf d
\end{bmatrix}
</math>.

の解として与えられることが容易に示される。ここで <math>\lambda</math> はラグランジュ乗数の集合で {{math|'''x'''}} と共に計算される。

このシステムを解く最も簡単な方法は直接的に問題を解くこと（例えば[[LU分解]]）で、問題の規模が小さければ非常に有用である。問題の規模が大きければ、このシステムは特異な難しさに直面する。もっとも重要なのは（{{mvar|Q}} が正値定符号であったとしても、）問題自体は正値定符号と決してならないことである。そのためうまくいく数値解法を見いだすことは非常に難しいので、問題に依存した様々な方法がある<ref>[https://scholar.google.com/scholar?hl=en&q=saddle+point+indefinite+constrained+linear Google search.]</ref>。

もしも、制約があまり多くの変数を含んでいなければ、比較的簡単な方法として制約を無条件で満たすように変数を変換する方法がある。例えば、{{math|'''d''' {{=}} 0}}（非ゼロの場合にも一般化できる）と仮定する。制約方程式を見ると

:<math>E\mathbf{x} = 0</math>.

となる。新しい変数として {{math|'''y'''}} を以下のように定義する。

:<math>Z \mathbf{y} = \mathbf x</math>.

ここで {{math|'''y'''}} の次元は {{math|'''x'''}} の次元から制約の数を引いたものである。この時、

:<math>E Z \mathbf{y} = 0</math>.

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

:<math>
\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 Q Z \mathbf{y} + (Z^T \mathbf{c})^T \mathbf{y}.
</math>

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

:<math>
Z^T Q Z \mathbf{y} = -Z^T \mathbf{c}.
</math>

{{mvar|Q}} についてのある条件の下で、退化した行列 {{math|''Z{{sup|T}}QZ''}} は正値定符号となる。{{mvar|Z}} の陽な計算を避けた[[共役勾配法]]のバリエーションとして書くことも可能である<ref>{{Cite journal
| last1 = Gould
| first1 = Nicholas I. M.
| last2 = Hribar
| first2 = Mary E.
| last3 = Nocedal
| first3 = Jorge
|date=April 2001
| title = On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization
| publisher = SIAM Journal of Scientific Computing
| publication-place = 
| pages = 1376–1395
| volume = 23
| issue = 4
| id = {{citeseerx|10.1.1.129.7555}}
| accessdate =
}}</ref>。

== ラグランジュ双対 ==
{{See also|双対問題}}
二次計画問題のラグランジュ[[双対問題|双対]]はまた二次計画問題となる。これを見るために、{{math|''c'' {{=}} 0}} かつ {{mvar|Q}} が正値定符号であるケースに着目しよう。[[ラグランジュの未定乗数法|ラグランジュ]]関数は以下のように書ける。

:<math>L(x,\lambda) = \tfrac{1}{2} x^{T}Qx + \lambda^{T}(Ax-b). </math>

（ラグランジュ）双対関数を <math>g(\lambda)</math> とし、<math>g(\lambda) = \inf_{x} L(x,\lambda) </math> を満たすものとすれば、<math>\nabla_{x} L(x,\lambda)=0</math> という条件と {{mvar|Q}} の正値定符号性を用いることで、{{mvar|L}} の下限を見つけることができる。

:{{big|<math> x^* =  -Q^{-1}A^{T}\lambda.  </math>}}

ゆえに双対関数は

:<math>g(\lambda) = -\tfrac{1}{2}\lambda^{T}AQ^{-1}A^{T}\lambda - \lambda^{T}b,</math>

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

:<math>\text{ maximize} \quad  -\tfrac{1}{2}\lambda^{T}AQ^{-1}A^{T}\lambda - \lambda^{T}b</math>

:<math>\, \, \text{subject to} \quad \lambda \geqslant 0</math>

となる。ラグランジュ双対理論の他にも他の双対性が存在する（例えば{{仮リンク|Wolfe双対|en|Wolfe duality}}）。

== 複雑性 ==
[[定符号二次形式|正値定符号]]行列である {{mvar|Q}} について[[楕円体法]]は[[多項式時間]]で二次計画問題を解くことができる<ref>{{cite journal| last=Kozlov | first=M. K. |author2=S. P. Tarasov |author3=[[Leonid Khachiyan|Leonid G. Khachiyan]] | year=1979 | title=[Polynomial solvability of convex quadratic programming] | journal=[[Doklady Akademii Nauk SSSR]] | volume=248 | pages=1049–1051}} Translated in: {{cite journal| journal=Soviet Mathematics - Doklady | volume=20 | pages=1108–1111}}</ref>。一方で、{{mvar|Q}} の符号が不定ならば、二次計画問題は[[NP困難]]となる<ref>{{cite journal | last = Sahni | first = S. | title = Computationally related problems | journal = SIAM Journal on Computing | volume = 3 | pages = 262–279 | year = 1974 | doi=10.1137/0203021}}</ref>。実際、{{mvar|Q}} のただ一つの[[固有値]]だけが負であったとしても、二次計画問題は[[NP困難]]である<ref>{{cite journal | title = Quadratic programming with one negative eigenvalue is NP-hard | first1 = Panos M. | last1 = Pardalos | first2 = Stephen A. | last2 = Vavasis | journal = Journal of Global Optimization | volume = 1 | issue = 1 | year = 1991 | pages = 15–22 | doi=10.1007/bf00120662}}</ref>。

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

{| class="wikitable"
|-
!名前
!要約
|-
|{{仮リンク|AIMMS|en|AIMMS}}|| 最適化とスケジューリング型問題のモデリングと計算のためのソフトウェアシステム
|-
|[[ALGLIB]]|| 二重ライセンス(GPL/proprietary)の数値ライブラリ(C++, .NET).
|-
|{{仮リンク|AMPL|en|AMPL}}|| 大規模数理最適化のための一般的なモデリング言語
|-
|{{仮リンク|APMonitor|en|APMonitor}}|| [[線形計画法|LP]]、QP、[[非線形計画法|NLP]]、[[整数計画問題|MILP]]、MINLP<ref>Mixed Integer Nonlinear Programming. 混合整数非線形計画問題のこと。</ref>、{{仮リンク|微分代数方程式|label=DAE|en|differential algebraic equation}}のための、MATLABとPython上のモデリングと最適化スイート。
|-
|[[CGAL]]|| 二次計画法ソルバーを含むオープンソースの計算幾何パッケージ
|-
|{{仮リンク|CPLEX|en|CPLEX}}|| API(C,C++,Java,.Net, Python, Matlab, R)によるポピュラーなソルバー。大学向けは無料。
|-
|CVXOPT||Pythonを元にした凸最適化のためのフリーパッケージ。[http://cvxopt.org/ software]
|-
|[[Microsoft Excel|Excel]] のソルバー関数|| 関数の評価がセル上の再計算を元にした表計算に調整された非線形ソルバー。基本バージョンはExcelの標準アドオンとして利用できる。
|-
|[http://www.galahad.rl.ac.uk/ GALAHAD]|| 凸、もしくは非凸二次計画法についての多様な方法を含む平滑非線形最適化のためのパッケージライブラリ。
|-
|[[General Algebraic Modeling System|GAMS]] || 数理最適化のためのハイレベルモデリングシステム。
|-
|{{仮リンク|Gurobi|de|Gurobi}}|| 大規模線形計画、二次計画、混合整数計画のための並列アルゴリズムを備えたソルバー。大学向けは無料。
|-
|[[IMSL]]|| プログラマーが自身のソフトウェアアプリケーションに埋め込むことが可能な数学関数と統計関数のセット。
|-
|[[IPOPT]]|| IPOPT (Interior Point OPTimizer) は大規模非線形最適化のためのソフトウェアパッケージである。
|- 
|JOptimizer || 線形等式制約と凸不等式制約を含む最小化問題を解くためのオープンソースライブラリ（Javaで実装されている）
|-
|{{仮リンク|Artelys Knitro|en|Artelys Knitro}} || 非線形最適化のための統合パッケージ
|-
|[[Maple]]|| 数学のための汎用的用途のプログラミング言語。Maple上で二次計画問題を解くには[http://www.maplesoft.com/support/help/Maple/view.aspx?path=Optimization/QPSolve QPSolve]のコマンドを用いればよい。
|-
|[[MATLAB]]|| 数値的計算のための汎用的用途の行列指向プログラミング言語。MATLAB上で二次計画法を行うにはMATLABの基本製品に加えて Optimization Toolbox が必要になる。
|-
|[[Mathematica]]|| 数学のための汎用的用途のプログラミング言語でシンボリック計算と数値計算を含む。
|-
|{{仮リンク|MOSEK|en|MOSEK}}||いくつかの言語(C++,java,.net, Matlab, python)のためのAPIを持つ大規模最適化のためのソルバー。
|-
|[[NAG数値計算ライブラリ]]||複数のプログラミング言語(C, C++, Fortran, Visual Basic, Java, C#)とパッケージ(MATLAB, Excel, R, LabVIEW)のための[[Numerical Algorithms Group]]によって開発された数学ルーチンと統計ルーチンの集まり。NAGライブラリの最適化チャプターには疎線形制約行列と非疎線形制約行列を持つ二次計画問題のルーチンが、非線形、有界、もしくは制約なしの線形ないしは非線形関数の線形、非線和、二乗和の最適化のためのルーチンとともに含まれている。NAGライブラリは局所最適化と大域的最適化のためと連続もしくは整数問題のためのルーチンが含まれている。
|-
|[http://pages.cs.wisc.edu/~swright/ooqp/ OOQP]|| OOQPは凸二次計画問題のためのオブジェクト指向の内点法ソルバーである<ref>{{cite web
 |author1=E. Michael Gertz
 |author2=Stephen J. Wright
 |title=Object-Oriented Software for Quadratic Programming (Paper)
 |url=http://pages.cs.wisc.edu/~swright/ooqp/ooqp-paper.pdf
 |publisher=University of Wisconsin-Madison
 |accessdate=11 July 2014
 |format=PDF
 |date=25 February 2003
}}</ref><ref>
{{cite web
 |author1=E. Michael Gertz
 |title=Source repository for OOQP, a quadratic programming solver (and more)
 |url=https://github.com/emgertz/OOQP
 |website=[[GitHub]]
 |accessdate=11 July 2014
}}</ref>。
|-
|OpenOpt||Pythonのための[[BSDライセンス]]の数値最適化ライブラリ。[https://web.archive.org/web/20110201043008/http://openopt.org/QP QP]のページを参照のこと。
|-
|{{仮リンク|OptimJ|en|OptimJ}}||Eclipseのプラグインとして利用可能な複数のターゲットをサポートした最適化のためのJavaをベースとしたフリーのモデリング言語<ref>{{cite journal | url = http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf | title = OptimJ used in an optimization model for mixed-model assembly lines | publisher = University of Münster}}</ref><ref>{{cite journal | url = http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 | title = OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games }}</ref>。
|-
|[http://qpoases.org qpOASES]||オンラインの有効制約法のオープンソースのC++実装
|-
|[[R言語|R]] (Fortran)||[[GPL]]ライセンスのユニバーサルクロスプラットフォームの統計計算フレームワーク。[https://cran.r-project.org/web/packages/quadprog/index.html quadprog]ページを参照のこと。[[MIT License]]の下で[https://github.com/albertosantini/node-quadprog javascriptに移植されている。][[LGPL]]の下で[http://accord-framework.net/ C#にも移植されている。]
|-
|{{仮リンク|SAS System|label=SAS|en|SAS System}}/OR|| 線形、整数、非線形、微分不可、ネットワーク、組み合わせ、そして制約付きの最適化のためのソルバーのスイート。{{仮リンク|algebraic modeling language|en|algebraic modeling language}}である[http://support.sas.com/documentation/cdl/en/ormpug/63975/HTML/default/ormpug_optmodel_sect005.htm OPTMODEL]と特定の問題と市場を目標とした多様な垂直ソリューションはそのすべてが完全に{{仮リンク|SAS System|en|SAS System}}上で統合されている。
|-
|{{仮リンク|TK Solver|en|TK Solver}}|| 宣言型のルールベース型言語に基づいた数理的モデリングと問題解決のためのソフトウェアシステムで[http://www.uts.com  Universal Technical Systems, Inc.]により商品化されている。
|-
|{{仮リンク|TOMLAB|en|TOMLAB}}|| [[MATLAB]]のための、大域的最適化、整数計画問題、あらゆるタイプの最小二乗法、線形計画、二次計画、制約なし計画問題のサポート。TOMLABは{{仮リンク|Gurobi|de|Gurobi}}、{{仮リンク|CPLEX|en|CPLEX}}、{{仮リンク|SNOPT|en|SNOPT}}、{{仮リンク|KNITRO|en|KNITRO}}のようなソルバーをサポートしている。
|-
|XPRESS||大規模線形計画問題、二次計画問題、汎用非線形計画問題、混合整数問題のためのソルバー。いくつかのプログラミング言語のためのAPIとモデリング言語Moselを持ち合わせており、APML、[[General Algebraic Modeling System|GAMS]]上で起動する。大学向けは無料。
|}

== 脚注 ==
{{脚注ヘルプ}}
{{reflist|2}}

== 参考文献 ==
* {{cite book|last1=Cottle|first1=Richard W.|last2=Pang|first2=Jong-Shi|last3=Stone|first3=Richard E.|title=The linear complementarity problem | series=Computer Science and Scientific Computing|publisher=Academic Press, Inc.|location=Boston, MA|year=1992|pages=xxiv+762 pp.|isbn=0-12-192350-9 | mr = 1150683 }}
* {{cite book|authorlink1=Michael R. Garey|first1=Michael R.|last1=Garey|authorlink2=David S. Johnson|last2=Johnson|first2=David S.| year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} A6: MP2, pg.245.

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

== 外部リンク ==
*[http://www.numerical.rl.ac.uk/qp/qp.html 二次計画法についてのページ (英語)]
*[http://neos-guide.org/content/quadratic-programming NEOS Optimization Guide: Quadratic Programming]
*[http://apmonitor.com/online/view_pass.php?f=qp2.apm Solve an example Quadratic Programming (QP) problem]

{{主要な最適化問題の分類}}
{{最適化アルゴリズム}}

{{デフォルトソート:にしけいかくほう}}
[[Category:最適化]]
[[Category:数学に関する記事]]