למת הנגישות

קבוצה קמורה Ω (בצהוב), נקודת שפה Υ, נקודה פנימית Χ, וקו המחבר ביניהן. על פי הלמה, כל הקו (מלבד Υ) מכיל נקודות פנימיות בלבד.

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

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

ניסוח פורמלי

תהי $\mathrm{\Omega }\subseteq {ℝ}^n$ קבוצה קמורה עם פנים ושפה לא ריקים.

יהיו $𝒙\in {\mathrm{\Omega }}^{\circ }$ ו- $𝒚\in \partial \mathrm{\Omega }$, כאשר ${\mathrm{\Omega }}^{\circ }$ ו-$\partial \mathrm{\Omega }$ הם הפנים והשפה של $\mathrm{\Omega }$, בהתאמה.

אז ה"קו החצי פתוח" מ-$𝒙$ ל- $𝒚$ $[𝒙,𝒚)=\{\lambda 𝒙+(1-\lambda )𝒚|0<\lambda \le 1\}$ מכיל אך ורק נקודות פנימיות.

הוכחה

נקבע נקודה ${𝒛}_0={\lambda }_0𝒙+(1-{\lambda }_0)𝒚$ מהקטע $[𝒙,𝒚)$. נניח ${\lambda }_0\ne 1$ כי אחרת ${𝒛}_0=𝒙$ וברור שהנקודה בפנים של $\mathrm{\Omega }$.

נתון $𝒙\in {\mathrm{\Omega }}^{\circ }$ ולכן קיים $r_0>0$ המקיים $B(𝒙,r_0)\subset {\mathrm{\Omega }}^{\circ }$.

נגדיר $\phi :{ℝ}^n\to {ℝ}^n$ כך:

$\phi (𝒘)=\frac{1}{1-{\lambda }_0}[{𝒛}_0-{\lambda }_0𝒘]$

נשים לב לשתי תכונות של $\phi$:

1. $\Vert \phi (𝒘)-\phi (𝒙)\Vert =\frac{{\lambda }_0}{1-{\lambda }_0}\Vert 𝒘-𝒙\Vert$
2. $\phi (𝒙)=𝒚$

מהתכונות הנ"ל נסיק ש$\phi$ יוצרת קשר חח"ע ועל בין $B(𝒙,r_0)$ לבין $B(𝒚,\frac{{\lambda }_0}{1-{\lambda }_0}{r}_0)$.

נתון $𝒚\in \overline{\mathrm{\Omega }}$ ולכן הכדור $B(𝒚,\frac{{\lambda }_0}{1-{\lambda }_0}{r}_0)$ נחתך עם $\mathrm{\Omega }$.

יהי $𝒘\in B(𝒙,r_0)$ כך ש$\phi (𝒘)\in \mathrm{\Omega }\cap B(𝒚,\frac{{\lambda }_0}{1-{\lambda }_0}{r}_0)$.

נשים לב ש${𝒛}_0={\lambda }_0𝒘+(1-{\lambda }_0)\phi (𝒘)$.

נגדיר $\psi :{ℝ}^n\to {ℝ}^n$

$\psi (𝒖)={\lambda }_0𝒖+(1-{\lambda }_0)\phi (𝒘)$

נשים לב ש:

1. $\Vert \psi (𝒖)-\psi (𝒘)\Vert ={\lambda }_0\Vert 𝒖-𝒘\Vert$
2. $\psi (𝒘)={𝒛}_0$

מאחר ש$𝒘\in B(𝒙,r_0)$ אז קיים $r_1>0$ כך ש$B(𝒘,r_1)\subset B(𝒙,r_0)\subset \mathrm{\Omega }$.

כמו קודם, $\psi$ יוצרת קשר חח"ע ועל בין $B(𝒘,r_1)$ לבין $B({𝒛}_0,{\lambda }_0{r}_1)$.

אבל אם $𝒖\in B(𝒘,r_1)$ אז $\psi (𝒖)\in \mathrm{\Omega }$ (כי $𝒖\in \mathrm{\Omega }$ וגם $\phi (𝒘)\in \mathrm{\Omega }$ ו- $0<{\lambda }_0<1$).

כלומר $B({𝒛}_0,{\lambda }_0{r}_1)\subset \mathrm{\Omega }$ שזה גורר ${𝒛}_0\in {\mathrm{\Omega }}^{\circ }$.