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

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

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

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

ניסוח פורמלי

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

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

לכל $x\in \mathrm{\Omega }$.

הוכחה

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

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

לכל $x\in \mathrm{\Omega }$.

נגדיר $a=y-z$. ברור ש $a\ne \overline{0}$ ו- $a\cdot (x-z)\le 0$ לכל $x\in \mathrm{\Omega }$.

אם כך אז $a\cdot x\le a\cdot z$ לכל $x\in \mathrm{\Omega }$.

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

כלומר $a\cdot x\le \alpha <a\cdot y$ לכל $x\in \mathrm{\Omega }$ ומכאן מ.ש.ל.

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

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