אופטימיזציה (מתמטיקה) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הרחבה קלה מוויקיפדיה האנגלית |
|||
שורה 1:
[[קובץ:Max paraboloid.svg|ממוזער|גרף של פרבלואיד הנתון על ידי הפונקציה <math>z=f(x,y)= -(x^2+ y^2) + 4</math>. המקסימום הגלובלי נמצא בנקודה המסומנת בכחול <math>(x, y, z) = (0, 0, 4)</math>]]
'''אוֹפּטִימִיזַצְיָה''', או '''מִטּוּב''', היא ענף של בעיות [[מתמטיקה|מתמטיות]] העוסקות במציאת ערך אופטימלי עבור [[פונקציה|פונקציות]], תחת אילוצים נתונים. בעיות אופטימיזציה יכולות לעסוק בפונקציות המקבלות ערכים [[מספר ממשי|ממשיים]], או בפונקציות במספר משתנים ממשיים או [[מספר מרוכב|מרוכבים]], וכן גם בפונקציות המקבלות ערכים בדידים. התחום נמצא במרכז העיסוק של ענף [[חקר ביצועים]] ב[[מתמטיקה שימושית|מתמטיקה השימושית]].
שורה 6 ⟵ 7:
בעיות אופטימיזציה מיוחדות הן לדוגמה [[תכנון לינארי]] (כאשר פונקציית המטרה והאילוצים הם לינאריים), [[תכנון לא-לינארי]] (כאשר לפחות אחת מהפונקציות אינה לינארית), [[אופטימיזציה קמורה]], [[תכנות בשלמים]] ועוד.
==שיטות חישוביות==
[[קובץ:Gradient descent.svg|ממוזער|תרשים של אופטמיזציה איטרטיבית באמצעות [[Gradient descent]]. על פי הגרדיאנט נקבעת נקודת השערוך הבאה כשבכל שלב מתקדמים לנקודת האופטימום.]]
קיימים [[אלגוריתם|אלגוריתמים]] שונים לפתרון בעיות אופטימיזציה, שחלקם מסתיימים לאחר מספר סופי של צעדים וחלקם מבוססים על [[שיטה איטרטיבית|שיטות איטרטיביות]] המתכנסות לפתרון וכן שיטות מבוססות [[היוריסטיקה]] שעשויות לתת קירוב לפתרון לבעיה (אך לא מובטח שהן מתכנסות לפתרון).
===אלגוריתמי אופטימיזציה===
* [[אלגוריתם הסימפלקס]] - אלגוריתם המיועד לפתרון בעיות ב[[תכנון לינארי]] שפותח במקור על ידי [[ג'ורג' דנציג]].
*הרחבות של אלגוריתם הסימפלקס לפתרון בעיות תכנון ריבועי
* אלגוריתמי אופטימיזציה המיועדים לפתרון [[רשת זרימה|בעיות זרימה]]
* אלגוריתמים קומבינטוריים
===שיטות איטרטיביות===
{{הפניה לערך מורחב|שיטה איטרטיבית}}
שיטות איטרטיביות נפוצות לפתרון בעיות [[תכנון לא-לינארי]], וניתן לסווג אותן על פי התבססותן על ערך הפונקציה בלבד, על ה[[גרדיאנט]] של הפונקציה או על [[הסיאן]] שלה. שיטות המבוססות על הגרדיאנט או על הסיאן עשויות להתכנס מהר יותר עבור פונקציות שיש להן כאלו, אך לעתים החישוב של שלהם מורכב חישובית.
אחת מאמות המידה החשובות בהקשר של שיטות איטרטיביות הוא מספר הפעמים שנדרשים לשערך את ערך הפונקציה, שכן שערוך הפונקציה עשוי להיות יקר. עבור פונקציה בעלת N משתנים, שערוך של הנגזרת עשוי להיות כרוך ב-N+1 שערוכים של הפונקציה, ואילו שערוך של הנגזרת השנייה (לצורך מטריצת ההסיאן) עשוי להיות כרוך בסדר גודל של <math>N^2</math> שערוכים של הפונקציה. לדוגמה [[שיטת ניוטון]] המתבססת על נגזרת שנייה מצריכה בכל איטרציה לשערך את הפונקציה בסדר גודל של <math>N^2</math> פעמים, ולעומתה שיטה המתבססת על הגרדיאנט בלבד מצריכה סדר גודל של N שערוכים של הפונקציה. יחד עם זאת, שיטות מבוססות גרדיאנט ידרשו לרוב יותר איטרציות עד להתכנסות.
==קישורים חיצוניים==
{{מיזמים|ויקימילון=אופטימיזציה}}
| |||