Bir polihedronun aşırı bir nokta içerdiğini ancak ve ancak sıkı kısıtlamalardan oluşan bir matris kullanan bir çizgi içermediğini kanıtlayın
Çokyüzlü olduğunu kanıtlamak istiyorum $P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$ sadece ve ancak bir çizgi içermiyorsa uç noktaya sahiptir, ancak bunu belirli bir şekilde yapmak istiyorum (tümevarım yoluyla bir ispatın farkındayım $n$Bu, bu sonucu herhangi bir kapalı konveks küme için genelleştirir, ancak buradaki ispata böyle gitmek istemiyorum). Özellikle şu sonucu kullanmak istiyorum:
$x$ aşırı bir nokta $P$ ancak ve ancak $\text{rank}(A^=) = n$, nerede $A^=$ sıkı / aktif kısıtlamaların matrisidir $x$.
Bunu nasıl kanıtlayacağımı zaten biliyorum $P$ bir satır içeriyorsa $P$uç noktaları yok ama sorum sohbetle ilgili. Resmi olmayan bir kanıt taslağım var, ancak bunu titiz hale getirmemize yardımcı olmaktan memnun olurum. Bunu göstermek istiyorum eğer$P$uç nokta içermez, bu durumda bir çizgi içermelidir. İşte benim kaba fikrim:
İzin Vermek $x\in P$. Aşırı olmadığını biliyoruz, bu yüzden var$d_1\in\mathbb{R}^n$ öyle ki $x + td_1\in P$ için $t\in (-\varepsilon_1, \varepsilon_1)$ yeterince küçük için $\varepsilon_1$. Ya$x + td_1$ içinde bulunan bir satırdır $P$, bu durumda işimiz biter veya $x \pm td_1$ bazıları için aktif / sıkı kısıtlamaya sahiptir $t = t_1$. WLOG, '+' durumunu varsayar, yani$x + t_1d_1$aktif bir kısıtlamaya sahip. Varsayımla,$x + t_1d_1$ aşırı bir nokta değil ve bu nedenle var $d_2\in\mathbb{R}^n$ içinde olmayan $\text{span}(d_1)$ öyle ki $(x + t_1d_1) \pm td_2\in P$ için $t\in (-\varepsilon_2, \varepsilon_2)$ yeterince küçük için $\varepsilon_2$. Ya$P$ satırı içerir $(x + t_1d_1) + td_2$ bu durumda bitirdik ya da var $t = t_2$ öyle ki $(x + t_1d_1) \pm t_2d_2$aktif bir kısıtlamaya sahip. Yine WLOG, '+' durumunu varsayar. Dan beri$d_2$ içinde değil $\text{span}(d_1)$o zaman önceki aktif kısıtlama hala aktiftir ve şimdi yeni bir kısıtlama da aktiftir. Bu süreci yineliyoruz, böylece bir$d_3\in\mathbb{R}^n$ değil $\text{span}(d_1, d_2)$ öyle ki $(x + t_1d_1 + t_2d_2) \pm td_3$ içinde bulunur $P$ küçük için $t$ ve ya bu bir satır $P$ veya orada $t_3$ öyle ki $x + t_1d_1 + t_2d_2 + t_3d_3$aktif bir kısıtlamaya sahiptir. Dan beri$d_3\notin\text{span}(d_1, d_2)$, orijinal iki aktif kısıtlama hala aktif olacak ve bu nedenle şimdi üçüncü bir aktif kısıtlama var, vb. Bir noktada ya bir çizgi bulmuş olacağız ya da $x + t_1d_1 + \cdots + t_nd_n$ hangisi $n$aktif kısıtlamalar. Ancak bu, aktif kısıtlamaların matrisinin$A^=$ bu nokta için rütbe $n$ki bu şu anlama gelir $x + t_1d_1 + \cdots + t_nd_n$hipotez ile çelişen aşırıdır. Bu nedenle, bu sürecin bazı yinelemelerinde mutlaka bir yön bulmuş olacağız$d_i$ öyle ki bu yöndeki çizgi, $P$.
Sezgilerim bana bunun gibi bir şeyin çalışması gerektiğini söylüyor, ancak bunu titiz hale getirmek için mücadele ediyorum. Özellikle, her birinin$d_i$ öncekinin aralığında değil $d_1,\dots, d_{i - 1}$ama bunun doğru olduğunu nasıl garanti edeceğimi bilmiyorum. İkincisi, her biri$d_i$ öncekinin aralığında değil $d_1,\dots, d_{i - 1}$ daha sonra aktif olan kısıtlamalar yöne doğru hareket ettikten sonra hala aktif kalır $d_i$. Bu doğru olması gerektiği gibi geliyor ama bunu nasıl kanıtlayacağımı bilmiyorum. Son olarak, argümanıma göre en azından sahip olmalıyım$n$ yinelemeyi bitirirsek etkin kısıtlamalar $n$ kez, ama aslında rütbesinin nasıl kanıtlanacağını bilmiyorum $A^=$ aslında eşittir $n$bu durumda (bu, bu aşamaya geldiysek bize istenen çelişkiyi verir). Belki de durum böyledir$\text{rank}(A^=)$ hala kesinlikle daha az $n$sahip olsak bile $n$aktif kısıtlamalar. Umarım bu imkansızdır, ancak bunu nasıl kanıtlayacağımı bilmiyorum.
Birisi, bu noktaların kesin bir şekilde ifade edilmesine yardımcı olabilir, böylece bu geçerli bir kanıt olur veya bunun yerine bu ispatın neden işe yaramadığını gösterirse, çok minnettar olurum.
Yanıtlar
İspatınızın titizlikle yapılabileceğinden oldukça eminim. Prosedürünüzün her aşamasında,$\ A_j^=\ $ sıkı kısıtlamaların matrisi olun ve $\ A_j^<\ $ için gevşek sınırlamaların matrisi $\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $. Çünkü$\ x_j \ $ aşırı bir nokta değil, rütbesi $\ A_j^=\ $ daha az $\ n\ $böylece seçebilirsin $\ d_{j+1}\ $çekirdeğinde yatmak. Sonra matris ile tüm kısıtlamalar$\ A_j^=\ $ için sıkı kalacak $\ x_j+td_{j+1}\ $ (ne olursa olsun $\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $ya da değil). Eğer$\ x_j+td_{j+1}\ $ bir çizgi değil, matrisli bir veya daha fazla kısıtlama $\ A_j^<\ $ için sıkı olmalı $\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. Bu nedenle$\ A_j^=\ $ katı bir alt matris olmalıdır $\ A_{j+1}^=\ $. Dan beri$\ A\ $ yalnızca sınırlı sayıda satıra sahipse, prosedürünüz bir satırla sonlandırılmalıdır $\ x_k+td_{k+1}\ $ bazı $\ k\ $veya ile $\ A_k^==A\ $, ve dolayısıyla $\ Ax_k=b\ $. İkinci durumda, çünkü$\ x_k\ $ aşırı bir nokta değil, o zaman rütbesi $\ A\ $ daha az olmalı $\ n\ $ve dolayısıyla boş olmayan bir çekirdeğe sahip olursunuz. Eğer$\ d\ $ çekirdeğin sıfır olmayan herhangi bir üyesi ise $\ x_k+td\ $ bir sıra olacak $\ P\ $.