משפט התמיכה

קבוצה קמורה Ω (בצהוב) וישר תומך שמכיל נקודת שפה ($x$) ומפריד את המישור לשני חלקים (תכלת ואדום בהיר).

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

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

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

מקרה בו תנאי המשפט לא מתקיימים ($x$ אכן נקודת שפה אבל $\mathrm{\Omega }$ לא קבוצה קמורה) ולכן לא מובטחת לנו התוצאה (היפר-מישור שעובר בנקודת השפה ומחלק את המרחב לשני חלקים כשאר הקבוצה כולה מוכלת באחד מהם).

ניסוח פורמלי

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

$a\cdot x\le a\cdot z$

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

הוכחה

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

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

מהעובדה ש$z_t\notin \overline{\mathrm{\Omega }}$ נוכל להפעיל את משפט ההפרדה הבסיסי ולקבל וקטור $\overline{0}\ne b_t\in {\mathbb{ℝ}}^n$ המקיים:

$b_t\cdot x<b_t\cdot z_t$

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

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

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

1. $\underset{k\to \mathrm{\infty }}{\lim }{t}_k=1$
2. $t_k>1$ לכל $k$.

ונגדיר $a_k=b_{t_k}$.

נשים לב ש$\Vert a_k\Vert =1$ לכל $k$. ולכן ממשפט בולצאנו ווירשטראס קיימת לסדרה $\{a_k\}$ תת סדרה $\{a_{k_p}\}$ ששואפת לאיזשהו $a\in {\mathbb{ℝ}}^n$.

מרציפות הנורמה נובע שהגבול $a$ מקיים $\Vert a\Vert =1$ ולכן בפרט מתקיים $a\ne \overline{0}$.

אבל אם כך אז מרציפות המכפלה הפנימית מתקבל:

$a\cdot x=\underset{p\to \mathrm{\infty }}{\lim }(a_{k_p}\cdot x)\le \underset{p\to \mathrm{\infty }}{\lim }(a_{k_p}\cdot z_{t_{k_p}})=a\cdot z$

לכל $x\in \mathrm{\Omega }$ ומכאן מ.ש.ל

לקריאה נוספת

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

משפט התמיכה40805925