พิสูจน์ว่ารูปทรงหลายเหลี่ยมมีจุดสุดขั้วก็ต่อเมื่อไม่มีเส้นโดยใช้เมทริกซ์ของข้อ จำกัด ที่แน่น
ฉันต้องการพิสูจน์ว่าเป็นรูปทรงหลายเหลี่ยม $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)$ข้อ จำกัด ที่ใช้งานอยู่เดิมสองข้อจะยังคงใช้งานได้ดังนั้นตอนนี้จึงมีข้อ จำกัด ที่ใช้งานอยู่ข้อที่สามเป็นต้นในบางจุดเราจะพบเส้นหรือเราจะมี $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}\ $ ไม่ใช่เส้นแล้วเป็นข้อ จำกัด อย่างน้อยหนึ่งข้อที่มีเมทริกซ์ $\ A_j^<\ $ ต้องแน่นสำหรับ $\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. ดังนั้น$\ A_j^=\ $ ต้องเป็น subatrix ที่เข้มงวดของ $\ 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\ $.