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

לכן הצורה הסטנדרטית של בעיית אופטימיזציה היא:<ref>{{הערה|{{צ-ספר|מחבר=J. Nocedal, S. J. Wright|שם=Numerical Optimization|מקום הוצאה=New York|מו"ל=Springer|שנת הוצאה=|עמ=3|ISBN=978-0-387-30303-1|קישור=https://link.springer.com/book/10.1007/978-0-387-40065-5}}</ref>|שמאל=כן}}

כבר במאה ה-17 הוכיח [[פייר דה פרמה|פרמה]] את [[משפט פרמה (לנקודות קיצון)|משפט פרמה]] לזיהוי נקודות קיצון על ידי נגזרות. [[ז'וזף-לואי לגראנז'|לגראנז']] הציג את [[כופלי לגראנז']], שנועדו לאפשר מציאת [[נקודת קיצון|נקודות קיצון]] מקומיות של הפונקציה בכפוף לאילוצים. [[אייזק ניוטון|ניוטון]] ו[[קרל פרידריך גאוס|גאוס]] היו הראשונים להציג [[שיטה איטרטיבית|שיטות איטרטיביות]] שמתכנסות לעבר המינימום. ניוטון הציג זאת על ידי הכללה של [[שיטת ניוטון-רפסון|שיטת ניוטון רפסון]], וגאוס על ידי [[אלגוריתם גאוס-ניוטון]], שהוא למעשה תיקון של השיטה הקודמת.<ref name{{הערה|שם=":0">היסטוריה|{{cite book|title=Encyclopedia of Optimization|last=Du|first=D. Z.|last2=Pardalos|first2=P. M.|last3=Wu|first3=W.|publisher=Springer|year=2008|editor-last=Floudas|editor-first=C.|location=Boston|pages=1538–1542|chapter=History of Optimization|editor2-last=Pardalos|editor2-first=P.|chapterurl=}}</ref>|שמאל=כן}}

ב[[שנות ה-30 של המאה ה-20]] פיתח [[לאוניד קנטורוביץ']] את [[תכנון ליניארי|התכנון הליניארי]], וב[[שנות ה-40 של המאה ה-20|שנות ה-40]] פיתח [[ג'ורג' דנציג]] את [[שיטת הסימפלקס]]. ב[[שנות ה-50 של המאה ה-20|שנות ה-50]] פיתח [[ריצ'רד בלמן]] את [[משוואות בלמן]] למציאת אופטימליות בבעיות בקרה, ואת [[אלגוריתם בלמן-פורד]] למציאת המסלול הקל ביותר מצומת מסוים לכל שאר הצמתים בגרף. באותה תקופה פרסם [[רוברט פלויד]] את [[אלגוריתם פלויד-וורשאל]] ו[[אדסחר דייקסטרה|דייקסטרה]] פיתח את [[אלגוריתם דייקסטרה]].<ref name{{הערה|שם=":0" />היסטוריה}}

מחלקת בעיות NP באופטימיזציה (ידועה גם כמחלקת סיבוכיות NPO) ניתנת לחלוקה לסוגי הבעיות הבאות:<ref>{{הערה|{{צ-ספר|מחבר=Juraj Hromkovič|שם=Algorithmics for Hard Problems|מו"ל=Springer|שנת הוצאה=2004|ISBN=978-3-540-44134-2|מהדורה=2}}</ref>|שמאל=כן}}

* בעיות במחלקת [[סכמת קירוב פולינומית#סכמת קירוב פולינומית מלאה|סכמת קירוב פולינומית מלאה]] (FPTAS), כלומר ניתן למצוא לבעיות האלו פתרון מקורב ככל שנרצה על ידי [[אלגוריתם קירוב]] שסיבוכיותו פולינומית גם בגודל הקלט וגם ב-<math>1/\varepsilon</math> (כלומר אם <math>OPT</math> הוא גודל או עלות הפתרון האופטימלי עבור קלט זה, האלגוריתם מחזיר תשובה שהיא לפחות <math>(1-\varepsilon)*OPT</math> עבור בעיית מציאת מקסימום או קטנה מ-<math>(1+\varepsilon)*OPT</math> בעבור בעיית מציאת מינימום, בזמן פולינומי גם בגודל הקלט וגם ב-<math>1/\varepsilon</math>). לדוגמה המחלקה מכילה את [[בעיית תרמיל הגב]].{{הערה|Katherine Lai,[http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf The Knapsack Problem and Fully Polynomial Time Approximation Schemes (FPTAS)]2006|שמאל=כן}}

*בעיות במחלקת [[APX]], כלומר ניתן למצוא פתרון מקורב על ידי [[אלגוריתם קירוב]] בסיבוכיות פולינומית. לדוגמה המחלקה מכילה את [[בעיית הספיקות#בעיות אופטימיזציה נגזרות|בעיית הספיקות המרבית]] שאינה מוכלת ב-[[PTAS]].{{הערה|J. Håstad, '''[http://citeseer.ist.psu.edu/506917.html Some optimal inapproximability results]''', Proc. 28th Annual ACM Symp. on Theory of Computing (1997), El Paso, Texas, pp. 1-10|שמאל=כן}}