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