目次
前提知識
$\inf$と$\sup$あたりの理解。
本題
なんとなく思い出したので、弱双対定理の証明メモ。雑です(泣)以下の問題を考える。
$$\gdef\l{\mathcal{L}} \gdef\x{\bm{x}} \min{f(\x)} \\ s.t. \,\bm{g}(\x)\geq0,\,\bm{h}(\x)=0$$実行可能領域を$\Omega$とする。次に、ラグランジアン$\l$を定義する。
$$\l=f(\x)-\bm{\mu}^T\bm{g}(\x)-\bm{\lambda}^T\bm{h}(\x)$$$\sup_{\bm{\mu}\geq0,\,\bm{\lambda}\in\R}$を考えると、以下のようになる。
$$\sup_{\bm{\mu}\geq0,\,\bm{\lambda}\in\R} \mathcal{L}= \begin{cases} f(\x)\,(x\in\Omega) \\ \infty \,(x\notin\Omega) \end{cases}$$したがって、最初の最小化問題は、次式に書き換えられる。
$$\inf_x\sup_{\bm{\mu}\geq0,\,\bm{\lambda}\in\R} \mathcal{L}$$ここで、ごく当たり前の不等式を考える。
$$\inf_x\mathcal{L}\leq\l$$両辺の$\sup_{\bm{\mu}\geq0,\,\bm{\lambda}\in\R}$を考えると、
$$\sup_{\bm{\mu}\geq0,\,\bm{\lambda}\in\R}\inf_x\mathcal{L}\leq \sup_{\bm{\mu}\geq0,\,\bm{\lambda}\in\R}\l$$さらに、両辺の$\inf_x$を考えると、左辺は定数なので、
$$\sup_{\bm{\mu}\geq0,\,\bm{\lambda}\in\R}\inf_x\mathcal{L}\leq \inf_x \sup_{\bm{\mu}\geq0,\,\bm{\lambda}\in\R}\l$$が分かる。これで、弱双対定理の証明は終了である。
この不等式が、何を言っているかというと、もとの問題の最小値を下から押さえているのです。すげぇ!
線形計画問題における弱双対定理
次に、線形計画問題について、実際に見てみよう。
以下では、(めんどいので)、太字を省略します。ベクトルと行列です。
線形計画問題は以下のように、一般化できます。
ラグランジアンは、$\l=c^Tx-\mu^T(Ax-b)$です。
$$\inf_x\mathcal{L}=\inf_x (c^T-\mu^TA)x+\mu^Tb= \begin{cases} \mu^Tb\,(A^T\mu-c=0) \\ -\infty \,(A^T\mu-c\neq0) \end{cases}$$より、
$$\sup_{\bm{\mu}\geq0}\inf_x\mathcal{L}$$は、
$$\max{b^T\mu} \\ s.t. \,A^T\mu-c=0,\,\mu\geq 0$$となります。
あとがき
また今度もっと綺麗にまとめます。双対定理にも触れたいなぁ。