הצגת המקור של הדף "אופטימיזציה (מתמטיקה)"

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

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

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

==הצורה הסטנדרטית==
הצורה הסטנדרטית של בעיית אופטימיזציה היא:{{הערה|{{צ-ספר|מחבר=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}}|כיוון=שמאל}}

: החזר את <math>\mathbf{x}</math> שממזער את <math>f(\mathbf{x})</math>

ומקיים את האילוצים:
{|
!<math>i \in \mathcal{I}</math>
!<math>c_{i}(\mathbf{x})\geq0</math>
|-
|<math>i \in \mathcal{E}</math>
|<math>c_{i}(\mathbf{x})=0</math>
|}
כאשר:
* <math>\, f\, :\, \mathbb{R}^{n} \rightarrow \mathbb{R}</math> היא פונקציית העלות שצריך למזער.
*<math>\mathcal {I}</math> היא קבוצת אי השוויונים, שמגדירה אילוצים על תחום הפונקציה.
*<math>\mathcal {E}</math> היא קבוצת שוויונים, שמגדירה אילוצים על תחום הפונקציה.
<math>\mathcal {I}</math> ו-<math>\mathcal {E}</math> ביחד נקראות האילוצים (לפעמים גם ההגבלות) של הבעיה.

כאשר <math>\mathcal {I} = \mathcal {E} = \emptyset</math>, הבעיה נקראת בעיית אופטימיזציה לא מאולצת, כלומר זוהי בעיה של מציאת מינימום גלובלי של הפונקציה <math>\, f\,</math> במרחב <math>\mathbb{R}^{n}</math>.

כאשר הבעיה היא בעיה של מציאת מקסימום (לדוגמה [[בעיית תרמיל הגב]], שבה נדרש למקסם את שווי המחיר של העצמים בתיק), נוכל להפוך אותה לבעיית מציאת מינימום על ידי החלפת פונקציית העלות <math>f(\mathbf{x})</math> בפונקציה <math>\tilde{f}\left(\mathbf{x}\right)</math> כך:

:<math>\tilde{f}\left(\mathbf{x}\right) := - f\left(\mathbf{x}\right),\, \tilde{f}\, :\, A \rightarrow \mathbb{R}</math>

אזי השוויון הבא יתקיים לכל <math>{x}</math> עצמים בתיק ו- <math>{x_0}</math> עצמים בתיק ששווי מחירם מקסימלי:

: <math>f\left(\mathbf{x}_{0}\right)\geq f\left(\mathbf{x}\right) \Leftrightarrow \tilde{f}\left(\mathbf{x}_{0}\right)\leq \tilde{f}\left(\mathbf{x}\right)</math>

ולכן כל נקודת מקסימום של הפונקציה <math>f</math> היא נקודת מינימום של הפונקציה <math>\bar{f}</math>, ולכן מציאת מינימום של הפונקציה <math>\bar{f}</math> שקולה למציאת מקסימום של הפונקציה <math>f</math>.

==היסטוריה==
כבר במאה ה-17 הוכיח [[פייר דה פרמה|פרמה]] את [[משפט פרמה (לנקודות קיצון)|משפט פרמה]] לזיהוי נקודות קיצון באמצעות נגזרות. [[ז'וזף-לואי לגראנז'|לגראנז']] הציג את [[כופלי לגראנז']], שנועדו לאפשר מציאת [[נקודת קיצון|נקודות קיצון]] מקומיות של פונקציה תחת אילוצים. [[אייזק ניוטון|ניוטון]] ו[[קרל פרידריך גאוס|גאוס]] היו הראשונים להציג [[שיטה איטרטיבית|שיטות איטרטיביות]] שמתכנסות לעבר המינימום. ניוטון הציג שיטה כזו באמצעות הכללה של [[שיטת ניוטון-רפסון]] וגאוס הציג את [[אלגוריתם גאוס-ניוטון]], שהוא למעשה תיקון של ההכללה שניוטון עשה קודם לכן לשיטת ניוטון-רפסון.{{הערה|שם=היסטוריה|{{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.}}|כיוון=שמאל}}

ב[[שנות ה-30 של המאה ה-20]] פיתח [[לאוניד קנטורוביץ']] את [[תכנון ליניארי|התכנון הליניארי]], וב[[שנות ה-40 של המאה ה-20|שנות ה-40]] פיתח [[ג'ורג' דנציג]] את [[שיטת הסימפלקס]]. ב[[שנות ה-50 של המאה ה-20|שנות ה-50]] פיתח [[ריצ'רד בלמן]] את [[משוואות בלמן]] למציאת פתרונות אופטימליים בבעיות בקרה ואת [[אלגוריתם בלמן-פורד]] למציאת מסלולים בעלי משקל מינימלי בגרף (מצומת מסוים בו לכל שאר הצמתים באותו גרף). באותה תקופה פרסם [[רוברט פלויד]] את [[אלגוריתם פלויד-וורשאל]] ו[[אדסחר דייקסטרה|דייקסטרה]] פיתח את [[אלגוריתם דייקסטרה]].{{הערה|שם=היסטוריה}}

==שיטות חישוביות==
[[קובץ:Newton optimization vs grad descent.svg|ממוזער|תרשים של אופטימיזציה איטרטיבית באמצעות [[Gradient descent]] (בירוק), ובאמצעות הרחבת שיטת ניוטון-רפסון לאופטימיזציה (באדום).]]
קיימים [[אלגוריתם|אלגוריתמים]] שונים לפתרון בעיות אופטימיזציה, חלקם מסתיימים לאחר מספר סופי של צעדים, חלקם מבוססים על [[שיטה איטרטיבית|שיטות איטרטיביות]] המתכנסות לפתרון וישנם אלגוריתמים שמבוססים על [[היוריסטיקה]] שעשוים לתת קירוב לפתרון לבעיה (אך לא מובטחת בהם התכנסות לפתרון).

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

===שיטות אופטימיזציה איטרטיביות===
[[קובץ:Frank-Wolfe Algorithm.png|ממוזער|שלב ב[[אלגוריתם פרנק-וולף]]]]
{{ערך מורחב|שיטה איטרטיבית}}
==== אופטימיזציה רציפה ====
שיטות איטרטיביות נפוצות לפתרון בעיות [[תכנון לא-ליניארי]], וניתן לסווג אותן על פי התבססותן על ערך הפונקציה בלבד, על ה[[גרדיאנט]] של הפונקציה או על ה[[הסיאן]] שלה. שיטות המבוססות על הגרדיאנט או על הסיאן עשויות להתכנס מהר יותר עבור פונקציות שיש להן כאלו, אך לעיתים החישוב שלהם מורכב חישובית.

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

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

====אופטימיזציה בדידה====
בין השיטות האיטרטיביות באופטימיזציה בדידה נוכל למצוא את אלגוריתם [[חיפוש מקומי]] שבכל איטרציה בוחר את האפשרות הטובה ביותר להתקדם מהמצב הנוכחי עד להגעה למצב שטוב יותר מכל שכניו (כלומר אין למצב שכנים טובים ממנו). אלגוריתמים כאלו יכולים לפתור לדוגמה הרחבה של [[חידת שמונה המלכות|חידת 8 המלכות]] בעבור <math>n</math> מלכות.

===שיטות אופטימיזציה היוריסטיות===
בין השיטות שמשתמשות ב[[היוריסטיקה]] באופטימיזציה בדידה נוכל למצוא את [[אלגוריתם חיפוש A*|חיפוש A*]] לחיפוש בגרף ובאופטימיזציה רציפה נוכל למצוא את אלגוריתם [[חיפוש מקומי#אלגוריתם hill-climbing|Hill-Climbing]].

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

==תחומים עיקריים==
*[[אופטימיזציה קמורה]], מטפלת במקרה שבו פונקציית המטרה היא [[פונקציה קמורה]] והאילוצים מגדירים מרחב [[קבוצה קמורה|קמור]]. באופטימיזציה קמורה כל מינימום מקומי של הפונקציה חייב להיות המינימום הגלובלי, ולכן באלגוריתמים איטרטיבים מובטחת ההתכנסות (שכן לא קיימת האפשרות של היתקעות במינימום מקומי ללא יכולת להשתפר).
*[[תכנון ליניארי]], תת-תחום של אופטימיזציה קמורה. כאשר פונקציית העלות היא ליניארית, והאילוצים הם שוויונים ואי שוויונים ליניארים.
*[[תכנון ליניארי בשלמים]], הבעיה היא בעיית תכנון ליניארי כאשר הפתרונות חייבים להיות שלמים. תת-תחום של אופטימיזציה בדידה.
*[[תכנון ליניארי בשברים]], הכללה של תכנון ליניארי כאשר [[פונקציית הפסד|פונקציית ההפסד]] היא מנה של שתי פונקציות ליניאריות.
*[[תכנון בשברים]], הכללה של תכנון ליניארי בשברים כאשר פונקציית ההפסד היא מנה של שתי פונקציות (שבדרך כלל לא ליניאריות).
*[[תכנון לא-ליניארי]], פותרת מערכת [[משוואה|משוואות]] ו[[אי-שוויון (מתמטיקה)|אי-שוויונות]] כאשר לפחות אחד מהאילוצים ומפונקציית המטרה אינם [[משוואה ליניארית|ליניארים]].
*[[אופטימיזציה קומבינטורית]], כאשר מרחב הפתרונות הוא בדיד או ניתן להפוך אותו לבדיד. לדוגמה, מציאת [[עץ פורש מינימלי]] בגרף.
*[[אופטימיזציה סטוכסטית]], משתמשת במשתנים רנדומליים או במדידות רנדומליות במהלך החיפוש.
*[[חשבון וריאציות]], מציאת נקודות קיצון של [[פונקציונל]]ים.
*[[בקרה אופטימלית]], מציאת חוקי בקרה, שביצועיהם מביאים למקסימום או מינימום [[אינדקס ביצועים]] כלשהו.
*[[אופטימיזציה הרמונית]], משמשת בעיקר בשלב העיבוד המקדים בלמידת מכונה.

== שימושים ==
=== כלכלה ===
====מיקרו-כלכלה====
הניתוח הבסיסי של [[מיקרו-כלכלה]] מתבסס על הנחות [[תחרות משוכללת|התחרות המשוכללת]], שבה אחת מהנחות היסוד היא התנהגות רציונלית של המוכרים והקונים. כלומר מניחים שמטרת הקונים היא למקסם את [[פונקציית תועלת|התועלת]] שלהם, בעוד ש[[חברה (תאגיד)|חברות]] והמוכרים ינסו למקסם את ה[[רווח (כלכלה)|רווח]] שלהן. בהתקיים הנחות אלו, על פי [[כלכלה נאו-קלאסית|הכלכלה הנאו-קלאסית]], השוק יתנהל לפי חוקי [[היצע וביקוש|הביקוש וההיצע]], וישאף להגיע לשיווי משקל ול[[יעילות פארטו]] באמצעות מנגנון "[[היד הנעלמה]]". תחת הנחות אלו אפשר להפעיל שיטות אופטימיזציה כדי לחזות את התנהגות השחקנים בשוק. בעקבות התפתחות הענף של [[כלכלה התנהגותית]] שמצביע על כך שהשחקנים פועלים עם [[רציונליות מוגבלת]] ו[[הטיה קוגניטיבית|הטיות קוגניטיביות]], כלכלנים פיתחו מודלים של אופטימיזציה סטוכסטית שמתבססים על תאוריית תוחלת התועלת של [[ג'ון פון נוימן]] ו[[אוסקר מורגנשטרן]], ועל כלים מ[[תורת המשחקים]] שמסוגלים להגיע לתוצאות אופטימליות תוך התחשבות בתנאי אי ודאות.{{הערה|{{cite journal |first=Robert |last=Dorfman |title=An Economic Interpretation of Optimal Control Theory |journal=[[American Economic Review]] |volume=59 |issue=5 |year=1969 |pages=817–831 |jstor=1810679 }}|כיוון=שמאל}}{{הערה|A.G. Malliaris (2008). "stochastic optimal control," ''The New Palgrave Dictionary of Economics'', 2nd Edition. {{ISBN|978-1-349-95121-5}}|כיוון=שמאל}}
בעיות רבות במיקרו-כלכלה הן בעיות אופטימיזציה, לדוגמה: [[בעיית מיקסום התועלת]] {{אנ|Utility maximization problem}} (כיצד הקונה יכול למקסם את התועלת שלו) היא בעיית אופטימיזציה.

====מקרו-כלכלה====
ב[[מקרו-כלכלה]] כלכלנים משתמשים במודלים של אופטימיזציה סטוכסטית כדי לתאר את תנודות השוק כתוצאה מהחלטות אופטימליות של צרכנים, מוכרים, חברות וממשלות.{{הערה|Rotemberg J. Woodford M. (1997) [https://www.nber.org/chapters/c11041.pdf An Optimization-Based Econometric Framework for the Evaluation of Monetary Policy] '''12''' "NBER Macroeconomics Annual": 297–346. {{doi|10.2307/3585236}}|כיוון=שמאל}}
===חקר ביצועים===
בחקר ביצועים נעשה שימוש באלגוריתמי אופטימיזציה סטוכסטית כדי למדל קבלת החלטות בתנאי אי ודאות. לדוגמה, ב[[תורת ההחלטות]]. נעשה גם שימוש באלגוריתמי אופטימיזציה בדידה כדי למצוא את הדרך היעילה ביותר לנצל משאבים מוגבלים. לדוגמה, פיזור מיטבי של מוקשיים ימיים או תחנות מכ"ם.

=== הנדסה ===
[[קובץ:Abstract Math-Nonlinear Rescaling (3724051623).jpg|ממוזער|250px|מציאת ארכיטקטורת [[מסבך]] אופטימלית ביחס למחיר]]
תחומים רבים בהנדסה משתמשים בשיטות אופטימיזציה בתכנון העבודה:

==== הנדסת חשמל ====
בהנדסת חשמל, שיטות מתקדמות באופטימיזציה מסייעות לשלב בין מודלים פיזיקליים מורכבים שונים{{הערה|{{cite journal|title=Space mapping technique for electromagnetic optimization|last1=Bandler|first1=J.W.|last2=Biernacki|first2=R.M.|date=1994|journal=IEEE Transactions on Microwave Theory and Techniques|issue=12|doi=10.1109/22.339794|volume=42|pages=2536–2544|bibcode=1994ITMTT..42.2536B|last3=Chen|first3=Shao Hua|last4=Grobelny|first4=P.A.|last5=Hemmers|first5=R.H.}}|כיוון=שמאל}} (שילובים בין מודל מהיר ולא מדויק למודל איטי ומדויק כדי לקבל מודל מהיר ומדויק). אופטימיזציה משמשת גם ביצור רכיבים, בתכנון מעגלים חשמליים ובתכנון רשתות חשמל אופטימליות (כך שיוכל לעבור בהן זרם מקסימלי גם אם חלקים מהרשת אינם עובדים).

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

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

=== ביולוגיה ===
אופטימיזציה נמצאת בשימוש ב[[ביולוגיה מולקולרית]], [[ביולוגיה מתמטית]] (ובפרט בתתי התחומים שלה: [[ביואינפורמטיקה]] ו[[ביולוגיה מערכתית]]), [[הנדסת חילוף חומרים]] {{אנ|Metabolic engineering}} ו[[גנומיקה חישובית]].

שיטות אופטימיזציה נמצאות בשימוש ב[[מידול מערכות ביולוגיות]] {{אנ|Modelling biological systems}}, ובפרט ב[[ניבוי מבנה חלבון|ניבוי מבני חלבונים]] {{אנ|Protein structure prediction}} (לדוגמה שיטת [[Dead-end elimination]]). תכנון לא ליניארי בשילוב עם סימולציות של מערכות ביוכימיות נמצא בשימוש בחקר של חילופי חומרים.{{הערה|{{Cite journal|last1=Mendes|first1=P. Mendes|last2=Kell|first2=D.|date=1998|title=Non-linear optimization of biochemical pathways: applications to metabolic engineering and parameter estimation|journal=Bioinformatics|volume=14|issue=10|pages=869–883|issn=1367-4803|pmid=9927716|doi=10.1093/bioinformatics/14.10.869}}|כיוון=שמאל}} שיטות אופטימיציה סייעו גם ביצירת דגמים בחקר התא ובביולוגיה מולקולרית ובדינמיקה של אוכלוסיות (חיזוי התפתחות של זיהום ומחלות זיהומיות). ולבניית שרשראות מיקרוביולוגיות יעילות, שמשמשות לייצור בין היתר של דלקי מאובנים ותרופות.{{הערה|Kim, J. and J.L. Reed. 2010. OptORF: Optimal metabolic and regulatory perturbations for metabolic engineering of microbial strains. ''BMC Systems Biology'', '''4''':53.|כיוון=שמאל}}

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

שיטות אופטימיזציה משמשות גם בכל שלוש הפרדיגמות של [[למידת מכונה]].{{הערה|{{cite book |last1=Sra |first1= S |last2= Nowozin |first2= S |last3= Wright |first3= S. J |date= September 2011 |title= Optimization for Machine Learning |url= https://books.google.co.il/books?id=JPQx7s2L1A8C&pg=PA403&dq=%22Improving+First+and+Second-Order+Methods+by+Modeling+Uncertainty&redir_esc=y&hl=iw#v=onepage&q&f=false |isbn= 9780262537766 |pages=403–405}}|כיוון=שמאל}} אולם, יש הבדל בין התחומים שכן אופטימיזציה מנסה למזער את פונקציית ההפסד על הנתונים הידועים (נתוני האימון), ואילו למידת מכונה מנסה למזער את ההפסד גם על נתונים לא ידועים (עקרון ההכללה).

==== למידת מכונה מונחית ====
בעיות רבות בלמידה מונחית מוגדרות על ידי מזעור של פונקציית ההפסד. לדוגמה, [[מכונת וקטורים תומכים|מכונת וקטורים תומכת]] מנסה למצוא את [[מפריד ליניארי|המפריד הליניארי]] אשר יוצר מרווח גדול ככל האפשר בינו לבין הדוגמאות הקרובות לו ביותר, ב[[רגרסיה ליניארית]] פונקציית ההפסד היא [[שיטת הריבועים הפחותים]] והפתרון הוא הישר שממזער את פונקציית ההפסד.
==== למידת מכונה בלתי מונחית ====
אלגוריתמים מסוימים בלמידה בלתי מונחית משתמשים באופטימיזציה. לדוגמה, [[אלגוריתם מיקסום התוחלת]] מחשב את הפרמטרים כתוחלת לוג הנראות, [[T-SNE]] הוא אלגוריתם הורדת מימד שמשתמש ב-gradient descent כדי למזער את [[דיברגנץ קולבק-ליבלר]] של התפלגויות של הנקודות בממדים (גם במימד הגבוה וגם במימד הנמוך). קיים גם שימוש באופטימיזציה הרמונית כדי להוריד ממדים (מכיוון שאלגוריתמי אופטימיזציה הרמונית מטילים את מסד הנתונים על גבי מספר קטן של רכיבים).

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

==בעיות NP באופטימיזציה==
מחלקת בעיות NP באופטימיזציה (ידועה גם כמחלקת סיבוכיות NPO) ניתנת לחלוקה לסוגי הבעיות הבאות:{{הערה|{{צ-ספר|מחבר=Juraj Hromkovič|שם=Algorithmics for Hard Problems|מו"ל=Springer|שנת הוצאה=2004|ISBN=978-3-540-44134-2|מהדורה=2}}|כיוון=שמאל}}
* בעיות במחלקת [[סכמת קירוב פולינומית#סכמת קירוב פולינומית מלאה|סכמת קירוב פולינומית מלאה]] (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|כיוון=שמאל}}
* בעיות במחלקת [[סכמת קירוב פולינומית]] (PTAS), כלומר ניתן למצוא לבעיות האלו פתרון מקורב ככל שנרצה על ידי אלגוריתם קירוב בסיבוכיות פולינומית לגודל הקלט בהתייחס ל-<math>\varepsilon</math> כקבוע (מה שמאפשר שהאלגוריתם יהיה אקספוננציאלי ביחס ל-<math>1/\varepsilon</math>).
*בעיות במחלקת [[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, p. 1-10|כיוון=שמאל}}
* בעיות שניתן למצוא להן פתרון מקורב ב[[סיבוכיות]] שתהיה בסדר גודל פולינומי בלוגריתם של גודל הקלט. לדוגמה, ל[[בעיית כיסוי קבוצות|בעיית כיסוי הקבוצות]] ניתן למצוא באופן יעיל פתרון לבעיה הקרוב לאופטימום, בסיבוכיות שתהיה בסדר גודל פולינומי בלוגריתם של גודל הקבוצה שאותה רוצים לכסות.

==ראו גם==
* [[אופטימיזציה קמורה]]
*[[אופטימיזציה הרמונית]]
* [[תכנון ליניארי]]
* [[תכנון לא-ליניארי|תכנון לא ליניארי]]
* [[חשבון וריאציות]]

==לקריאה נוספת==
<div class="mw-content-ltr">
* Jorge Nocedal, Stephen J. Wright, [https://link.springer.com/book/10.1007/978-0-387-40065-5 Numerical Optimization] (Second Edition), Springer, 2006, {{ISBN|978-0-387-30303-1}}
* Panos Pardalos, Christodoulos A. Floudas, Encyclopedia of Optimization, Springer, 2009, {{ISBN|978-0-387-74759-0}}
</div>

==קישורים חיצוניים==
{{מיזמים|ויקימילון=אופטימיזציה}}
*{{MathWorld|OptimizationTheory}}
*{{אנציקלופדיה למתמטיקה|Mathematical_programming}}
*[https://theory.stanford.edu/~trevisan/books/cs261.pdf Combinatorial Optimization], [[אוניברסיטת סטנפורד]] {{אנגלית}}.
*[https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization], אוניברסיטת סטנפורד {{אנגלית}}.
*[https://neos-guide.org/content/optimization-introduction פירוט על תחומי אופטימיזציה] באתר neos-guide {{אנגלית}}.
* {{בריטניקה}}
* {{דף שער בספרייה הלאומית|987007538691105171|תכנות (מתמטיקה)}}

==הערות שוליים==
{{הערות שוליים|יישור = שמאל}}

{{בקרת זהויות}}

[[קטגוריה:אופטימיזציה מתמטית|*]]