שאלה 4: קמירות ואופטימיזציה קלאסית

א מכפלה של פונקציות קמורות

נוסח הסעיף: האם מכפלת שתי פונקציות קמורות בהכרח קמורה, והאם היא בהכרח לא קמורה?

הרעיון: המילה "בהכרח" נבדקת באמצעות דוגמאות. צריך להציג מקרה שבו המכפלה אינה קמורה ומקרה שבו היא כן קמורה.

מקרה שבו המכפלה אינה קמורה: נבחר על כל הישר הממשי:

f קמורה ו-g ליניארית ולכן גם קמורה. אבל h″(x) שלילית כאשר x < 0 וחיובית כאשר x > 0, ולכן x³ אינה קמורה על כל הישר.

מקרה שבו המכפלה קמורה:

שתי הפונקציות קמורות, וגם המכפלה שלהן קמורה.

תוצאת הסעיף: המכפלה אינה בהכרח קמורה, אך גם אינה בהכרח לא קמורה. אין כלל חד-משמעי; בודקים את המכפלה עצמה.

ב כפל בקבוע אי־שלילי

נוסח הסעיף: אם f(x) קמורה ו-a ≥ 0, האם af(x) קמורה?

הרעיון: משתמשים ישירות באי־שוויון שמגדיר קמירות ומכפילים את שני אגפיו במספר שאינו משנה את כיוון האי־שוויון.

לכל שתי נקודות u,v בתחום ולכל t ∈ [0,1], קמירות f נותנת:

מכפילים ב-a ≥ 0:

זהו בדיוק אי־שוויון הקמירות עבור הפונקציה af. כאשר a=0 מתקבלת פונקציה קבועה, שגם היא קמורה.

תוצאת הסעיף: כן. כפל פונקציה קמורה בקבוע אי־שלילי שומר על קמירות.

ג פתרון בעיית האופטימיזציה

נוסח הסעיף: מצאו את x,y,z שממקסמים את פונקציית המטרה תחת שני האילוצים.

הרעיון: מפשטים את המטרה, מסדרים את האילוצים בצורת הקורס gᵢ≤bᵢ, בונים לגראנז' של בעיית מקסימום ומאמתים את תנאי KKT. הקעירות והאילוצים הליניאריים מבטיחים שהפתרון הוא גלובלי.

נסמן את פונקציית המטרה ב-F(x,y,z) ונפתח סוגריים:

מטריצת הסיאן של F היא:

diag(-2,-4,0) היא מטריצה אלכסונית שהערכים שעל האלכסון שלה הם -2,-4,0. היא שלילית למחצה, ולכן F קעורה. שני האילוצים ליניאריים, ולכן תנאי KKT מספיקים לאופטימום גלובלי.

נכתוב את האילוצים בצורת הקורס gᵢ(x,y,z)≤bᵢ:

המרווחים הם b₁-g₁=z-x-y ו-b₂-g₂=17.25-z. נסמן ב-λ₁≥0 וב-λ₂≥0 את הכופלים של האילוצים, בהתאמה. במקסימום, לפי מוסכמת הקורס, מוסיפים למטרה כל כופל כפול המרווח:

תנאי היציבות (סטציונריות) מתקבלים מגזירה לפי כל משתנה:

מאחר שמקדם z במטרה הוא -10, לכל x,y כדאי לבחור את z הקטן ביותר שמותר. לכן האילוץ הראשון פעיל:

נציב z=x+y במטרה. מתקבלת פונקציה בשני משתנים:

1. גוזרים לפי x ומשווים לאפס. ∂φ/∂x = -2x + 17 = 0   ⇒   x = 8.5
2. גוזרים לפי y ומשווים לאפס. ∂φ/∂y = -4y + 35 = 0   ⇒   y = 8.75
3. מחשבים את z ובודקים את האילוץ העליון. z = x+y = 8.5+8.75 = 17.25

כעת נמצא את הכופלים. מהמשוואה לפי x:

שני האילוצים פעילים, אך הכופל של האילוץ השני הוא אפס. תנאי הרפיון המשלים מתקיימים: λ₁(b₁-g₁)=0 ו-λ₂(b₂-g₂)=0. זוהי גם תזכורת לכך שאילוץ פעיל אינו מחייב כופל חיובי.

ערך המטרה:

תוצאת הסעיף: הפתרון האופטימלי הוא (x*,y*,z*)=(8.5,8.75,17.25), ערך המטרה המרבי הוא 225.375, והכופלים הם (λ₁,λ₂)=(10,0).

ד שינוי האילוץ ל-z ≤ 17.35

נוסח הסעיף: כיצד ישתנה ערך המטרה אם אגף ימין של האילוץ האחרון יגדל מ-17.25 ל-17.35?

הרעיון: במקסימום ובמוסכמת gᵢ≤bᵢ, שינוי קטן באגף ימין נותן ΔF*≈+λᵢΔbᵢ. כאן הכופל אפס, ואפשר גם לאמת שהפתרון הישן נשאר אופטימלי לאחר ההרפיה.

השינוי באגף ימין הוא:

הנקודה (8.5,8.75,17.25) עדיין אפשרית, וכעת יש לה מרווח 17.35-17.25=0.10 באילוץ השני. עם λ₂=0 היא עדיין מקיימת את כל תנאי KKT, ולכן נשארת אופטימלית.

תוצאת הסעיף: ערך פונקציית המטרה אינו משתנה ונשאר 225.375.