厳密な制約の行列を使用して、多面体に線が含まれていない場合に限り、多面体に極値が含まれていることを証明します。
多面体であることを証明したい $P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$ 線が含まれていない場合にのみ極端なポイントがありますが、特定の方法でそうしたいです（私は帰納法による証明を知っています $n$これは、閉じた凸集合に対してこの結果を一般化しますが、これは私がここで証明を行う方法ではありません）。具体的には、次のような結果を利用したいと思います。
$x$ の極値です $P$ 場合に限り $\text{rank}(A^=) = n$、 どこ $A^=$ のタイト/アクティブ制約のマトリックスです $x$。
私はすでにそれを証明する方法を知っています $P$ 次に行が含まれています $P$極端な点はありませんが、私の質問はその逆です。私は証明の非公式のスケッチを持っていますが、それを厳密にするためにいくつかの助けをいただければ幸いです。私はそれを示したい$P$極端な点が含まれていない場合は、線が含まれている必要があります。これが私の大まかな考えです：
しましょう $x\in P$。極端ではないことはわかっているので、$d_1\in\mathbb{R}^n$ そのような $x + td_1\in P$ ために $t\in (-\varepsilon_1, \varepsilon_1)$ 十分に小さい場合 $\varepsilon_1$。どちらか$x + td_1$ に含まれる行です $P$、その場合は完了、または $x \pm td_1$ 一部のアクティブ/タイトな制約があります $t = t_1$。WLOGは、「+」の場合を想定しています。$x + t_1d_1$アクティブな制約があります。仮定により、$x + t_1d_1$ 極値ではないので、 $d_2\in\mathbb{R}^n$ ない $\text{span}(d_1)$ そのような $(x + t_1d_1) \pm td_2\in P$ ために $t\in (-\varepsilon_2, \varepsilon_2)$ 十分に小さい場合 $\varepsilon_2$。どちらか$P$ 行が含まれています $(x + t_1d_1) + td_2$ その場合、完了したか、存在します $t = t_2$ そのような $(x + t_1d_1) \pm t_2d_2$アクティブな制約があります。ここでも、WLOGは「+」の場合を想定しています。以来$d_2$ にありません $\text{span}(d_1)$その後、以前のアクティブな制約はまだアクティブであり、新しい制約もアクティブになります。このプロセスを繰り返すことで、$d_3\in\mathbb{R}^n$ ありませんで $\text{span}(d_1, d_2)$ そのような $(x + t_1d_1 + t_2d_2) \pm td_3$ に含まれています $P$ 小さいため $t$ そしてこれはの行です $P$ またはあります $t_3$ そのような $x + t_1d_1 + t_2d_2 + t_3d_3$アクティブな制約があります。以来$d_3\notin\text{span}(d_1, d_2)$、元の2つのアクティブな制約は引き続きアクティブであるため、3番目のアクティブな制約などがあります。ある時点で、行が見つかるか、次のようになります。 $x + t_1d_1 + \cdots + t_nd_n$ 持っている $n$アクティブな制約。しかし、これはアクティブな制約のマトリックスを意味するはずです$A^=$ この点はランクです $n$、それはそれを意味します $x + t_1d_1 + \cdots + t_nd_n$は極端であり、これは仮説と矛盾します。したがって、このプロセスのある反復で、必然的に方向性が見つかります。$d_i$ その方向の線が含まれるように $P$。
私の直感では、このようなことがうまくいくはずだと言っていますが、これを厳密にするのに苦労しています。具体的には、私はそれぞれが$d_i$ 上記の範囲内ではありません $d_1,\dots, d_{i - 1}$、しかし、これが真実であることを保証する方法がわかりません。第二に、私はそれぞれ以来$d_i$ 以前のスパンではありません $d_1,\dots, d_{i - 1}$ その後、前にアクティブだった拘束は、方向に移動した後もアクティブのままになります $d_i$。これは本当のはずのように感じますが、それを証明する方法がわかりません。最後に、私の議論では、少なくとも$n$ 反復することになった場合のアクティブな制約 $n$ 何度も、しかし私は実際にそのランクを証明する方法を知りません $A^=$ 実際には等しい $n$この場合（この段階に到達した場合、望ましい矛盾が生じます）。多分それはその場合です$\text{rank}(A^=)$ まだ厳密に $n$、 $n$アクティブな制約。これが不可能であることを願っていますが、それを証明する方法がわかりません。
誰かがこれらの点を厳密にして、これが有効な証明になるように、または代わりにこの証明が機能しない理由を示すことができれば、私は非常に感謝します。
回答
私はあなたの証明が厳密にされることができるとかなり確信しています。手順の各段階で、$\ A_j^=\ $ 厳しい制約のマトリックスであり、 $\ A_j^<\ $ のスラック制約の行列 $\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $。なぜなら$\ x_j \ $ 極端なポイントではありません、のランク $\ A_j^=\ $ より少ない $\ n\ $、選択できるように $\ d_{j+1}\ $そのカーネルにあること。次に、行列を使用したすべての制約$\ A_j^=\ $ タイトなままになります $\ x_j+td_{j+1}\ $ （どうか関わらず $\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $か否か）。場合$\ x_j+td_{j+1}\ $ が線ではない場合、行列を使用した1つ以上の制約 $\ A_j^<\ $ タイトでなければなりません $\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $。したがって、$\ A_j^=\ $ の厳密な部分行列である必要があります $\ A_{j+1}^=\ $。以来$\ A\ $ 行数が有限である場合、プロシージャはいずれかの行で終了する必要があります $\ x_k+td_{k+1}\ $ いくつかのための $\ k\ $、または $\ A_k^==A\ $、 それゆえ $\ Ax_k=b\ $。後者の場合、$\ x_k\ $ 極端なポイントではありません、そしてのランク $\ A\ $ 未満である必要があります $\ n\ $したがって、空でないカーネルがあります。場合$\ d\ $ カーネルのゼロ以外のメンバーである場合、 $\ x_k+td\ $ の行になります $\ P\ $。