אופטימיזציה קמורה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

אלגוריתמים לאופטימיזציה קמורה[עריכת קוד מקור | עריכה]

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא אופטימיזציה קמורה בוויקישיתוף
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.