משפט התמיכה

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

משפט זה הוא משפט יסודי ונחוץ להוכחת משפט קארוש-קון-טאקר - אחת מהתוצאות המרכזיות בתחום.

המשפט דומה בנוסח למשפט ההפרדה הבסיסי אך מתייחס לנקודת שפה של הקמורה במקום לנקודה כללית שלא נמצאת בקבוצה.

ניסוח פורמלי

תהי $\Omega$ קבוצה קמורה עם פנים לא ריק במרחב האוקלידי $\mathbb {R} ^{n}$ ותהי $z$ בשפה של $\Omega$ . אז קיים ווקטור ${\bar {0}}\neq a\in \mathbb {R} ^{n}$ המקיים:

$a\cdot x\leq a\cdot z$

לכל $x\in \Omega$ .

הוכחה

תהי $y$ נקודה פנימית ו- $z$ נקודת שפה של $\Omega$ . לכל $t>1$ נגדיר $z_{t}=y+t(z-y)$ .

נשים לב שלכל $t$ כנ"ל מתקיים $z_{t}\notin {\bar {\Omega }}$ כי אחרת, על פי למת הנגישות, הקו $(z_{t},y]=\{\lambda y+(1-\lambda )z_{t}\,|\,\ 0<\lambda \leq 1\}$ מכיל אך ורק נקודות פנימיות. אבל אם נציב $\lambda =1-{\frac {1}{t}}$ נקבל ש $z$ נקודה פנימית של $\Omega$ סתירה.

מהעובדה ש $z_{t}\notin {\bar {\Omega }}$ נוכל להפעיל את משפט ההפרדה הבסיסי ולקבל וקטור ${\bar {0}}\neq b_{t}\in \mathbb {R} ^{n}$ המקיים:

$b_{t}\cdot x<b_{t}\cdot z_{t}$

לכל $x\in \Omega$ ולכל $t>1$ .

מאחר שהאי שוויון הנ"ל יישמר גם אם ננרמל את $b_{t}$ נרשה לעצמנו להתייחס לכל $b_{t}$ כווקטור מנורמל, כלומר $\lVert b_{t}\rVert =1$ לכל $t>1$ .

נגדיר סדרה $\{t_{k}\}$ המקיימת שתי תכונות:

$\textstyle \lim _{k\to \infty }\displaystyle t_{k}=1$
$t_{k}>1$ לכל $k$ .

ונגדיר $a_{k}=b_{t_{k}}$ .

נשים לב ש $\lVert a_{k}\rVert =1$ לכל $k$ . ולכן ממשפט בולצאנו ווירשטראס קיימת לסדרה $\{a_{k}\}$ תת סדרה $\{a_{k_{p}}\}$ ששואפת לאיזשהו $a\in \mathbb {R} ^{n}$ .