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

איך מזהים שהנושא מתאים

• מבקשים למצוא נקודת קיצון של פונקציה לא ליניארית ללא אילוצים באמצעות נגזרות, גרדיאנט או הסיאן.
• מבקשים לקבוע אם פונקציה קמורה או קעורה.
• יש אילוצי שוויון בלבד, ולכן משתמשים בשיטת כופלי לגראנז'.
• יש אילוצי אי־שוויון, עם או בלי אילוצי אי־שליליות, ולכן משתמשים בתנאי KKT.
• מבקשים לאמוד כיצד שינוי קטן באגף ימין של אילוץ ישפיע על ערך המטרה האופטימלי.

אינטואיציה

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

אילוץ שוויון מגביל את התנועה למשטח מסוים. כופל לגראנז' מאזן בין שיפוע פונקציית המטרה לשיפוע האילוץ, כך שלא נשאר כיוון שיפור המותר על המשטח.

באילוצי אי־שוויון לא כל אילוץ חייב להשפיע על הפתרון. תנאי KKT מחברים בין שתי אפשרויות: אילוץ עם מרווח חיובי חייב לקבל כופל אפס; כופל חיובי מחייב שהאילוץ יהיה פעיל.

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

הגדרות פורמליות

נקודת קיצון ונקודה יציבה

נקודה x̄ היא מקסימום מקומי אם בסביבה קרובה שלה מתקיים f(x̄) ≥ f(x), ומינימום מקומי אם מתקיים f(x̄) ≤ f(x). בקיצון גלובלי ההשוואה נכונה לכל נקודה בתחום.

אם x̄ היא נקודת פנים והפונקציה גזירה, תנאי הכרחי לקיצון הוא שהנקודה תהיה יציבה:

f היא הפונקציה, x הוא המשתנה ו-x̄ היא הנקודה הנבדקת. התנאי הכרחי אך אינו מספיק: גם נקודת פיתול יכולה לקיים אותו.

סיווג במשתנה אחד

אם כל הנגזרות עד סדר r-1 מתאפסות בנקודה והנגזרת הראשונה שאינה אפס היא f⁽ʳ⁾(x̄), אז:

• אם r זוגי והנגזרת חיובית, מתקבל מינימום מקומי.
• אם r זוגי והנגזרת שלילית, מתקבל מקסימום מקומי.
• אם r אי־זוגי, הנקודה אינה נקודת קיצון; בדרך כלל זו נקודת פיתול.

r הוא סדר הנגזרת הראשונה שאינה מתאפסת בנקודה, ו-f⁽ʳ⁾ היא הנגזרת מסדר זה.

כמה משתנים: גרדיאנט והסיאן

נסמן X=(x₁,…,xₙ). הגרדיאנט הוא וקטור כל הנגזרות החלקיות מסדר ראשון:

n הוא מספר המשתנים, xⱼ הוא המשתנה שמספרו j, X̄ היא הנקודה הנבדקת, ו-∇f הוא הגרדיאנט. השורה השנייה היא התנאי ההכרחי לנקודת קיצון פנימית וגזירה.

מטריצת הסיאן H(X) מכילה את כל הנגזרות השניות. בנקודה יציבה:

לפי מבחן המינורים המובילים, H חיובית מוגדרת אם Dₖ>0 לכל k; היא שלילית מוגדרת אם הסימנים מתחלפים, כלומר (-1)ᵏDₖ>0 לכל k. הסימון Dₖ הוא הדטרמיננטה של תת־המטריצה הראשית המובילה בגודל k×k.

קמירות וקעירות

תהי f פונקציה המוגדרת על תחום קמור D. לכל u,v∈D ולכל t∈[0,1]:

אם האי־שוויון מתקיים, f קמורה. אם הכיוון הפוך, היא קעורה. u,v הן שתי נקודות בתחום, t הוא משקל, ו-tu+(1-t)v היא נקודה על הקטע המחבר ביניהן.

במשתנה אחד, f″(x)≥0 בכל התחום מעיד על קמירות ו-f″(x)≤0 על קעירות. בכמה משתנים, הסיאן חיובית למחצה בכל התחום מעידה על קמירות ושלילית למחצה על קעירות.

אם פונקציה קמורה, כל מינימום מקומי שלה הוא גם מינימום גלובלי. אם היא קעורה, כל מקסימום מקומי שלה הוא גם מקסימום גלובלי.

פעולות על פונקציות קמורות

• סכום של פונקציות קמורות הוא קמור.
• כפל פונקציה קמורה בקבוע a≥0 שומר על קמירות.
• כפל בקבוע שלילי הופך פונקציה קמורה לפונקציה קעורה.
• מכפלה של שתי פונקציות קמורות אינה מקבלת סיווג אוטומטי; בודקים את המכפלה עצמה.

הסיבה שסכום שומר על קמירות היא שאפשר לחבר את שני אי־שוויונות הקמירות. אם f ו-g קמורות על אותו תחום קמור, אז לכל u,v בתחום ולכל t∈[0,1]:

השורה האחרונה היא בדיוק הגדרת הקמירות עבור f+g.

לגראנז' ותנאי KKT לפי מוסכמת הקורס

נסמן X=(x₁,…,xₙ). הסימון i=1,…,m מונה אילוצים פונקציונליים, והסימון j=1,…,n מונה משתנים.

אילוצי שוויון

לבעיה עם אילוצים gᵢ(X)=bᵢ בונים:

f היא פונקציית המטרה, gᵢ הוא אגף שמאל של אילוץ i, bᵢ הוא אגף ימין שלו, ו-λᵢ הוא כופל לגראנז' של האילוץ. באילוץ שוויון אין דרישת סימן על λᵢ.

אם f קמורה במינימום או קעורה במקסימום, וכל אילוצי השוויון ליניאריים, פתרון משוואות הלגראנז' הוא אופטימום גלובלי.

אילוצי אי־שוויון פונקציונליים

תחילה מסדרים כל אילוץ לצורת הקורס gᵢ(X)≤bᵢ. אילוץ מהצורה gᵢ(X)≥bᵢ מוכפל ב--1. אילוץ שוויון יכול להיכתב כשני אילוצי אי־שוויון הפוכים, אך כאשר יש רק שוויונות נוח יותר להשתמש ישירות בשיטת לגראנז'.

הביטוי bᵢ-gᵢ(X) הוא המרווח של אילוץ i. הסימון λᵢ הוא הכופל שלו.

מרפיון משלים נובעות שתי מסקנות שימושיות: אם λᵢ>0, אז האילוץ פעיל ולכן gᵢ(X)=bᵢ; אם המרווח חיובי, אז λᵢ=0. הכיוון ההפוך אינו מובטח: אילוץ פעיל יכול לקבל כופל אפס.

הוספת אילוצי אי־שליליות

כאשר הבעיה כוללת במפורש xⱼ≥0, מצמידים לכל אילוץ כזה כופל μⱼ≥0:

μⱼ הוא הכופל של אילוץ האי־שליליות על משתנה xⱼ. בנוסף לתנאי KKT של האילוצים הפונקציונליים, כותבים את תנאי היציבות לפי הלגראנז' המורחב ואת שלושת התנאים שבשורה האחרונה לכל j.

מתי התנאים גם מספיקים?

• במקסימום: f קעורה וכל gᵢ קמורה.
• במינימום: f קמורה וכל gᵢ קמורה.
• באילוצי שוויון: פונקציות האילוץ ליניאריות.

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

משמעות הכופלים בשינוי קטן באגף ימין

f* הוא ערך המטרה האופטימלי, Δbᵢ הוא השינוי באגף ימין של אילוץ i, ו-Δf* הוא השינוי המשוער בערך האופטימלי. זהו קירוב מקומי בלבד, כל עוד מבנה הפתרון אינו משתנה.

אם מחליפים אילוץ אי־שליליות ב-xⱼ≥rⱼ ומגדילים את הגבול התחתון ב-Δrⱼ, מתקבל בקירוב Δf*≈-μⱼΔrⱼ במקסימום ו-Δf*≈+μⱼΔrⱼ במינימום. הגדלת גבול תחתון מצמצמת את התחום האפשרי, ולכן כיוון ההשפעה הפוך מהרפיית אילוץ ≤.

שיטת פתרון

1. מסווגים את הבעיה: ללא אילוצים, שוויון בלבד, אי־שוויון, או אי־שוויון יחד עם אי־שליליות.
2. בודקים את המבנה: קובעים קמירות במינימום או קעירות במקסימום באמצעות נגזרות או הסיאן.
3. ללא אילוצים: פותרים f′(x)=0 או ∇f(X)=0, מסווגים כל נקודה יציבה, ומשווים גם נקודות קצה אם התחום סגור.
4. עם אילוצי שוויון: בונים L=f+Σλᵢ(bᵢ-gᵢ), פותרים את תנאי היציבות ואת האילוצים יחד, ואז מאמתים את התנאי המספיק.
5. עם אילוצי אי־שוויון: מסדרים את כולם כ-gᵢ≤bᵢ, בוחרים את סימן הלגראנז' לפי מקסימום או מינימום, וכותבים את כל משפחות KKT.
6. עם אי־שליליות: מוסיפים את כופלי μⱼ ואת התנאים μⱼxⱼ=0, μⱼ≥0, xⱼ≥0.
7. פותרים מצבי פעילות: לכל אילוץ בודקים אם המרווח אפס או הכופל אפס. פוסלים מצב מיד אם הוא מפר אפשריות או סימן כופל.
8. מאמתים ומסכמים: מציבים בכל האילוצים, בודקים את התנאי המספיק, מחשבים את ערך המטרה ומדווחים אם האופטימום מקומי או גלובלי.
9. מנתחים שינוי: משתמשים בכופל ובסימן המתאים רק לשינוי קטן שבמהלכו מבנה הפתרון נשאר תקף.

הערות מוכנות למבחן