Farkas の補題と双対定理の初等的証明松井知己並木誠

この原稿は, Farkas の補題及びそれを用いた強双対定理の\underline{初等的な証明}の試みです. この原稿を書くに至ったきっかけは, 2 人の筆者の間で交わされた次のような疑問でした; 「KKT 条件も単体法も一次独立もコーシー列も知らない生徒がいる授業で, 双対定理を証明できるか?」 . さてその結果が以下の証明ですが「いかがでしょう?」 .

多くの線形計画法の本では, 強双対定理の証明は, 単体法の正当性から導かれている事が多い. しかしながら, 単体法の有限性の証明や, 2 段階単体法の詳細は決して簡単なものではない. また非線形計画の KKT 条件の特殊形として示そうとしても, 適用できる簡単な制約想定が無いため, その証明は安易ではない. そもそも最適解があるかという問題についても, 許容領域のコンパクト性が保証されず, 決して自明ではない.

実は強双対定理の証明は, 許容解の存在性, つまり線形不等式系の解の存在性の特長付けと本質的な関わりがある. 線形不等式系の解の存在性については, 以下の Farkas の補題と呼ばれるものが成り立つ. \underline{Farkas の補題:} 任意の m × n 実行列 A と, 任意の m 次元実ベクトル b に対し, 以下 X と Y のうち丁度 1 つが要素をもつ.

\begin{matrix}X = \{x ∈ R^{n} | Ax = b, x ≥ 0\}, \\ Y = \{y ∈ R^{m} | y^{⊤}A ≥ 0^{⊤}, y^{⊤}b < 0\}. \end{matrix}

例えば

\begin{matrix}X = \{x = (x_{1}, x_{2}, x_{3}) | \begin{matrix}−x_{1} + x_{2} + x_{3} = −5, \\ 2x_{1} + x_{2} − x_{3} = 7, x ≥ 0 \end{matrix} \} \\ Y = \{y = (y_{1}, y_{2}) | \begin{matrix}−y_{1} + 2y_{2} ≥ 0, & y_{1} + y_{2} ≥ 0, \\ y_{1} − y_{2} ≥ 0, & −5y_{1} + 7y_{2} < 0 \end{matrix} \} . \end{matrix}

とすると, Y が要素 y = (2, 1) を持つ事と Farkas の補題より, X が空である事が容易に判定される. 事実, y = (2, 1) の重みで X の定義中の等式を加えると,

まついともみ東京大学大学院工学系研究科計数工学専攻〒 113-8656 東京都文京区本郷 7-3-1

http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/

なみきまこと東邦大学理学部情報科学科〒 274-8510 千葉県船橋市三山 2-2-1

E-mail: namiki@is.sci.toho-u.ac.jp

2∗(−x_{1} +x_{2} +x_{3})= 2 ∗ (−5)
1∗ (2x_{1} +x_{2} −x_{3})= 1 ∗ 7
(0x_{1} +3x_{2}+x_{3})= −3

となり, x = (x_{1}, x_{2}, x_{3}) ≥ 0 とは両立しない式となっていることから, X が空であることが分かる.

以下では, Farkas の補題の初等的な証明を試みる. この証明は以下のような特徴も持っている. (1) コーシー列等の知識が不必要, (2) 単体法の知識が不必要, (3) 非常に短い, (4) 証明の手続きに従うと, Farkas の補題の性質を達成するベクトルを有限ステップで生成できる. では, 始めよう.

集合 S と集合 {j} に対し, S ∪ {j} を S + j と書く. また j ∈ S の時, S \ {j} を S − j と書く. 集合 S, I, J, K が I ∩ J = J ∩ K = K ∩ I = ∅ と S = I ∪ J ∪ K を満たすとき, I, J, K は S の分割であると言う. 本稿では, 冒頭の主張を証明する代わりに, より一般的な形式の以下の主張を証明する. \underline{Farkas の補題 (一般形):}任意の m × n 行列 A と, 任意の m 次元ベクトル b に対し, 以下が成り立つ. 行列 A の列の添え字集合を N = {1, 2, …, n} とし, A_{i} を A の第 i 列ベクトルとする. N の分割 I, J, K に対し, X(I, J, K), Y (I, J, K) を以下のように定義する.

\begin{aligned}X(I, J, K) & = & \{x ∈ R^{n} | \begin{matrix}Ax = b, \\ x_{i} ≥ 0 & (i ∈ I), \\ x_{i} は自由 & (i ∈ J), \\ x_{i} = 0 & (i ∈ K) \end{matrix} \} , \\ Y (I, J, K) & = & \{y ∈ R^{m} | \begin{matrix}y^{⊤}A_{i} ≥ 0 & (i ∈ I), \\ y^{⊤}A_{i} = 0 & (i ∈ J), \\ y^{⊤}A_{i} は自由 & (i ∈ K), \\ y^{⊤}b < 0 \end{matrix} \} . \end{aligned}

N の任意の分割 I, J, K に対し, X(I, J, K) と Y (I, J, K) のうち丁度 1 つが要素をもつ. 上記において I = N, J = K = ∅ とすると, 冒頭の Farkas の補題となる. 集合 X(I, J, K), Y (I, J, K) の定義中の制約は, 以下のようになっている.

表 1. X(I, J, K) と Y (I, J, K) における制約.

\begin{matrix}添え字 i & I & J & K \\ X(I, J) における x_{i} の符号 & 非負 & 自由 & ゼロ \\ Y (I, J) における y^{⊤}A_{i} の符号 & 非負 & ゼロ & 自由 \end{matrix}

証明: \overline{x} ∈ X(I, J, K) かつ\overline{y} ∈ Y (I, J, K) とすると, ; \begin{matrix}0 & > \overline{y}^{⊤}b = \overline{y}^{⊤}A\overline{x} \\ = ∑_{i∈I} \overline{y}^{⊤}A_{i}\overline{x}_{i} + ∑_{i∈J} \overline{y}^{⊤}A_{i}\overline{x}_{i} + ∑_{i∈K} \overline{y}^{⊤}A_{i}\overline{x}_{i} \\ = ∑_{i∈I} \overline{y}^{⊤}A_{i}\overline{x}_{i} + 0 + 0 ≥ 0 \end{matrix} ; となり矛盾. ゆえに X(I, J, K) と Y (I, J, K) が同時に ; 解を持つことは無い. 以下では X(I, J, K) と Y (I, J, K) ; の一方が要素を持つ事を, I の要素数に関する帰納法を ; 用いて示す. ; (1) |I| = 0 の場合. 補題１において証明する. ; (2) 正整数 k に関して, |I| < k ならば補題の主張が成り ; 立つと仮定して, |I| = k の場合を示す. ; I 中の要素を 1 つ選び l とする. 以下では 6 つの集合 ; X(I, J, K), X(I − l, J + l, K), X(I − l, J, K + l), ; Y (I, J, K), Y (I − l, J + l, K), Y (I − l, J, K + l), ; について議論する. これらの集合の定義中の制約を表 1 ; に倣ってまとめると, 次のようになる. ; 表 2. 制約の一覧表. ; \begin{aligned}& 添え字 & & I − l & l & J & K \\ X( & I, & J, & K) & 非負 & 非負 & 自由 & ゼロ \\ X( & I − l, & J + l, & K) & 非負 & 自由 & 自由 & ゼロ \\ X( & I − l, & J, & K + l) & 非負 & ゼロ & 自由 & ゼロ \\ Y ( & I, & J, & K) & 非負 & 非負 & ゼロ & 自由 \\ Y ( & I − l, & J + l, & K) & 非負 & ゼロ & ゼロ & 自由 \\ Y ( & I − l, & J, & K + l) & 非負 & 自由 & ゼロ & 自由 \end{aligned} ; X(I − l, J, K + l) は X(I, J, K) の定義の x_{l} ≥ 0 を ; x_{l} = 0 に換えた物なので X(I, J, K) ⊇ X(I − l, J, K + ; l) が成り立つ. よって X(I − l, J, K + l) ≠ ∅ ならば ; X(I, J, K) ≠ ∅ である. ゆえに X(I − l, J, K + l) = ∅ の ; 場合のみ議論する. 帰納法の仮定より, X(I −l, J, K +l) ; と Y (I − l, J, K + l) は丁度一方が非空となる事から, ; Y (I − l, J, K + l) が非空の場合のみ議論する. ; 同様に, Y (I−l, J +l, K) の定義は Y (I, J, K) の定義の ; y^{⊤}A_{l} ≥ 0 を y^{⊤}A_{l} = 0 に換えた物なので, Y (I, J, K) ⊇ ; Y (I −l, J +l, K) が成り立ち, Y (I −l, J +l, K) ≠ ∅ なら ; ば Y (I, J, K) ≠ ∅ である. ゆえに Y (I − l, J + l, K) = ∅ ; の場合のみ議論する. 帰納法の仮定より, 2 つの集合 ; X(I − l, J + l, K) と Y (I − l, J + l, K) は丁度一方が非 ; 空なので, X(I − l, J + l, K) が非空の場合のみ議論する. ; 上記より, 以下の要素が存在する場合のみ議論すれば ; 良い; ∃\overline{x} ∈ X(I − l, J + l, K), ∃\overline{y} ∈ Y (I − l, J, K + l). ; 解\overline{x}, \overline{y} の定義より, ; \begin{aligned}0 & > & \overline{y}^{⊤}b = \overline{y}^{⊤}(A\overline{x}) \\ & = & ∑_{i∈I−l} \overline{y}^{⊤}A_{i}\overline{x}_{i} + \overline{y}^{⊤}A_{l}\overline{x}_{l} + ∑_{i∈J∪K} \overline{y}^{⊤}A_{i}\overline{x}_{i} \\ & = & ∑_{i∈I−l} \overline{y}^{⊤}A_{i}\overline{x}_{i} + \overline{y}^{⊤}A_{l}\overline{x}_{l} ≥ \overline{y}^{⊤}A_{l}\overline{x}_{l} \end{aligned} ; となり, \overline{y}^{⊤}A_{l} > 0 または\overline{x}_{l} > 0 が成り立つ. \overline{y}^{⊤}A_{l} > 0 ならば, \overline{y} は Y (I, J, K) の要素である.

\overline{x}_{l} > 0 ならば, \overline{x} は X(I, J, K) の要素である.

\underline{補題 1:} M を m × n 行列とする. 以下の２つの集合の ; うち丁度 1 つが要素を持つ. ; \begin{aligned}X(M, b) & = & \{x ∈ R^{n}|Mx = b\}, \\ Y (M, b) & = & \{y ∈ R^{m}|y^{⊤}M = 0^{⊤}, y^{⊤}b < 0\}. \end{aligned}

{注: |I| = 0 の場合の Farkas の補題は, \{A_{i} | i ∈ J\} 中の縦 \atop ベクトルを並べた行列を M とすると, 上記の補題となる.}

証明: ベクトル b を M の列ベクトルの張る線形空間に直交射影して得られるベクトルを b′ とし, \overline{y} = b′ − b と定義する. 直交射影の定義より [ ∃\overline{x}, b′ = M\overline{x} ] と [ \overline{y}^{⊤}M = 0^{⊤} ] が成り立つ. \overline{y} の定義より, \overline{y}^{⊤}b = \overline{y}^{⊤}(b′ − \overline{y}) = \overline{y}^{⊤}M\overline{x} − ||\overline{y}||^{2} = −||\overline{y}||^{2} ≤ 0 である.

(i) \overline{y}^{⊤}b < 0 ならば, \overline{y}^{⊤}M = 0^{⊤} より\overline{y} ∈ Y (M, b) ≠ ∅ となる. (ii) \overline{y}^{⊤}b = 0 ならば, 0 = \overline{y}^{⊤}b = −||\overline{y}||^{2} より\overline{y} = 0 が成り立ち, M\overline{x} = b′ = b′ − 0 = b′ − \overline{y} = b となり, \overline{x} ∈ X(M, b) ≠ ∅ である.

上記の証明の特徴の 1 つは, 構成的な事である. すなわち上記の証明は, Farkas の補題の主張を示すベクトルを実際に求める有限時間算法になっている. その際補題 1 の直交射影には, グラム-シュミットの直交化法を用いる事ができる. しかし, 本稿の初期の目的に「線形代数の知識を要求しない」を課したので, 直交射影等の知識を要求しない補題 1 の証明を付録に付けた.

最後に, Farkas の補題を用いて双対定理を証明しよう. m, n を任意の正整数とし, A, b, c を m × n 実行列, m 次元実ベクトル, n 次元実ベクトルとする. 次の線形計画問題 P とその双対問題 D について議論する.

P: max{c^{⊤}x | Ax = b, x ≥ 0},
D: min{y^{⊤}b | y^{⊤}A ≥ c^{⊤}}.

{\underline{弱双対定理:}2 つの線形計画問題 P と D の任意の実行 \atop 可能解の対\overline{x}, \overline{y} は, c^{⊤}\overline{x} ≤ \overline{y}^{⊤}b を満たす.}

証明：問題 P, D の定義と\overline{x}, \overline{y} が各々の実行可能解である事から\overline{y}^{⊤}b = \overline{y}^{⊤}A\overline{x} ≥ c^{⊤}\overline{x} となる.

\underline{強双対定理:}２つの線形計画問題 P と D のどちらも 実行可能解を持つならば, P と D のいずれも最適解を 持ち, 最適値は一致する.

証明：不等式系

X = \{x ∈ R^{n}, y ∈ R^{m} | \begin{matrix}Ax = b, x ≥ 0, \\ A^{⊤}y ≥ c, c^{⊤}x ≥ b^{⊤}y \end{matrix} \}

について議論する. X が空でなく, 要素 x, y を持つならば, 弱双対定理より明らかに x, y はそれぞれ P と D の最適解であり, P と D の最適値も一致する. 以下では, P, D がそれぞれ実行可能解を持つにもかかわらず, X が空であると仮定をして矛盾を導く. スラック変数 s を導入し, X の不等式系を見やすく書くと,

\begin{matrix}A  O ; O  −A^{⊤} ; I ; −c^{⊤}  b^{⊤} [ \begin{matrix}x \\ s \\ y \end{matrix} ] = [ \begin{matrix}b \\ −c \\ 0 \end{matrix} ] , \\ x ≥ 0, s ≥ 0, \end{matrix}

となる. ただし, I は単位行列を表し, O は適当なサイズの零行列を表す. Farkas の補題 (一般形) より, X が空ならば次の線形不等式系の解集合 Y = {(w^{⊤}, z^{⊤}, q)^{⊤} ∈ R^{m+n+1} |

w^{⊤}A − qc^{⊤} ≥ 0^{⊤}, z^{⊤} ≥ 0^{⊤}, q ≥ 0, − z^{⊤}A^{⊤} + qb^{⊤} = 0^{⊤}, w^{⊤}b − z^{⊤}c < 0}

が非空となる. 以下では Y が要素 (\overline{w}^{⊤}, \overline{z}^{⊤}, \overline{q})^{⊤} を持つと仮定して矛盾を導く. (証明の, これ以降の部分は, オペレーションズ・リサーチ, Vol. 45 (2000) では間違っています. 申し訳ありません. 下記が改訂版です.)

\overline{x}, \overline{y} を P, D の実行可能解とする. \overline{q} > 0 ならば,

\begin{aligned}0 & > \overline{q}(\overline{w}^{⊤}b − c^{⊤}\overline{z}) = \overline{w}^{⊤}(\overline{q}b) − (\overline{q}c^{⊤})\overline{z} \\ & = \overline{w}^{⊤}A\overline{z} − (\overline{q}c^{⊤})\overline{z} ≥ \overline{w}^{⊤}A\overline{z} − \overline{w}^{⊤}A\overline{z} = 0, \end{aligned}

より矛盾. \overline{q} = 0 ならば,

\begin{aligned}0 & > \overline{w}^{⊤}b − \overline{z}^{⊤}c ≥ \overline{w}^{⊤}A\overline{x} − \overline{z}^{⊤}A^{⊤}\overline{y} \\ & ≥ \overline{q}c^{⊤}\overline{x} − \overline{q}b^{⊤}\overline{y} = 0 − 0 = 0 \end{aligned}

となり矛盾.

Farkas の補題を強双対定理から導くことは容易であり (例えば [2] 参照), 逆に Farkas の補題から強双対定理も容易に導かれる (上記の証明や [1] 参照) 事から, この 2 つは殆ど等価な性質に見える. ではどちらがより始原的なのか? Farkas の補題は許容解の存在性について述べており, 強双対定理は最適解について述べている. 最適解があるのならば許容解は当然存在するのだから, Farkas の補題の方がより簡単で本質的な性質と考えるのは自然だろう. 実は, Farkas の補題と強双対定理を, 数値の符号のみに注目した組合せ的な構造に拡張した場合, Farkas の補題が成り立っていながら, 強双対定理が成り立たない状況が存在する事も知られている [3]. \underline{付録補題 1 の別証明:}

X(M, b) と Y (M, b) が同時に解を持つことは無いのは, Farkas の補題の証明中で示した. 以下では, X(M, b) と Y (M, b) の少なくとも一方が要素を持つ事を, 行列 M の列数と行数の和に関する帰納法を用いて示す.

(1) M の行数が 1 のとき, 明らかに成り立つ.

(2) M の行数が 2 以上のとき, M を m × n 行列とし, m + n = k + 1 とする. 行数と列数の和が k 以下の任意の行列に関して, 補題の主張が成り立つと仮定する. 行列 M の一番上の行を α^{⊤}(α ∈ R^{n}) とし, ベクトル b の第一要素の値を β (β ∈ R) とする. さらに M′, b′

を M = [ \begin{matrix}α & ⊤ \\ M′ \end{matrix} ] , b = (\begin{matrix}β \\ b & ′ \end{matrix}) と定義する. 以下では,

行列 M′ および M^{′⊤} の行数と列数の和は k であり, 帰納法の仮定が成り立つ事を用いる. 帰納法の仮定より, 次の２つの集合

\begin{aligned}X(M′, b′) & = & \{x ∈ R^{n} | M′x = b′\}, \\ Y (M′, b′) & = & \{y′ ∈ R^{m−1} | y^{′⊤}M′ = 0^{⊤}, y^{′⊤}b′ < 0\}, \end{aligned}

は, いずれか一方のみ要素を持つ. また,

\begin{aligned}X(M^{′⊤}, α) & = & \{z ∈ R^{m−1} | M^{′⊤}z = α\}, \\ Y (M^{′⊤}, α) & = & \{w ∈ R^{n} | w^{⊤}M^{′⊤} = 0^{⊤}, w^{⊤}α < 0\}, \end{aligned}

とすると, 帰納法の仮定より上記 2 つの集合はいずれか一方のみ要素を持つ. ゆえに, 下記 (i)(ii)(iii) に場合分けする事ができる.

(i) ∃\overline{y} ∈ Y (M′, b′) の場合. (0 ; \overline{y}) ∈ Y (M, b) となる.

(ii) ∃\overline{x} ∈ X(M′, b′) かつ ∃w ∈ Y (M^{′⊤}, α) の場合. ベ

クトル x^{∗} を, x^{∗} = \overline{x} − (\frac{α^{⊤}\overline{x} − β}{α^{⊤}w} ) w と定義すると,

\begin{aligned}α^{⊤}x^{∗} & = & α^{⊤}\overline{x} − (\frac{α^{⊤}\overline{x} − β}{α^{⊤}w} ) α^{⊤}w = β, \\ M′x^{∗} & = & M′\overline{x} − (\frac{α^{⊤}\overline{x} − β}{α^{⊤}w} ) M′w = M′\overline{x} = b′, \end{aligned}

となり, Mx^{∗} = b が成り立ち x^{∗} ∈ X(M, b) である. (iii) ∃\overline{x} ∈ X(M′, b′) かつ ∃z ∈ X(M^{′⊤}, α) の場合. α^{⊤}\overline{x} = β ならば, \overline{x} ∈ X(M, b) が成り立つ. z^{⊤}b′ ≠ β

ならば, y^{∗} = (\begin{matrix}−1 \\ z \end{matrix}) とすると,

\begin{aligned}y^{∗}^{⊤}M & = & −α^{⊤} + z^{⊤}M′ = 0^{⊤}, \\ y^{∗}^{⊤}b & = & −β + z^{⊤}b′ ≠ 0, \end{aligned}

を満たし, y^{∗} ∈ Y (M, b) または −y^{∗} ∈ Y (M, b) のどちらかが成り立つ. α^{⊤}\overline{x} ≠ β かつ z^{⊤}b′ = β ならば, β ≠ α^{⊤}\overline{x} = z^{⊤}M′\overline{x} = z^{⊤}b′ = β となり矛盾.

参考文献

[1] 伊理正夫, 「線形計画法」 , 共立出版, 1986.

[2] 今野浩, 「線形計画法」 , 日科技連, 1987.

[3] 田村明久, 『線形計画法と有向マトロイド計画法』 , 「離散構造とアルゴリズム IV」第１章, 室田一雄編, 近代科学社, 1995.