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

