ラグランジュの双対性

【らぐらんじゅのそうついせい (Lagrange duality)】

ラグランジュ関数 $L\,$ に対して定義された以下の主問題とその双対問題の間に成立する双対性のこと.

\[ \begin{array}{cll} \mbox{(P}_{L}\mbox{)} & \mbox{min.} & \displaystyle\sup_{\lambda\ge{0},\mu}L(x,\lambda,\mu) \\

                     & \mbox{s.t.} & \displaystyle{x\in{{\bf R}^n}}   \\

\mbox{(D}_{L}\mbox{)} & \mbox{max.} & \displaystyle\inf_{x}L(x,\lambda,\mu) \\

                     & \mbox{s.t.} & \displaystyle{0\le\lambda\in{{\bf R}^{k}}}, \: 
                      \displaystyle\mu\in{{\bf R}^{l}}

\end{array} \]

$L\,$ の鞍点 $({\bar {x}},{\bar {\lambda }},{\bar {\mu }})\,$ が存在すれば, ${\bar {x}}\,$ と $({\bar {\lambda }},{\bar {\mu }})\,$ はそれぞれ問題(P$_{L}\,$)と(D$_{L}\,$)の最適解となり最適値が一致する.