ファルカスの補題

数学において、ファルカスの補題は、有限の線型不等式系の可解定理である。この定理はもともとハンガリーの数学者ギュラ・ファルカスによって証明された。^[1] ファルカスの補題は、線型計画法の双対性を支える重要な結果であり、数学的最適化（あるいは数理計画法）の発展において中心的な役割を果たしてきた。この定理は、非線形計画法におけるカルシュ・キューン・タッカー定理の証明などに使用されている。^[2] 注目すべきことに、量子論の基礎の分野では、この補題は、特定の測定セットからのデータに基づいて局所的な隠れた変数理論が存在するための必要十分条件という形で、ベル不等式の完全なセットの基礎にもなっている。^[3]

ファーカスの補題の一般化は、凸不等式、つまり無限線形不等式の可解定理に関するものである^[4]。ファーカスの補題は、「代替定理」と呼ばれるステートメントのクラスに属し、2つのシステムのうち正確に1つに解が存在することを述べる定理である^[5]。

文献には、この補題の若干異なる（しかし同等の）定式化が数多くある。ここで示すのは、Gale、Kuhn、Tucker（1951）によるものである。^[6]

ここで、表記はベクトルのすべての要素が非負であることを意味します。 ${\displaystyle \mathbf {x} \geq 0}$${\displaystyle \mathbf {x} }$

m、n = 2とします。この補題は、次の 2 つのステートメントのうち 1 つだけが真でなければならないことを示しています ( b ₁とb ₂に依存します)。 ${\displaystyle \mathbf {A} ={\begin{bmatrix}6&4\\3&0\end{bmatrix}},}$${\displaystyle \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}}.}$

1. x ₁ ≥ 0、x ₂ ≥ 0が存在し、 6 x ₁ + 4 x ₂ = b ₁かつ3 x ₁ = b ₂である、または
2. 6 y ₁ + 3 y ₂ ≥ 0、4 y ₁ ≥ 0、b ₁ y ₁ + b ₂ y ₂ < 0となるy ₁、y _{2 が}存在する。

この特殊なケースにおける補題の証明は次の通りです。

• b ₂ ≥ 0かつb ₁ − 2 b ₂ ≥ 0の場合、線形方程式の解は であるためオプション 1 は真であり、右辺が正であれば左辺も正でなければならない ためオプション 2 は偽です。${\displaystyle x_{1}={\tfrac {b_{2}}{3}}}$${\displaystyle x_{2}={\tfrac {b_{1}-2b_{2}}{4}}.}$$${\displaystyle b_{1}y_{1}+b_{2}y_{2}\geq b_{2}(2y_{1}+y_{2})=b_{2}{\frac {6y_{1} +3y_{2}}{3}},}$$
• それ以外の場合、線形方程式の唯一の解は弱正ではないため、オプション 1 は偽です。ただし、この場合はオプション 2 が真です。
  • b ₂ < 0の場合、例えばy ₁ = 0およびy ₂ = 1とすることができます。
  • b ₁ − 2 b ₂ < 0の場合、ある数B > 0に対して、b ₁ = 2 b ₂ − Bとなるため、たとえば、y ₁ = 1、y ₂ = −2とすることができます。$${\displaystyle b_{1}y_{1}+b_{2}y_{2}=2b_{2}y_{1}+b_{2}y_{2}-By_{1}=b_{2}{\frac {6y_{1}+3y_{2}}{3}}-By_{1}.}$$

Aの列によって張られる閉じた 凸錐を 考える。つまり、 ${\displaystyle C(\mathbf {A} )}$

${\displaystyle C(\mathbf {A} )=\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geq 0\}。}$

は、ファルカスの補題の最初の主張が成り立つベクトルbの集合であることに注目してください。一方、2番目の主張のベクトルyは、 bとを分離する超平面に直交しています。補題は、 bがに属するのは、それを分離する超平面が存在しないときのみであるという観察から導かれます。${\displaystyle C(\mathbf {A} )}$${\displaystyle C(\mathbf {A} ).}$${\displaystyle C(\mathbf {A} )}$${\displaystyle C(\mathbf {A} ).}$

より正確には、Aの列を とします。これらのベクトルに関して、Farkas の補題は、次の 2 つのステートメントのうち 1 つが真であることを述べています。 ${\displaystyle \mathbf {a} _{1},\dots ,\mathbf {a} _{n}\in \mathbb {R} ^{m}}$

1. 非負の係数が存在するので、${\displaystyle x_{1},\dots ,x_{n}\in \mathbb {R} }$${\displaystyle \mathbf {b} =x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}.}$
2. に対してとなるベクトルが存在し、${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$${\displaystyle \mathbf {a} _{i}^{\top }\mathbf {y} \geq 0}$${\displaystyle i=1,\dots ,n,}$${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}$

非負の係数を持つ和は、Aの列によって張られる円錐を形成する。したがって、最初の文は、bが${\displaystyle x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}}$${\displaystyle x_{1},\dots ,x_{n}}$${\displaystyle C(\mathbf {A} ).}$

2 番目のステートメントは、ベクトルyが存在し、yとベクトルa _iとの角度は最大で 90° であるのに対し、 yとベクトルbとの角度は90° を超えることを示しています。このベクトルに垂直な超平面は、片側にベクトルa _{iがあり、反対側にベクトル}b があります。したがって、この超平面は、 が張る円錐をベクトルbから分離します。 ${\displaystyle \mathbf {a} _{1},\dots ,\mathbf {a} _{n}}$

たとえば、n、m = 2、a ₁ = (1, 0) ^T、a ₂ = (1, 1) ^{Tとします。} a ₁とa ₂で張られる凸錐は、xy平面の第 1 象限のくさび形のスライスとして見ることができます。 ここで、b = (0, 1)とします。 確かに、b は凸錐a ₁ x ₁ + a ₂ x ₂内にはありません。 したがって、分離超平面が存在する必要があります。y = (1, −1) ^{Tとします。} a ₁ · y = 1、a ₂ · y = 0、b · y = −1であることがわかります。 したがって、法線yを持つ超平面は確かに凸錐a ₁ x ₁ + a ₂ x _{2 を}bから分離します。

特に示唆に富み、覚えやすいバージョンは次のようになります。線型不等式の集合に解がない場合は、非負の係数を持つ線型結合によって矛盾が生じる可能性があります。式では、が解けない場合は解が存在します。^{[7] は}不等式の左辺の組み合わせ、右辺の組み合わせであることに注意してください。正の組み合わせでは左側にゼロベクトル、右側に -1 が生成されるため、矛盾は明らかです。 ${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$${\displaystyle \mathbf {y} ^{\top }\mathbf {A} =0,}$ ${\displaystyle \mathbf {y} ^{\top }\mathbf {b} =-1,}$ ${\displaystyle \mathbf {y} \geq 0}$${\displaystyle \mathbf {y} ^{\top }\mathbf {A} }$${\displaystyle \mathbf {y} ^{\top }\mathbf {b} }$

したがって、ファーカスの補題は論理的完全性の定理として見ることができる。は「公理」の集合であり、線形結合は「導出規則」であり、補題は、公理の集合が矛盾している場合、導出規則を使用して反駁できると述べている。^{[8] : 92–94}${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$

ファーカスの補題は、「線形方程式系が与えられた場合、非負の解を持つか？」という決定問題がNPとco-NPの共通部分にあることを意味している。これは、補題によれば、「はい」の答えと「いいえ」の答えの両方に、多項式時間で検証できる証明があるためである。共通部分にある問題は、よく特徴付けられた問題とも呼ばれる。 がPに等しいかどうかは、長年の未解決問題である。特に、線形方程式系が非負の解を持つかどうかという問題は、楕円体法を使用して証明されるまで、P に含まれることは知られていなかった。^{[9] : 25}${\displaystyle NP\cap coNP}$${\displaystyle NP\cap coNP}$

ファルカスの補題には、異なる符号制約を持ついくつかの変種がある（最初のものは元のバージョンである）: ^{[8] : 92}

• 解決策があるか、解決策がある${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {x} \geq 0,}$${\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0}$${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}$
• 解決策があるか 、解決策がある${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$${\displaystyle \mathbf {x} \geq 0,}$${\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0}$${\displaystyle \mathbf {y} \geq 0}$${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0}$
• には解があるか、で解が見つかります。${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$${\displaystyle \mathbf {x} \in \mathbb {R} ^{n},}$${\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0}$${\displaystyle \mathbf {y} \geq 0}$${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0}$
• 解決策があるか、解決策がある${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {x} \in \mathbb {R} ^{n},}$${\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0}$${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$${\displaystyle \mathbf {b} ^{\top }\mathbf {y} \neq 0.}$

後者の変形は完全性のために言及されている。これは等式のみを含むため、実際には「Farkas の補題」ではない。その証明は線形代数の演習である。

整数計画法にもFarkasのような補題が存在する。^{[9] : 12--14}連立方程式の場合、補題は単純である。

• Aとb が有理係数を持つと仮定します。この場合、どちらかが積分解を持つか、またはが積分で が積分でないようなものが存在します。${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n},}$${\displaystyle \mathbf {y} \in \mathbb {R} ^{n}}$${\displaystyle \mathbf {A} ^{\top }\mathbf {y} }$${\displaystyle \mathbf {b} ^{\top }\mathbf {y} }$

不等式系の場合、補題ははるかに複雑です。これは、次の 2 つの推論規則に基づいています。

1. 不等式と係数が与えられた場合、不等式を推論します。${\displaystyle a_{1}^{T}x\leq b_{1},\ldots ,a_{m}^{T}x\leq b_{m}}$${\displaystyle w_{1},\ldots ,w_{m}}$${\displaystyle \left(\sum _{i=1}^{m}w_{i}a_{i}^{T}\right)x\leq \sum _{i=1}^{m}w_{i}b_{i}}$
2. 不等式 が与えられた場合、不等式 を推論します 。${\displaystyle a_{1}x_{1}+\cdots +a_{m}x_{m}\leq b}$${\displaystyle \lfloor a_{1}\rfloor x_{1}+\cdots +\lfloor a_{m}\rfloor x_{m}\leq \lfloor b\rfloor }$

補題はこう述べています:

• Aとb が有理係数を持つと仮定します。この場合、どちらかが整数解を持つか、または推論規則 1、2 を有限回適用して不等式を推論することが可能です。${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n},x\geq 0}$${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$${\displaystyle 0^{T}x\leq -1}$

バリエーションは以下の表にまとめられています。

一般化された Farkas の補題は、幾何学的に次のように解釈できます。ベクトルが与えられた閉じた凸錐内にあるか、ベクトルを錐から分離する超平面が存在するかのいずれかです。他の可能性はありません。閉条件は必須です。超平面分離定理の分離定理 I を参照してください。元の Farkas の補題では、は非負の直交座標であるため、閉条件は自動的に成立します。実際、多面体凸錐の場合、つまり、閉条件が自動的に成立する ような が存在します。凸最適化では、さまざまな種類の制約条件、たとえばSlater の条件が、基礎となる凸錐の閉条件に関係します。${\displaystyle \mathbf {S} }$${\displaystyle \mathbb {R} _{+}^{n},}$${\displaystyle \mathbf {B} \in \mathbb {R} ^{n\times k}}$${\displaystyle \mathbf {S} =\{\mathbf {B} \mathbf {x} \mid \mathbf {x} \in \mathbb {R} _{+}^{k}\},}$${\displaystyle C(\mathbf {A} ).}$

一般化されたファルカスの補題でとを設定すると、線形等式の有限系の可解性に関する次の系が得られます。 ${\displaystyle \mathbf {S} =\mathbb {R} ^{n}}$${\displaystyle \mathbf {S} ^{*}=\{0\}}$

ファルカスの補題は、簡単な修正によって、さらに多くの代替定理に変化させることができます。^[5]例えば、ゴルダンの定理: のいずれかに解xがあるか、y ≥ 0の非ゼロ解yがあります。 ${\displaystyle \mathbf {Ax} <0}$${\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0}$

ファーカスの補題の一般的な応用としては、線型計画法に関連する強い双対性定理やカルーシュ・キューン・タッカー条件の証明などがある。ファーカスの補題の拡張は、半正定値計画法の強い双対性条件の解析や、半正定値計画法の双対の構築に使用できる。フレドホルム代替法を用いてカルーシュ・キューン・タッカー条件の存在を証明すれば十分であるが、条件が必要であるためには、フォン・ノイマンのミニマックス定理を適用して、コーシーによって導出された方程式が破られないことを示す必要がある。

• 二重線形計画
• フーリエ-モツキン消去法は、ファルカスの補題を証明するために使用できます。

• Goldman, AJ; Tucker, AW (1956)。「多面体凸円錐」 。Kuhn , HW; Tucker, AW (編)。線形不等式と関連システム。プリンストン: プリンストン大学出版局。pp. 19–40。ISBN 0691079994。
• Rockafellar, RT (1979).凸解析. プリンストン大学出版局. p. 200.
• Kutateladze SS「Farkas の補題の再考」Siberian Mathematical Journal、2010 年、第 51 巻、第 1 号、78–87 ページ。