אופטימיזציה (מתמטיקה) – הבדלי גרסאות

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

 

 

==שיטות חישוביות==

 

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

*הרחבות של אלגוריתם הסימפלקס לפתרון בעיות תכנון ריבועי

* אלגוריתמי אופטימיזציה המיועדים לפתרון [[רשת זרימה|בעיות זרימה]]

{{הפניה לערך מורחב|שיטה איטרטיבית}}

 

 

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