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

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

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

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

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

תוכן עניינים

שיטות חישוביותעריכה

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

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

אלגוריתמי אופטימיזציהעריכה

שיטות איטרטיביותעריכה

  ערך מורחב – שיטה איטרטיבית

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

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

קישורים חיצונייםעריכה

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