前提知識

$\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$$

が分かる。これで、弱双対定理の証明は終了である。
この不等式が、何を言っているかというと、もとの問題の最小値を下から押さえているのです。すげぇ！

次に、線形計画問題について、実際に見てみよう。
以下では、(めんどいので)、太字を省略します。ベクトルと行列です。
線形計画問題は以下のように、一般化できます。

$$\min{c^Tx} \\ s.t. \,Ax-b\geq0$$

ラグランジアンは、$\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$$

となります。

また今度もっと綺麗にまとめます。双対定理にも触れたいなぁ。