Farkasの補題
概要
Farkasの補題（Farkas' lemma）とは、実行列 $A$ と実ベクトル $b$ について、「$Ax=b$、$x\ge0$ に解がある」と「$A^{\mathsf T}y\ge0$、$b\cdot y< 0$ に解がある」のちょうど一方が成り立つ、という定理である（不等号は成分ごと）。有限個のベクトルが生成する錐の外の点は、原点を通る超平面で錐から分離できることを述べ、1 次不等式系に解がないことの検算できる証拠を与える。不等式の形や Gordan の定理などの択一定理、線形計画法の双対定理の土台になる。生成元が無限個の場合や整数解に限る場合には、一般には成り立たない。
Farkasの補題（Farkas' lemma）とは、実数の $m\times n$ 行列 $A$ と $b\in\mathbb{R}^m$ について、
- $Ax=b$、$x\ge0$ を満たす $x\in\mathbb{R}^n$ がある
- $A^{\mathsf T}y\ge0$、$b\cdot y< 0$ を満たす $y\in\mathbb{R}^m$ がある
のちょうど一方が成り立つ、という定理である（ベクトルの不等号は成分ごと）。1 は「$b$ が $A$ の列ベクトルの $0$ 以上の係数による 1 次結合で書ける」こと、2 は「原点を通る超平面 $\{v\mid y\cdot v=0\}$ が、$A$ の列ベクトルをすべて一方の側に、$b$ を反対の側に分ける」ことである。有限個のベクトルが生成する錐と、その外の点は、原点を通る超平面で分離できる、という分離定理である。
1 次の等式・不等式の系が解をもつことは解を 1 つ示せば確かめられるが、解をもたないことを確かめるのは一般には難しい。Farkas の補題は、解がないときにはいつも 2 のような $y$ が「解がないことの証拠」として存在し、その証拠は代入だけで検算できることを保証する。不等式の系の形を変えた同様の定理（Gordan の定理など）をまとめて 択一定理（theorem of alternatives）といい、線形計画法の双対定理や、凸最適化の最適性条件の土台になる。
この記事では、錐が閉じていることと最短点の性質を使って主定理を証明し、不等式の形・Gordan の定理・狭義と非狭義が混ざった形を導く。最後に、生成元が無限個の場合や、整数解に限る場合などで定理が成り立たなくなる例を挙げる。
記号
$\mathbb{R}^m$ の内積を $u\cdot v$、長さを $\lvert v\rvert=\sqrt{v\cdot v}$ と書く。ベクトルの不等式 $u\le v$、$u\ge0$、$u< v$ は成分ごとの不等式を表す。$a_1,\dots,a_n\in\mathbb{R}^m$ について
$$
\operatorname{cone}\{a_1,\dots,a_n\}:=\Bigl\{\sum_{j=1}^nx_ja_j\ \Bigm|\ x_1,\dots,x_n\ge0\Bigr\}
$$
を $a_1,\dots,a_n$ が 生成する錐 という（凸錐 の定義「生成される錐・有限生成の錐・多面錐」）。$A$ の列を $a_1,\dots,a_n$ とすれば、これは $\{Ax\mid x\ge0\}$ であり、和と $0$ 以上の数倍で閉じている。
2 つの補題
$b\in\operatorname{cone}\{a_1,\dots,a_n\}$ なら、$\{1,\dots,n\}$ の部分集合 $J$ で、$\{a_j\}_{j\in J}$ が 1 次独立かつ $b\in\operatorname{cone}\{a_j\mid j\in J\}$ となるものがある（$b=0$ なら $J=\emptyset$ とし、空集合の生成する錐は $\{0\}$ と読む）。
$b=\sum_{j\in J}x_ja_j$（$x_j>0$）と書ける $J$ のうち、要素の個数が最小のものをとる。$\{a_j\}_{j\in J}$ が 1 次従属だとすると、すべてが $0$ ではない実数の組 $(t_j)_{j\in J}$ で $\sum_jt_ja_j=0$ となるものがあり、符号を替えて正の $t_j$ があるとしてよい。$s:=\min\{x_j/t_j\mid t_j>0\}$ とおくと、$x_j-st_j\ge0$ がすべての $j$ で成り立ち、最小を与える $j$ では $0$ になる。$b=\sum_j(x_j-st_j)a_j$ なので、係数が正の $j$ だけを残すと $J$ より小さい集合で $b$ が書けて、最小性に反する。よって $\{a_j\}_{j\in J}$ は 1 次独立である。$\square$
$K=\operatorname{cone}\{a_1,\dots,a_n\}$ は $\mathbb{R}^m$ の閉集合である。
lem-fk-caratheodory により、$K$ は、$\{a_j\}_{j\in J}$ が 1 次独立となる有限個の $J$ についての $K_J:=\operatorname{cone}\{a_j\mid j\in J\}$ の和集合である。有限個の閉集合の和集合は閉なので、各 $K_J$ が閉であることを示せばよい。
$J=\{j_1,\dots,j_k\}$ とし、$M:=(a_{j_1}\ \cdots\ a_{j_k})$（$m\times k$ 行列）とおくと $K_J=\{Mz\mid z\in\mathbb{R}^k,\ z\ge0\}$ である。$M$ の列は 1 次独立なので、単位球面 $\{\lvert z\rvert=1\}$（コンパクト）の上で連続関数 $\lvert Mz\rvert$ は正の最小値 $c$ をとり、すべての $z$ で $\lvert Mz\rvert\ge c\lvert z\rvert$ である。$K_J$ の点列 $Mz^{(\nu)}$（$z^{(\nu)}\ge0$）が $w$ に収束するとすると、$\lvert z^{(\nu)}-z^{(\mu)}\rvert\le c^{-1}\lvert Mz^{(\nu)}-Mz^{(\mu)}\rvert$ なので $z^{(\nu)}$ は Cauchy 列で、ある $z$ に収束する。成分ごとの極限で $z\ge0$ であり、$w=\lim Mz^{(\nu)}=Mz\in K_J$ である。$\square$
この 2 つの補題は 凸錐 の定理「錐の Carathéodory の定理」と定理「有限生成の錐は閉じている」と同じ内容である。「有限生成」が本質的であることは、反例の表の 1 行目で見る。
主定理
$A\in\mathbb{R}^{m\times n}$、$b\in\mathbb{R}^m$ とする。次の 2 つのうち、ちょうど一方が成り立つ。
- $Ax=b$、$x\ge0$ を満たす $x\in\mathbb{R}^n$ がある。
- $A^{\mathsf T}y\ge0$、$b\cdot y< 0$ を満たす $y\in\mathbb{R}^m$ がある。
両方は成り立たない。 1 の $x$ と 2 の $y$ があるとすると、$x\ge0$ と $A^{\mathsf T}y\ge0$ から
$$
b\cdot y=(Ax)\cdot y=x\cdot(A^{\mathsf T}y)\ge0
$$
となり、$b\cdot y< 0$ に反する。
1 が成り立たなければ 2 が成り立つ。 $K:=\{Ax\mid x\ge0\}=\operatorname{cone}\{a_1,\dots,a_n\}$ とおく（$a_j$ は $A$ の列）。仮定は $b\notin K$ である。
段 1（最短点）。$K$ は $0$ を含む閉集合（lem-fk-closed）なので、$K\cap\{v\mid\lvert v-b\rvert\le\lvert b\rvert\}$ は空でない有界閉集合で、連続関数 $v\mapsto\lvert v-b\rvert$ はその上で最小値をとる。その最小点 $p$ は $K$ 全体での $b$ への最短点である。$y:=p-b$ とおく。$b\notin K$ なので $y\ne0$ である。
段 2（列との内積は $0$ 以上）。各 $j$ と $t>0$ について $p+ta_j\in K$ なので、$\lvert p+ta_j-b\rvert^2\ge\lvert p-b\rvert^2$、すなわち
$$
2t\,a_j\cdot y+t^2\lvert a_j\rvert^2\ge0
$$
である。$t$ で割って $t\to+0$ とすると $a_j\cdot y\ge0$ を得る。これがすべての $j$ で成り立つので $A^{\mathsf T}y\ge0$ である。
段 3（$p\cdot y=0$）。$-1< s$ なら $(1+s)p\in K$ なので、$g(s):=\lvert(1+s)p-b\rvert^2=\lvert y+sp\rvert^2=\lvert y\rvert^2+2s\,p\cdot y+s^2\lvert p\rvert^2$ は $s=0$ で最小になる。$s=0$ は区間 $(-1,\infty)$ の内点なので $g'(0)=2\,p\cdot y=0$ である。
段 4。$b=p-y$ だから $b\cdot y=p\cdot y-\lvert y\rvert^2=-\lvert y\rvert^2< 0$ である。段 2 と合わせて、$y$ は 2 を満たす。$\square$
証明で作った $y=p-b$ は、$b$ から錐 $K$ への最短点 $p$ に向かうベクトルである。超平面 $\{v\mid y\cdot v=0\}$ は $p$ を通り（段 3）、$K$ は $y\cdot v\ge0$ の側に、$b$ は $y\cdot v< 0$ の側にある。凸錐 の系「Farkas の補題（錐の形）」は、同じ主張を双対錐の双対の公式から導いている。
別証明（Fourier–Motzkin の消去法）を開く
cor-fk-inequality の形（$Ax\le b$ に解がないなら $y\ge0$、$A^{\mathsf T}y=0$、$b\cdot y< 0$ となる $y$ がある）を直接示す。多面体 の定理「Fourier–Motzkin の消去法」で $x_n,x_{n-1},\dots,x_1$ を順に消去する。各段の不等式系の解の全体は前の段の多面体の射影なので、前の段に解があることと次の段に解があることは同値である。また各段の不等式はもとの不等式に $0$ 以上の係数を掛けて足したものなので、ある $y\ge0$ によって $(A^{\mathsf T}y)\cdot x\le b\cdot y$ と書け、消去済みの変数の係数は $0$ である。全部消去すると、変数を含まない不等式 $0\le b\cdot y^{(k)}$（$y^{(k)}\ge0$、$A^{\mathsf T}y^{(k)}=0$）だけが残る。もとの系に解がなければ、このうちどれかが成り立たず、その $y^{(k)}$ が求める $y$ である。主定理は、1 を不等式系 $Ax\le b$、$-Ax\le-b$、$-x\le0$ に書き直してこの形を使い、最初の 2 つの不等式に掛ける乗数の差を $y$ とすれば得られる（乗数を $u,w\in\mathbb{R}^m$、$z\in\mathbb{R}^n$ とすると $A^{\mathsf T}(u-w)=z\ge0$、$b\cdot(u-w)< 0$）。この証明は位相を使わず、係数が有理数なら $y$ も有理数にとれることも示している。
ほかの形
主定理を行列と変数を取り替えて使うと、いろいろな形の択一定理が得られる。
$A\in\mathbb{R}^{m\times n}$、$b\in\mathbb{R}^m$ とする。次の 2 つのうち、ちょうど一方が成り立つ。
- $Ax\le b$ を満たす $x\in\mathbb{R}^n$ がある。
- $y\ge0$、$A^{\mathsf T}y=0$、$b\cdot y< 0$ を満たす $y\in\mathbb{R}^m$ がある。
$x$ を $x=x^+-x^-$（$x^\pm\ge0$）と分け、すき間 $s:=b-Ax\ge0$ を導入すると、1 は
$$
\begin{pmatrix}A&-A&I_m\end{pmatrix}\begin{pmatrix}x^+\\x^-\\s\end{pmatrix}=b,\qquad\begin{pmatrix}x^+\\x^-\\s\end{pmatrix}\ge0
$$
に解があることと同値である（逆向きは $x:=x^+-x^-$ とおけばよい）。この $m\times(2n+m)$ 行列に thm-fk-main を使うと、その 2 は $A^{\mathsf T}y\ge0$、$-A^{\mathsf T}y\ge0$、$y\ge0$、$b\cdot y< 0$、すなわち $y\ge0$、$A^{\mathsf T}y=0$、$b\cdot y< 0$ である。$\square$
2 の $y$ は、不等式 $a_i^{\mathsf T}x\le b_i$（$a_i^{\mathsf T}$ は $A$ の第 $i$ 行）にそれぞれ $y_i\ge0$ を掛けて足すと、左辺が $0$ で右辺が負の矛盾した不等式 $0\le b\cdot y$ ができる、という乗数の組である。
$A\in\mathbb{R}^{m\times n}$ とする。次の 2 つのうち、ちょうど一方が成り立つ。
- $Ax< 0$（すべての成分が負）を満たす $x\in\mathbb{R}^n$ がある。
- $y\ge0$、$y\ne0$、$A^{\mathsf T}y=0$ を満たす $y\in\mathbb{R}^m$ がある。
$Ax< 0$ に解 $x$ があれば、成分の最大値 $-\delta< 0$ について $x/\delta$ は $A(x/\delta)\le-\mathbf 1$ を満たす（$\mathbf 1$ は成分がすべて $1$ のベクトル）。逆に $Ax\le-\mathbf 1$ の解は $Ax< 0$ を満たす。よって 1 は「$Ax\le-\mathbf 1$ に解がある」と同値である。cor-fk-inequality を $b=-\mathbf 1$ で使うと、その 2 は $y\ge0$、$A^{\mathsf T}y=0$、$-\sum_iy_i< 0$ であり、$y\ge0$ のもとで $\sum_iy_i>0$ は $y\ne0$ と同値である。$\square$
$A$ の行ベクトルを $a_1^{\mathsf T},\dots,a_m^{\mathsf T}$ とすると、1 は $a_1,\dots,a_m$ がすべて同じ開半空間 $\{v\mid v\cdot x< 0\}$ に入ることであり、2 は $y$ を成分の和が $1$ になるように正の数で割れば $\sum_iy_ia_i=0$ となること、すなわち原点が $a_1,\dots,a_m$ の凸包（凸包）に属することである。$a_1,\dots,a_m$ が全部その開半空間に入ればその凸包も入るが、原点は入らないので、2 つが両立しないことはこの形でも見てとれる。
右辺が一般の $b$ のとき、$Ax< b$ に解がないことは、$y\ge0$、$y\ne0$、$A^{\mathsf T}y=0$、$b\cdot y\le0$ となる $y$ があることと同値である（BV04 Example 2.21、p. 50。そこでは開凸集合とアフィン集合の分離から導いている）。
狭義の不等式と非狭義の不等式が混ざった形として、$Ax\le0$、$c\cdot x< 0$ に解があることと、$A^{\mathsf T}y+c=0$、$y\ge0$ に解があることは、ちょうど一方が成り立つ（BV04 §5.8.3、p. 263）。これは thm-fk-main を行列 $A^{\mathsf T}$ と右辺 $-c$ に使い、2 の変数 $z$ を $x=-z$ に置き換えたものである。
例
$a_1=(1,0)^{\mathsf T}$、$a_2=(1,1)^{\mathsf T}$、$b=(0,1)^{\mathsf T}$ とする。$x_1a_1+x_2a_2=(x_1+x_2,x_2)^{\mathsf T}=b$ からは $x_2=1$、$x_1=-1$ で、$x\ge0$ の解はない。主定理の 2 の証拠は $y=(1,-1)^{\mathsf T}$ で、$a_1\cdot y=1\ge0$、$a_2\cdot y=0\ge0$、$b\cdot y=-1< 0$ である。
証明の作り方で求めると、錐 $K=\{(u,v)\mid0\le v\le u\}$ の中で $b$ に最も近い点は $p=\frac12(1,1)^{\mathsf T}$（$b$ から直線 $v=u$ への垂線の足）で、$y=p-b=\frac12(1,-1)^{\mathsf T}$ となり、上の $y$ の正の数倍である。
$x_1+x_2\le1$、$x_1\ge1$、$x_2\ge1$ は明らかに解をもたない。$Ax\le b$ の形では $A=\begin{pmatrix}1&1\\-1&0\\0&-1\end{pmatrix}$、$b=(1,-1,-1)^{\mathsf T}$ で、$y=(1,1,1)^{\mathsf T}$ が cor-fk-inequality の 2 を満たす：$y\ge0$、$A^{\mathsf T}y=(1-1,\ 1-1)^{\mathsf T}=0$、$b\cdot y=-1< 0$。3 つの不等式をそのまま足すと $0\le-1$ になる、というのがこの証拠の意味である。
応用
線形計画法の双対定理。 最大化問題 $\max\{c\cdot x\mid Ax\le b,\ x\ge0\}$ と最小化問題 $\min\{b\cdot y\mid A^{\mathsf T}y\ge c,\ y\ge0\}$ について、実行可能な $x,y$ はつねに $c\cdot x\le(A^{\mathsf T}y)\cdot x=y\cdot(Ax)\le b\cdot y$ を満たす（弱双対性）。両方が実行可能なら最適値が一致すること（強双対性）は、両方の制約に $b\cdot y\le c\cdot x$ を加えた $(x,y)$ の不等式系に解がないと仮定し、cor-fk-inequality の乗数から矛盾を導いて示される（線形計画法 の定理「線形計画法の双対定理」）。
$n$ 個の資産の現在の価格を $p\in\mathbb{R}^n$ とし、期末に起こりうる状態が $m$ 通りで、状態 $i$ での資産 $j$ の価値を $V_{ij}$ とする。保有量 $x\in\mathbb{R}^n$（負は空売り）の組合せで、$p\cdot x< 0$（受け取って始められる）かつ $Vx\ge0$（どの状態でも期末の価値が $0$ 以上）となるものを 裁定機会 という。
裁定機会がないことは、$y\ge0$ で $V^{\mathsf T}y=p$ となる $y\in\mathbb{R}^m$ があることと同値である（BV04 Example 5.10、p. 263）。実際、上の混ざった形を $A=-V$、$c=p$ に使うと、「$-Vx\le0$、$p\cdot x< 0$ に解がない」ことは「$-V^{\mathsf T}y+p=0$、$y\ge0$ に解がある」ことと同値である。$p_j=\sum_iy_iV_{ij}$ は、各状態に $0$ 以上の「状態価格」$y_i$ を割り当てて、価格を期末の価値の重み付きの和として表せることを意味する。
たとえば $m=n=2$、$V=\begin{pmatrix}1&2\\1&0\end{pmatrix}$（資産 1 はどちらの状態でも $1$、資産 2 は状態 1 で $2$、状態 2 で $0$）とする。$p=(1,1.2)^{\mathsf T}$ なら $V^{\mathsf T}y=p$ の解は $y=(0.6,0.4)^{\mathsf T}\ge0$ で、裁定機会はない。$p=(1,2.2)^{\mathsf T}$ なら解は $y=(1.1,-0.1)^{\mathsf T}$ で $y\ge0$ とならず、実際 $x=(2,-1)^{\mathsf T}$ では $Vx=(0,2)^{\mathsf T}\ge0$、$p\cdot x=-0.2< 0$ である。
仮定を外すと成り立たなくなること
各行で外す条件は 1 つだけで、ほかは thm-fk-main のとおりである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 生成元が有限個 | $\mathbb{R}^2$ で $K=\operatorname{cone}\{(1,t)^{\mathsf T}\mid t\in\mathbb{R}\}$、$b=(0,1)^{\mathsf T}$ | $b\notin K$ だが、すべての生成元との内積が $0$ 以上で $b\cdot y< 0$ となる $y$ はない（どちらも成り立たない） |
| 2 の $b\cdot y< 0$ が狭義の不等号 | 任意の $A,b$ で 2 を $b\cdot y\le0$ に替える | $y=0$ が替えた 2 をいつも満たし、1 が成り立つときも両方成り立つ |
| 1 の $x$ が実数 | $A=(2)$、$b=(1)$ で、1 を整数の $x\ge0$ に限る | $2x=1$ の整数解はなく、$2y\ge0$ かつ $y< 0$ となる $y$ もない（どちらも成り立たない） |
| 1 の $x\ge0$ | $A=(1)$、$b=(-1)$ で、1 を $Ax=b$ だけにする | $x=-1$ が替えた 1 を満たし、$y=1$ が 2 を満たす（両方成り立つ） |
各行の確かめを開く
1 行目：$x_1>0$ なら $(x_1,x_2)=x_1(1,x_2/x_1)$ なので、$K=\{(x_1,x_2)\mid x_1>0\}\cup\{0\}$ である。これは閉集合でなく、$b=(0,1)^{\mathsf T}$ は $K$ に属さないが $K$ の閉包に属する。すべての $t$ で $(1,t)\cdot y=y_1+ty_2\ge0$ なら $y_2=0$、$y_1\ge0$ で、$b\cdot y=y_2=0$ となり負にならない。外れた条件は生成元の個数だけで、生成元が有限個なら lem-fk-closed により $K$ は閉じている。
2 行目：不等号を緩めると、$y=0$ がつねに証拠になってしまい、「ちょうど一方」が崩れる。
3 行目：$x$ を実数で考えれば $x=\frac12\ge0$ が 1 を満たし、定理どおり 2 は成り立たない。整数に限ると 1 も 2 も成り立たない。整数解の存在には別の択一定理（Hermite 標準形などを使うもの）が要る。
4 行目：$x\ge0$ を外すと 1 は $b$ が $A$ の列空間に属することになり、両方が成り立ちうる。符号の条件のない連立 1 次方程式については「$Ax=b$ に解がある」と「$A^{\mathsf T}y=0$、$b\cdot y\ne0$ となる $y$ がある」のちょうど一方が成り立つ（列空間が $\ker A^{\mathsf T}$ の直交補空間であることによる）。
補足
閉じていることの役割。 証明の要は、有限生成の錐が閉じていて最短点がとれることだった。一般の閉凸錐 $K$ では、$b\notin K$ なら $b$ を分離する $y$ がある（凸錐 の定理「双対錐の双対」）。しかし $K=\{Ax\mid x\in C\}$ のように閉凸錐 $C$ の 1 次写像の像として与えられた錐は閉じているとは限らず、そのときは表の 1 行目のように、$b$ が $K$ の閉包にだけ属して、1 も 2 も成り立たないことがある。半正定値計画などの錐計画で双対定理に追加の条件（内点の存在など）が要るのはこのためである。
名前。 J. Farkas（Gyula Farkas）の名による。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
