משפט ההפרדה הבסיסי

המחשה דו־ממדית של המשפט. קבוצה קמורה $\Omega$ (בירוק), נקודה $y$ שלא נמצאת בקבוצה והיפר-מישור $(\cdot ,a)=\alpha$ המפריד בין הקבוצה והנקודה.

בגאומטריה, משפט ההפרדה הבסיסי עוסק בקשר בין קבוצות קמורות ונקודות שנמצאות מחוץ לקבוצה.

המשפט טוען שבהינתן נקודה שלא נמצאת בקבוצה הקמורה תמיד ניתן יהיה למצוא היפר-מישור שיפריד את הקבוצה מהנקודה.

ניסוח פורמלי

תהי $\Omega$ קבוצה קמורה וסגורה במרחב האוקלידי $\mathbb {R} ^{n}$ ויהי $y\in \mathbb {R} ^{n}$ המקיים $y\notin \Omega$ אז קיים ווקטור ${\bar {0}}\neq a\in \mathbb {R} ^{n}$ ומספר $\alpha \in \mathbb {R}$ כך ש:

$a\cdot x\leq \alpha <a\cdot y$

לכל $x\in \Omega$.

הוכחה

נתון $\Omega$ קמורה וסגורה ולכן ממשפט הקירוב הטוב ביותר קיים $z$ שהוא הווקטור הקרוב ביותר ל$y$ ב$\Omega$. מעובדה זו, נובע אי השוויון הבא:

$(y-z)\cdot (x-z)\leq 0$

לכל $x\in \Omega$.

נגדיר $a=y-z$. ברור ש $a\neq {\bar {0}}$ ו- $a\cdot (x-z)\leq 0$ לכל $x\in \Omega$.

אם כך אז $a\cdot x\leq a\cdot z$ לכל $x\in \Omega$.

נגדיר $\alpha =a\cdot z$ ונשים לב ש $a\cdot y-\alpha =a\cdot (y-z)=\lVert a\rVert ^{2}>0$

כלומר $a\cdot x\leq \alpha <a\cdot y$ לכל $x\in \Omega$ ומכאן מ.ש.ל.

קישורים חיצוניים

• A. L. Peressini, F. E. Sullivan J. J. Uhl, Jr. The Mathematics of Nonlinear Programming p.162–163