Buktikan bahwa polihedron mengandung titik ekstrim jika dan hanya jika tidak mengandung garis menggunakan matriks batasan ketat
Saya ingin membuktikan bahwa polihedron $P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$ memiliki titik ekstrim jika dan hanya jika tidak mengandung garis, tetapi saya ingin melakukannya dengan cara tertentu (saya mengetahui bukti dengan induksi pada $n$yang menggeneralisasi hasil ini untuk setiap set cembung tertutup, tetapi ini bukan cara saya ingin membahas bukti di sini). Secara khusus saya ingin memanfaatkan hasil yang:
$x$ adalah titik ekstrim $P$ jika dan hanya jika $\text{rank}(A^=) = n$, dimana $A^=$ adalah matriks batasan ketat / aktif $x$.
Saya sudah tahu bagaimana membuktikannya jika $P$ berisi garis $P$tidak ada poin ekstrimnya, tapi pertanyaan saya tentang kebalikannya. Saya memiliki sketsa bukti informal, tetapi saya akan menghargai bantuan yang membuatnya ketat. Saya ingin menunjukkan bahwa jika$P$tidak mengandung titik ekstrim, maka harus mengandung garis. Inilah ide kasar saya:
Membiarkan $x\in P$. Kami tahu itu tidak ekstrim, jadi karena itu ada$d_1\in\mathbb{R}^n$ seperti yang $x + td_1\in P$ untuk $t\in (-\varepsilon_1, \varepsilon_1)$ cukup kecil $\varepsilon_1$. Antara$x + td_1$ adalah baris yang ada di $P$, dalam hal ini kami selesai, atau $x \pm td_1$ memiliki batasan aktif / ketat untuk beberapa $t = t_1$. WLOG menganggap kasus '+', yaitu$x + t_1d_1$yang memiliki kendala aktif. Dengan asumsi,$x + t_1d_1$ bukanlah titik ekstrim, dan karenanya ada $d_2\in\mathbb{R}^n$ yang tidak ada $\text{span}(d_1)$ seperti yang $(x + t_1d_1) \pm td_2\in P$ untuk $t\in (-\varepsilon_2, \varepsilon_2)$ cukup kecil $\varepsilon_2$. Antara$P$ berisi garis $(x + t_1d_1) + td_2$ dalam hal ini kita selesai, atau ada $t = t_2$ seperti yang $(x + t_1d_1) \pm t_2d_2$yang memiliki kendala aktif. Sekali lagi WLOG menganggap kasus '+'. Sejak$d_2$ tidak masuk $\text{span}(d_1)$maka batasan aktif dari sebelumnya masih aktif, dan sekarang batasan baru juga aktif. Kami mengulangi proses ini, sehingga kami menemukan file$d_3\in\mathbb{R}^n$ tidak masuk $\text{span}(d_1, d_2)$ seperti yang $(x + t_1d_1 + t_2d_2) \pm td_3$ terkandung dalam $P$ untuk kecil $t$ dan entah ini jalur masuk $P$ atau ada $t_3$ seperti yang $x + t_1d_1 + t_2d_2 + t_3d_3$memiliki kendala aktif. Sejak$d_3\notin\text{span}(d_1, d_2)$, dua pembatas aktif yang asli akan tetap aktif, sehingga sekarang ada pembatas aktif ketiga, dll. Pada titik tertentu kita akan menemukan garis, atau kita akan menemukan $x + t_1d_1 + \cdots + t_nd_n$ yang memiliki $n$kendala aktif. Tapi kemudian ini harus menyiratkan bahwa matriks kendala aktif$A^=$ untuk poin ini adalah peringkat $n$, yang menyiratkan hal itu $x + t_1d_1 + \cdots + t_nd_n$ekstrim, yang bertentangan dengan hipotesis. Jadi, oleh karena itu, pada beberapa pengulangan proses ini kita akan menemukan arahnya$d_i$ sedemikian rupa sehingga garis ke arah itu tertampung $P$.
Intuisi saya memberi tahu saya sesuatu seperti ini seharusnya berhasil, tetapi saya berjuang untuk membuatnya ketat. Secara khusus, saya membuat klaim itu masing-masing$d_i$ tidak dalam rentang waktu sebelumnya $d_1,\dots, d_{i - 1}$, tapi saya tidak tahu bagaimana menjamin ini benar. Kedua, saya mengklaim itu karena masing-masing$d_i$ tidak dalam rentang sebelumnya $d_1,\dots, d_{i - 1}$ kemudian kendala yang aktif sebelumnya masih tetap aktif setelah melakukan perjalanan searah $d_i$. Sepertinya ini benar, tapi saya tidak yakin bagaimana membuktikannya. Akhirnya, dengan argumen saya, saya harus memiliki setidaknya$n$ kendala aktif jika kita akhirnya melakukan iterasi $n$ kali, tapi saya tidak benar-benar tahu bagaimana membuktikan pangkat itu $A^=$ sebenarnya sama dengan $n$dalam hal ini (yang memberi kita kontradiksi yang diinginkan jika kita sudah sampai pada tahap ini). Mungkin memang begitu$\text{rank}(A^=)$ masih kurang dari $n$, meskipun kami punya $n$kendala aktif. Saya berharap ini tidak mungkin, tetapi saya tidak yakin bagaimana membuktikannya.
Jika seseorang dapat membantu membuat poin-poin ini ketat sehingga ini menjadi bukti yang valid, atau malah menunjukkan mengapa bukti ini tidak dapat berfungsi, saya akan sangat menghargai.
Jawaban
Saya cukup yakin bukti Anda dapat dibuat dengan teliti. Pada setiap tahap prosedur Anda, biarkan$\ A_j^=\ $ menjadi matriks kendala ketat dan $\ A_j^<\ $ matriks kendala kendur untuk $\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $. Karena$\ x_j \ $ bukanlah titik ekstrim, peringkat $\ A_j^=\ $ kurang dari $\ n\ $, jadi Anda bisa memilih $\ d_{j+1}\ $terletak pada intinya. Kemudian semua kendala dengan matriks$\ A_j^=\ $ akan tetap ketat untuk $\ x_j+td_{j+1}\ $ (terlepas dari apa pun $\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $atau tidak). Jika$\ x_j+td_{j+1}\ $ bukan garis, maka satu atau lebih batasan dengan matriks $\ A_j^<\ $ harus ketat untuk $\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. Karena itu$\ A_j^=\ $ harus merupakan submatriks yang ketat dari $\ A_{j+1}^=\ $. Sejak$\ A\ $ hanya memiliki jumlah baris yang terbatas, prosedur Anda harus diakhiri baik dengan sebuah baris $\ x_k+td_{k+1}\ $ untuk beberapa $\ k\ $, atau dengan $\ A_k^==A\ $, dan karenanya $\ Ax_k=b\ $. Dalam kasus terakhir, sejak$\ x_k\ $ bukanlah titik ekstrim, maka peringkat $\ A\ $ harus kurang dari $\ n\ $dan karenanya memiliki kernel yang tidak kosong. Jika$\ d\ $ adalah anggota kernel selain nol $\ x_k+td\ $ akan menjadi antrean $\ P\ $.