代替定理について詳しく解説

導入

ファルカスの補題が最も有名な代替定理はすべて、実際の有限次元ベクトル空間における線形不等式系に関係します。これには、システムが一貫しているかどうか、つまり、解 (0 が明らかな解の場合は非ゼロ解) を許容するかどうかを決定できる基準を与えることが含まれます。

原理は常に次のとおりです。不等式系に直面した場合、これらの不等式を正またはゼロの係数で線形結合して演算できます。これがすべて系の結果となります (場合に応じて、厳密に正の係数を賢明に使用します)。ケースバイケースで、厳密な不平等となる結果を生み出します）。これらの結果の 1 つが不条理である場合 (通常は0 < 0 )、初期システムでは解を得ることができないことは明らかです。ただし、システムが矛盾するためのこの十分条件は毎回必要であることがわかります。以下の各定理はその変形を表しています。

「代替定理」という名前は、必要十分条件が方程式と不等式が混在する系の解を求める問題の形式も持つことに由来しています。したがって、私たちは 2 つのシステムが並行して存在しており、そのうちの 1 つだけが解決策を持っていることに気づきます。行列の観点から翻訳すると、代替案の 2 つの分岐は同じ精神の定式化を持ち、ヴィルの定理の場合は驚くほど似ています。

厳密な不等式の系と広範な不等式の系: ゴードンとスティムケの定理

ゴーダンの定理

これは、次の形式のすべての厳密な不等式のシステムの場合をカバーします。

$$ {f_1(y)> 0,\, f_2(y)>0,\ldots,f_k(y)> 0} $$

ここで、 f _{j は}有限次元の実ベクトル空間E上の線形形式です。

このような系の解の存在には明らかな障害があります。この不等式群のゼロ以外の正の係数を使って線形結合を行うと、すべての解によって検証される新しい厳密な不等式が得られます。この線形結合の係数を調整して、不条理な不等式0 > 0が得られる場合、それはシステムに一貫性がないためです。

ゴーダンの定理により、矛盾したシステムからでも不等式0 > 0が得られることが保証されます。

ゴーダンの定理 (1873) —みましょう

$$ {f_1,\ldots,f_k} $$

有限次元Eの実ベクトル空間上の線形形状。それで：

$$ {\{y\in E\,\mid\,f_1(y)> 0,f_2(y)>0,\ldots,f_k(y)> 0\}=\emptyset} $$

もし、そしてその場合に限り

書き込みがあります

$$ {0=\lambda_1 f_1+\cdots+\lambda_k f_k} $$

すべての係数が正またはゼロで、少なくとも 1 つはゼロではありません。

スティムケの定理

これは、広い意味での線形不等式系に関係します。

$$ {f_1(y)\geq 0,\, f_2(y)\geq0,\ldots,f_k(y)\geq 0} $$

。

その声明はまさに次のとおりです。

スティエムケの定理 (1913) —みましょう

$$ {f_1,\dots,f_k} $$

有限次元ベクトル空間上の線形形状E.それで：

$$ {\{y\in E\,\mid\,f_1(y)\geq 0,\ldots,f_k(y)\geq 0} $$

、これらの不等式のうち少なくとも 1 つは厳密です

$$ {\}=\emptyset} $$

もし、そしてその場合に限り

書き込みがあります

$$ {0=\lambda_1 f_1+\dots+\lambda_k f_k} $$

すべて厳密に正の係数を使用します。

このステートメントは、「これらの不等式の少なくとも 1 つは厳密である」という専門的な理由から、シリーズの他の定理よりも少し読みにくくなっています。その理由は、大きな不等式の系が完全に矛盾することはありえないためです。それらの解には少なくとも0があり、それを超えると、対応する線形方程式系を検証するすべての点が存在します。したがって、すべての形式f _jの核の交差にあるものを重要な解として考慮しないことにより、系の形式を少し複雑にする必要があります。

ゴーダンの定理の証明

このページで検討するすべての定理の中で、ゴーダンの定理は、証明に追加の専門的要素が最も少ない定理です。これは、凸面の分離定理 (「ハーン-バナハの定理の第 2 幾何学的形式」と呼ばれることもあります) または閉じた凸面の射影定理に基づくことができます。ここで行われるのは最後の選択です。

多くの場合、双対で操作を実行するのが実用的であるため、 Eにユークリッド構造を装備しましょう。したがって、インデックスjごとに、 Eの一意のベクトルs _{j が}存在し、すべてのyについて_次のよう_に書くことができます。 y > 。

$$ {<-y_0|s_j-y_0>\leq 0} $$

ゴーダンの証明の核心に迫りましょう。この記事のすべての定理と同様、上昇する含意は明らかです。したがって、厳密な不等式の体系が矛盾していると仮定して、トップダウンの含意を示しましょう。特にy _{0 は}解ではないため、次のj が存在します。

$$ {f_j(y_0)\leq 0} $$

。したがって、

$$ {-\|y_0\| = 0} $$

これは、 0_がKに属し、したがってs _jの正の係数との線形結合であることを明確に証明します。

ゴーダンの定理はスティエムケの定理につながる

スティームケの定理の直接の証明は、凸面の分離理論を再度呼び出すことによって与えることができます。しかし、これがゴーダンの定理の「双対」定理であり、自然ではないにしても単純な代数操作によってそこから演繹できることを理解することは有益です。

これらの同じ操作が、後でヴィレの定理を述べることで行列形式で再び提示されるのを見ることになります。これらは、特に線形計画法における双対問題の理論の基礎に見られる重要なアイデアに基づいています。それは、スティムケの定理の等価性の 2 番目の分岐であり、最初は厳密な不等式 (条件0 < )の混合を読み取ります。 λ _j ) とベクトル方程式(条件

$$ {\lambda_1 f_1+\cdots+\lambda_k f_k=0} $$

) は、少しのスキルを使えば、厳密な不等式の単純なコレクションに変換でき、これにゴーダンの定理を適用できます。 Stiemke は最終的には、2 つの同等のステートメントの位置を交換した Gordan の書き直しであるように見えます。

から抽出することから始めます

$$ {(f_1,\ldots,f_k)} $$

最大限に自由な家族。たとえそれが再番号付けを意味するとしても、我々はそれがそうであると仮定します。

$$ {(f_1,\ldots,f_p)} $$

。ベースで勝手に完成させます

$$ {(f_1,\ldots,f_p,f’_{p+1},\ldots,f’_n)} $$

E ^*そして最後に注意します

$$ {(e_1,\ldots,e_n)} $$

Eの基底

$$ {(f_1,\ldots,f_p,f’_{p+1},\ldots,f’_n)} $$

は二重基礎です。したがって、 1とn の間のすべてのiと1とpの間のすべてのjについて、関係f _j ( e _i ) = δ _{i j} (クロネッカー記号) が成立します。 p + 1とkの間のjのf _{j は}最初のf _jの線形結合であるため、すべての形式のf _{j は}インデックスのすべてのe _iでキャンセルされます。

$$ {i \geq p+1} $$

。

これらの表記法が確立されたら、Stiemke の証明に着手しましょう。すべての発言と同様に、その意味合いが高まっていることは明らかです。したがって、0 は次の形式で書くことができないと仮定して、もう一方を対比して証明しましょう。

$$ {0=\lambda_1 f_1+\cdots+\lambda_k f_k} $$

不等式系のy解を構築することを目的として、 λ _jはすべて厳密に正です。

線形適用間の関係は、特定の基底のすべてのベクトルで真である場合にのみ真です。したがって、次のことに気づくことができます。

$$ {\left\{\begin{array}{l} \begin{matrix} \lambda_1>0\\ \vdots\\ \lambda_k>0\\ \end{matrix}\\ \begin{matrix} (\lambda_1 f_1+\cdots +\lambda_k f_k)(e_1)=0\\ \vdots\\ (\lambda_1 f_1+\cdots +\lambda_k f_k)(e_n)=0\\ \end{matrix}\\ \end{array}\right.} $$

f _j ( e _i )に関する情報をこのシステムに挿入すると、次のことがわかります。

$$ {\left\{\begin{array}{l} \begin{matrix} \lambda_1>0\\ \vdots\\ \lambda_k>0\\ \end{matrix}\\ \begin{matrix} \lambda_1&&&+\lambda_{p+1} f_{p+1}(e_1)+\cdots +\lambda_k f_k(e_1)=0\\ &&&\vdots\\ &&\lambda_p&+\lambda_{p+1} f_{p+1}(e_p)+\cdots +\lambda_k f_k(e_p)=0\\ \end{matrix}\\ \end{array}\right.} $$

証明の重要な点は、先行する不等式と方程式の混合系の矛盾は、不等式のみからなるより単純な系の矛盾として再表現できるということです。

システム

$$ {\left\{\begin{array}{l} \begin{matrix} \lambda_{p+1} f_{p+1}(e_1)+\cdots +\lambda_k f_k(e_1)<0\\ \vdots\\ \lambda_{p+1} f_{p+1}(e_p)+\cdots +\lambda_k f_k(e_p)<0\\ \end{matrix}\\ \end{array}\right.} $$

解決策はありません。

このシステムの形式は、ゴーダンの定理の枠組み内に収まります。したがって、正またはゼロの実数が存在します。

$$ {\alpha_1,\ldots,\alpha_p} $$

、少なくとも 1 つはゼロではありません。これを使用して、前のシステムに現れる形式のゼロ線形結合を構築できます。各λ _jの係数を連続的にキャンセルすると、次のことがわかります。

p + 1からkまでの任意のインデックスiに対して、

$$ {f_i(\alpha_1e_1+\cdots+\alpha_pe_p)=0} $$

。

また、関係f _j ( e _i ) = δ _{i j}から次のことがわかります。

1からpまでのインデックスiの場合、

$$ {f_i(\alpha_1e_1+\cdots+\alpha_pe_p)=\alpha_i} $$

。

それではポーズをとってみましょう

$$ {y=\alpha_1e_1+\cdots+\alpha_pe_p} $$

。次に、このベクトルを使用して、Stiemke の定理に従う不等式系の自明ではない解を構築したことに気づきます。

導入

厳密な不等式の系と広範な不等式の系: ゴードンとスティムケの定理

ゴーダンの定理

スティムケの定理

ゴーダンの定理の証明

ゴーダンの定理はスティエムケの定理につながる

参考資料

代替定理について詳しく解説・関連動画