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

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

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

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

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

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

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

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

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