ラグランジュ双対
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/02 19:43 UTC 版)
「双対問題」も参照 二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、c = 0 かつ Q が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。 L ( x , λ ) = 1 2 x T Q x + λ T ( A x − b ) . {\displaystyle L(x,\lambda )={\tfrac {1}{2}}x^{T}Qx+\lambda ^{T}(Ax-b).} （ラグランジュ）双対関数を g ( λ ) {\displaystyle g(\lambda )} とし、 g ( λ ) = inf x L ( x , λ ) {\displaystyle g(\lambda )=\inf _{x}L(x,\lambda )} を満たすものとすれば、 ∇ x L ( x , λ ) = 0 {\displaystyle \nabla _{x}L(x,\lambda )=0} という条件と Q の正値定符号性を用いることで、L の下限を見つけることができる。 x ∗ = − Q − 1 A T λ . {\displaystyle x^{*}=-Q^{-1}A^{T}\lambda .} ゆえに双対関数は g ( λ ) = − 1 2 λ T A Q − 1 A T λ − λ T b , {\displaystyle g(\lambda )=-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b,} であり、二次計画問題のラグランジュ双対は maximize − 1 2 λ T A Q − 1 A T λ − λ T b {\displaystyle {\text{ maximize}}\quad -{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b} subject to λ ⩾ 0 {\displaystyle \,\,{\text{subject to}}\quad \lambda \geqslant 0} となる。ラグランジュ双対理論の他にも他の双対性が存在する（例えばWolfe双対（英語版））。
※この「ラグランジュ双対」の解説は、「二次計画法」の解説の一部です。
「ラグランジュ双対」を含む「二次計画法」の記事については、「二次計画法」の概要を参照ください。
- ラグランジュ双対のページへのリンク
