אופטימיזציה קמורה
קפיצה לניווט
קפיצה לחיפוש
אופטימיזציה קמורה היא תת-תחום של אופטימיזציה מתמטית, המטפלת במקרה שבו פונקציית המטרה היא פונקציה קמורה והאילוצים מגדירים מרחב שהוא קבוצה קמורה. למרות שמדובר במשפחה רחבה מאד של בעיות, קיימים אלגוריתמים כלליים לפתרון יעיל של בעיות קמורות, ולכן לתחום של אופטימיזציה קמורה יש שימושים רבים בתחומים מגוונים. אופטימיזציה קמורה כוללת בתוכה בעיות שהן "קלות" יותר לפתרון - לדוגמה כל מינימום לוקלי של הפונקציה חייב להיות המינימום הגלובלי. כך, כאשר אנחנו רוצים לפתור בעיות אופטימיזציה, מובטח לנו שנתכנס לפתרון הכי טוב.
אלגוריתמים לאופטימיזציה קמורה
ישנם מספר אלגוריתמים שמטפלים בבעיות של אופטימיזציה קמורה. מרביתם מתבססים על קירוב לפתרון עד כדי אפסילון נתון. בין האלגוריתמים:
- האלגוריתם של Cimmino - האלגוריתם מוצא נקודה משותפת בחיתוך של הקבוצות הקמורות. האלגוריתם מתבסס על חישוב היטלים ולקיחת ממוצעים. זהו אלגוריתם איטרטיבי. אלגוריתם זה נועד לתת פתרון בזמן אמת ומשתמשים בו בעיקר למציאת תת-אופטימום.
- אלגוריתם פרנק-וולף (Frank-Wolfe) - אלגוריתם זה עובד רק על בעיות אופטימיזציה קמורות כאשר האילוצים הם לינאריים ופונקציית המטרה לא לינארית אבל קמורה. באלגוריתם פרנק-וולף דורשים שפונקציית המטרה תהיה גזירה. למעשה, אלגוריתם זה יוצר סדרת בעיות של תכנון לינארי, כאשר לוקחים קירוב ראשון בפיתוח טיילור של פונקציית המטרה (קירוב לינארי של הפונקציה) מה שמוביל לבעיית תכנון לינארי.
