אופטימיזציה (מתמטיקה)

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

אוֹפּטִימִיזַצְיָה, או מִטּוּב, היא ענף של בעיות מתמטיות העוסקות במציאת ערך אופטימלי עבור פונקציות, תחת אילוצים נתונים. בעיות אופטימיזציה יכולות לעסוק בפונקציות המקבלות ערכים ממשיים, או בפונקציות במספר משתנים ממשיים או מרוכבים, וכן גם בפונקציות המקבלות ערכים בדידים. התחום נמצא במרכז העיסוק של ענף חקר ביצועים במתמטיקה השימושית.

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

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

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

שיטות חישוביות[עריכת קוד מקור | עריכה]

תרשים של אופטמיזציה איטרטיבית באמצעות Gradient descent. על פי הגרדיאנט נקבעת נקודת השערוך הבאה כשבכל שלב מתקדמים לנקודת האופטימום.

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

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

שיטות איטרטיביות[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – שיטה איטרטיבית

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

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

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

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