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