למת הנגישות

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

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

ניסוח פורמלי

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

יהיו $x \in Ω^{\circ}$ ו- $y \in \partial Ω$ , כאשר $Ω^{\circ}$ ו- $\partial Ω$ הם הפנים והשפה של $Ω$ , בהתאמה.

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

נקבע נקודה $z_{0} = λ_{0} x + (1 - λ_{0}) y$ מהקטע $[x, y)$ . נניח $λ_{0} \neq 1$ כי אחרת $z_{0} = x$ וברור שהנקודה בפנים של $Ω$ .

נתון $x \in Ω^{\circ}$ ולכן קיים $r_{0} > 0$ המקיים $B (x, r_{0}) \subset Ω^{\circ}$ .

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

$φ (w) = \frac{1}{1 - λ_{0}} [z_{0} - λ_{0} w]$

נשים לב לשתי תכונות של $φ$ :

מהתכונות הנ"ל נסיק ש $φ$ יוצרת קשר חח"ע ועל בין $B (x, r_{0})$ לבין $B (y, \frac{λ_{0}}{1 - λ_{0}} r_{0})$ .

נתון $y \in \bar{Ω}$ ולכן הכדור $B (y, \frac{λ_{0}}{1 - λ_{0}} r_{0})$ נחתך עם $Ω$ .

יהי $w \in B (x, r_{0})$ כך ש $φ (w) \in Ω \cap B (y, \frac{λ_{0}}{1 - λ_{0}} r_{0})$ .

נשים לב ש $z_{0} = λ_{0} w + (1 - λ_{0}) φ (w)$ .

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

$ψ (u) = λ_{0} u + (1 - λ_{0}) φ (w)$

נשים לב ש:

מאחר ש $w \in B (x, r_{0})$ אז קיים $r_{1} > 0$ כך ש $B (w, r_{1}) \subset B (x, r_{0}) \subset Ω$ .

כמו קודם, $ψ$ יוצרת קשר חח"ע ועל בין $B (w, r_{1})$ לבין $B (z_{0}, λ_{0} r_{1})$ .

אבל אם $u \in B (w, r_{1})$ אז $ψ (u) \in Ω$ (כי $u \in Ω$ וגם $φ (w) \in Ω$ ו- $0 < λ_{0} < 1$ ).

כלומר $B (z_{0}, λ_{0} r_{1}) \subset Ω$ שזה גורר $z_{0} \in Ω^{\circ}$ .

A. L. Peressini, F. E. Sullivan J. J. Uhl, Jr. The Mathematics of Nonlinear Programming p.164-165

למת הנגישות39706212