Farkasの補題の証明をわかりやすく解説

2023年7月26日2023年11月24日

Farkasの補題を証明します。これは線形計画問題や最適化問題で重要な補題で、凸解析の分離定理を用いて証明します。連立方程式の解の存在と、連立不等式の解の存在のあいだの関係に示唆を与える補題でもあります。

Farkasの補題の証明をわかりやすく解説

Farkasの補題を証明するために、有限次元の凸解析における基本的な命題を復習しておきましょう。
コーシー列・収束列・下限・凸集合・閉包などの実数論あるいは集合位相の標準的な内容を分かっていれば理解することができます。

予備知識1：有限次元射影定理

定理：有限次元射影定理(原点版)

$K \subset \mathbb R^d$ を閉凸集合とする。
$x^* \in \mathbb R^d$ で
\begin{align*} ||x^* || \leq \inf_{x \in K} ||x|| \end{align*}
を満たすものが存在して、一意である。つまり、
\begin{align*}\inf_{x \in K} ||x|| \end{align*}
はユニークなミニマイザーをもつ。

証明：$\inf$ の定義から$x_n \in K$ で
\begin{align*} \inf_{x \in K} ||x|| \leq ||x_n || \leq \inf_{x \in K} ||x|| + \frac{1}{n}\end{align*}
を満たすものがとれる。

$\frac{1}{2}x_n + \frac{1}{2}x_m \in K$ なので、
\begin{align*} \inf_{x \in K} ||x|| \leq ||\frac{1}{2}x_n + \frac{1}{2}x_m|| \end{align*}
であることから、
\begin{align*} 4 \left( \inf_{x \in K} ||x||\right)^2 \leq || x_n + x_m ||^2 \geq \end{align*}
である。

中線定理
\begin{align*} || x_n – x_m||^2 + || x_n + x_m||^2 = 2||x_n|| ^2 + 2||x_m||^2 \end{align*}
を思い出すと、
\begin{align*}|| x_n – x_m||^2 = 2||x_n|| ^2 + 2||x_m||^2 – || x_n + x_m||^2 \leq 2||x_n||^2 + 2||x_m||^2 – 4 \left( \inf_{x \in K} ||x||\right)^2 \end{align*}
であるので、極限をとると$\lim_n ||x_n|| = \inf_{x \in K} ||x||$ であったことを思い出すと、
\begin{align*} || x_n – x_m||^2 \rightarrow 0\end{align*}
となるのでコーシー列である。

従って、$\mathbb R^n$ が完備なので$x_n$ は収束列であるので、収束先$x^*$ が存在する。
$K$ が閉集合であることから、$x^* \in K$ である。この$x^*$ が求めているミニマイザーである。

一意性を示しておく。もし異なるミニマイザーが存在すると、
\begin{align*} ||\frac{1}{2}(x + y))||^2 = \frac{1}{2}||x|| ^2 + \frac{1}{2}||y||^2 – || x – y||^2 \end{align*}
となり、$||x|| = ||y||, \,\, || x – y|| > 0$ であることから、
\begin{align*} ||\frac{1}{2}(x + y))|| < ||x|| \end{align*}
となってしまい、$x$ がミニマイザーでなくなってしまうので、ミニマイザーは一意である。

補足：原点$0$ が$p$ にくるように図形の位置関係を平行移動することで、以下の有名な定理が直ちに従う。

定理：有限次元射影定理

$K \subset \mathbb R^d$ を閉凸集合とする。
任意の$p \in \mathbb R^d$ に対して、$x^* \in \mathbb R^d$ で
\begin{align*} || p – x^* || \leq \inf_{x \in K} || p – x|| \end{align*}
を満たすものが存在して、一意である。

予備知識2：有限次元の分離超平面定理の一種

分離超平面の存在に関する命題はさまざまなバージョンが存在するが、次のものを用いることにする。

定理：有限次元の分離超平面定理の一種

$p \in \mathbb R^n$ とし、$K \subset $ を閉包が$p$を含まない凸集合とする。
このとき、$\xi \in \mathbb R^n$ で任意の$k \in K$ に対して
\begin{align*}(\xi, p) < (\xi, k) \end{align*}
を満たすものが存在する。

$K^\prime = K – p = \{k – p \mid k \in K \}$ と表すことにする。
$K^\prime$ の閉包は閉凸集合であるので、
\begin{align*} \xi \in \overline{K^\prime} \quad \textrm{s.t.} \quad ||\xi|| = \inf_{k \in K^\prime} ||k|| \end{align*}
が、有限次元射影定理から存在することがわかる。任意に$v = k – p \in K^\prime$ をとる。
$\xi, v$の凸結合$ (1-t)\xi + tv \in K^\prime$ を考える$0 \leq t \leq 1$。
$(1-t) \xi + tv = \xi + t(v – \xi) $ であるので、
\begin{align*} ||\xi ||^2 &\leq ||\xi + t(v-\xi)||^2 = ||\xi||^2 + 2t(\xi, v -\xi) + t^2||v-\xi||^2
\\&=||\xi||^2 + 2t(\xi, v) – 2t ||\xi||^2 + t^2||v-\xi||^2 \end{align*}
が得られる。従って、両辺から$||v||^2$を引くと
\begin{align*} 0 \leq 2t(\xi, v) – 2t ||\xi||^2 + t^2||v-\xi||^2 \end{align*}
が任意の$0 \leq t \leq 1$に対して成り立つ。$t$で割ると($t = 0$の時は次の式は自明)、
\begin{align*} 0 \leq 2(\xi, v) – 2 ||\xi||^2 + t||v-\xi||^2 \end{align*}
が得られる。$t \rightarrow 0$と極限をとることで、
\begin{align*} 0 \leq 2(\xi, v) – 2 ||\xi||^2 \end{align*}
が得られる。$v = k – p$ であったので、
\begin{align*} (\xi, p) + ||\xi||^2 \leq (\xi, k) \end{align*}
が成り立つ。

ここで、$p$ が$K$の閉包に含まれないことから、原点が$K^\prime = K – p$の閉包に含まれないので、
$|| \xi || > 0$ が成り立っている。従って、
\begin{align*} (\xi, p) < (\xi, p) + ||\xi||^2 \leq (\xi, k) \end{align*}
となり、証明が終了する。

Farkasの補題の証明

補題：Farkasの補題

$A$ を$n \times m$ 行列とし、$b$ を$n$ 次列ベクトルとする。このとき、
(1)非負$m$次列ベクトル$x \geq 0 $で$Ax = b$ を満たすものが存在する。
(2)任意の$n$次列ベクトル$y$に対して、$y^tA \geq 0 $ ならば$y^t b \geq 0$
は同値である。

証明：

(1)ならば(2)を示す。非負$m$次列ベクトル$x \geq 0 $で$Ax = b$ を満たすものをとる。
\begin{align*} y^tb = y^t Ax \geq 0 \end{align*}
より主張が従う。ただし最後の不等号は、$y^t A, x$ が共に非負であることから成り立つ。

(2)ならば(1)を示す。$A$の列ベクトルを$a_1, \ldots, a_m$ と表記することにする。
(背理法)(1)が成り立たないとすると、$b$は$a_1, \ldots, a_m$の凸錐結合で表せない。即ち、
\begin{align*} b \notin \{\sum_{i = 1}^m x_i a_i \mid x_1, \ldots, x_m \geq 0 \} \end{align*}
である。

$a_1, \ldots, a_m$の凸錐結合全体(つまり閉凸錐)は$ b $ を含まないので、
有限次元の超平面分離定理から適当な$y$で任意の$a \in \{\sum_{i = 1}^m x_i a_i \mid x_1, \ldots, x_m \geq 0 \} $ に対して、
\begin{align*} (y, b) < (y, a_1) , \ldots (y, a_m) \end{align*}
を満たすものが存在する。

特に$a$ として$a = 0, a_1, a_2, \ldots, a_m$ を考えることで
\begin{align*} (y, b) < (y, 0) = 0 \end{align*}
が得られる。また、もし$a_1, \ldots, a_m$の凸錐結合$a$で
\begin{align*} (y, a) < 0\end{align*}
であるものが存在してしまうと、$a$を$R>0$倍して、
\begin{align*} (y, Ra) < (y, b) \end{align*}
となるように十分大きな$R$ がとれてしまうが、$Ra$も凸錐結合で表されるのでこれはあり得ないので、任意の凸錐結合$a$に対して
\begin{align*} 0 \leq (y, a) \end{align*}
である。

このことはすなわち、$y^t A = ((y, a_1), \ldots, (y, a_m)) $であることに注意すると、
\begin{align*} (y, b) < 0, \quad 0 \leq y^t A \end{align*}
を満たす$y$ が存在することを意味している。これは、
(2)任意の$n$次列ベクトル$y$に対して、$y^tA \geq 0 $ ならば$y^t b \geq 0$
と矛盾する。

以上で証明を終了する。

補足：Farkasの補題は択一定理(Alternative)的な書き方を以下のようにすることができる。

補題：Farkasの補題の択一定理的な書き方

$A$ を$n \times m$ 行列とし、$b$ を$n$ 次列ベクトルとする。このとき、
(1)非負$m$次列ベクトル$x \geq 0 $で$Ax = b$ を満たすものが存在する。
(2)$n$次列ベクトル$y$で、$(y, b)$かつ$0 \leq y^tA $であるものが存在する。
のいずれか一方のみが成り立つ。