二次計画法(にじけいかくほう、英: quadratic programming, QP)は、数理最適化における非線形計画法の代表例の一つであり、いくつかの変数からなる二次関数を線形制約の下で最適化(最小化ないしは最大化)する方法である。二次計画法の対象となる最適化問題を二次計画問題という。 n の変数と m の制約からなる二次計画問題は以下のように定式化することができる[1]。 以下を所与とする: 二次計画問題の目的は以下の問題の解となる n 次元ベクトル x を見つけることである。 minimize {\displaystyle {\text{minimize}}} 1 2 x T Q x + c T x {\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} } ここで xT はベクトル x の転置を表す。Ax ? b という記法はベクトル Ax の全ての要素が対応するベクトル b の要素より小さいもしくは等しいことを意味する。 関係する最適化問題として、二次制約付き二次計画問題
問題の定式化
実数値の n 次元ベクトル c
n 行 n 列の実数値対称行列 Q
m 行 n 列の実数値行列 A
実数値の m 次元ベクトル b
subject to {\displaystyle {\text{subject to}}} A x ≤ b , {\displaystyle A\mathbf {x} \leq \mathbf {b} ,}
一般の問題について、多様な解法が広く用いられており、例えば
内点法
有効制約法
などがある。行列 Q が正値定符号ならば、問題はより一般的な凸最適化の領域の特殊ケースとなる。 二次計画問題は行列 Q が正値定符号であり、等式制約のみを含む時、特に簡単になり、解の過程は線形となる。ラグランジュの未定乗数法を用い、ラグランジアンの極値を探せば、以下の等式制約問題 Minimize 1 2 x T Q x + c T x {\displaystyle {\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} } , subject to E x = d {\displaystyle {\text{subject to}}\quad E\mathbf {x} =\mathbf {d} } . の解は次の線形システム [ Q E T E 0 ] [ x λ ] = [ − c d ] {\displaystyle {\begin{bmatrix}Q&E^{T}\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}} . の解として与えられることが容易に示される。ここで λ {\displaystyle \lambda } はラグランジュ乗数の集合で x と共に計算される。 このシステムを解く最も簡単な方法は直接的に問題を解くこと(例えばLU分解)で、問題の規模が小さければ非常に有用である。問題の規模が大きければ、このシステムは特異な難しさに直面する。もっとも重要なのは(Q が正値定符号であったとしても、)問題自体は正値定符号と決してならないことである。そのためうまくいく数値解法を見いだすことは非常に難しいので、問題に依存した様々な方法がある[4]。 もしも、制約があまり多くの変数を含んでいなければ、比較的簡単な方法として制約を無条件で満たすように変数を変換する方法がある。例えば、d = 0(非ゼロの場合にも一般化できる)と仮定する。制約方程式を見ると E x = 0 {\displaystyle E\mathbf {x} =0} . となる。新しい変数として y を以下のように定義する。 Z y = x {\displaystyle Z\mathbf {y} =\mathbf {x} } . ここで y の次元は x の次元から制約の数を引いたものである。この時、 E Z y = 0 {\displaystyle EZ\mathbf {y} =0} . であり、もし Z を EZ = 0 となるように選べば、制約方程式は常に満たされるようになる。このような Z を見つけるということは E の零空間を見つけることを意味し、E の構造に依存するが多かれ少なかれ単純である。二次形式に代入すると次の無制約の最小化問題が得られる。 1 2 x T Q x + c T x ⇒ 1 2 y T Z T Q Z y + ( Z T c ) T y . {\displaystyle {\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 Q Z y = − Z T c . {\displaystyle Z^{T}QZ\mathbf {y} =-Z^{T}\mathbf {c} .}
等式制約