制約 (数学)
等式制約
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/02 19:43 UTC 版)
二次計画問題は行列 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 が正値定符号であったとしても、）問題自体は正値定符号と決してならないことである。良い数値解法を見つけることは潜在的に非常に難しく、問題に依存した様々な方法がある。 もし、制約が変数をそう含んでないのであれば、相対的に簡単な方法として変数を変換し制約を無条件で満たすようにすることがある。例えば、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} } Q についてのある条件の下で、退化した行列 ZTQZ は正値定符号となる。Z の陽な計算を避けた共役勾配法のバリエーションとして書くことも可能である。
※この「等式制約」の解説は、「二次計画法」の解説の一部です。
「等式制約」を含む「二次計画法」の記事については、「二次計画法」の概要を参照ください。
- 等式制約のページへのリンク
