אופטימיזציה (מתמטיקה)

מתוך ויקיפדיה, האנציקלופדיה החופשית
גרף של פרבולואיד הנתון על ידי הפונקציה . המקסימום הגלובלי נמצא בנקודה המסומנת בכחול

אוֹפּטִימִיזַצְיָה מתמטית, או מִטּוּב, הוא תת-תחום במתמטיקה שימושית שעוסק במציאת הערך האופטימלי של פונקציה תחת מגבלות אילוצים נתונות. בעיות אופטימיזציה מופיעות בתחומים רבים כגון: מדעי המחשב, הנדסה, חקר ביצועים וכלכלה.

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

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

הצורה הסטנדרטית[עריכת קוד מקור | עריכה]

כל בעיית מציאת מקסימום ניתן להמיר לבעיית מציאת מינימום, כיוון שאם נבחר פונקציה חדשה כך:

אזי יתקיים השוויון הבא:

ולכן כל נקודת מקסימום של הפונקציה היא נקודת מינימום של הפונקציה , ומכך נקבל שהבעיה של מציאת מינימום של הפונקציה שקולה למציאת מקסימום של הפונקציה .

לכן הצורה הסטנדרטית של בעיית אופטימיזציה היא:[1]

החזר את שממזער את

ומקיים את האילוצים:

כאשר:

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

ו- ביחד נקראות האילוצים (לפעמים גם ההגבלות) של הבעיה.

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

כאשר הבעיה היא בעיה של מציאת מקסימום (לדוגמה בעיית תרמיל הגב, שבה נדרש למקסם את שווי המחיר של העצמים בתיק), נוכל להפוך אותה לבעיית מציאת מינימום על ידי החלפת פונקציית העלות בפונקציה כמתואר לעיל.

היסטוריה[עריכת קוד מקור | עריכה]

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

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

שיטות חישוביות[עריכת קוד מקור | עריכה]

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

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

שיטות אופטימיזציה ישירות[עריכת קוד מקור | עריכה]

שיטות אופטימיזציה איטרטיביות[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – שיטה איטרטיבית

אופטימיזציה רציפה[עריכת קוד מקור | עריכה]

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

אחת מאמות המידה החשובות בהקשר של שיטות איטרטיביות הוא מספר הפעמים שנדרשים לשערך את ערך הפונקציה, שכן שערוך הפונקציה עשוי להיות יקר. עבור פונקציה בעלת N משתנים, שערוך של הנגזרת עשוי להיות כרוך בלפחות שערוכים של הפונקציה, ואילו שערוך של הנגזרת השנייה (לצורך מטריצת ההסיאן) עשוי להיות כרוך בסדר גודל של שערוכים של הפונקציה. לדוגמה, הרחבת שיטת ניוטון-רפסון לאופטימיזציה שמתבססת על נגזרת שנייה מצריכה בכל איטרציה לשערך את הפונקציה בסדר גודל של פעמים, ולעומתה שיטה המתבססת על הגרדיאנט בלבד מצריכה סדר גודל של שערוכים של הפונקציה. עם זאת, שיטות מבוססות גרדיאנט ידרשו לרוב יותר איטרציות עד להתכנסות.

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

אופטימיזציה בדידה[עריכת קוד מקור | עריכה]

בין השיטות האיטרטיביות באופטימיזציה בדידה נוכל למצוא את אלגוריתם חיפוש מקומי שבכל איטרציה בוחר את האפשרות הטובה ביותר להתקדם מהמצב הנוכחי עד להגעה למצב שטוב יותר מכל שכניו (כלומר אין למצב שכנים טובים ממנו). אלגוריתמים כאלו יכולים לפתור לדוגמה הרחבה של חידת 8 המלכות בעבור מלכות.

שיטות אופטימיזציה היוריסטיות[עריכת קוד מקור | עריכה]

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

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

תחומים עיקריים[עריכת קוד מקור | עריכה]

שימושים[עריכת קוד מקור | עריכה]

כלכלה[עריכת קוד מקור | עריכה]

מיקרו-כלכלה[עריכת קוד מקור | עריכה]

הניתוח הבסיסי של מיקרו-כלכלה מתבסס על הנחות התחרות המשוכללת, שבה אחת מהנחות היסוד היא התנהגות רציונלית של המוכרים והקונים. כלומר מניחים שמטרת הקונים היא למקסם את התועלת שלהם, בעוד שחברות והמוכרים ינסו למקסם את הרווח שלהן. בהתקיים הנחות אלו, על פי הכלכלה הנאו-קלאסית, השוק יתנהל לפי חוקי הביקוש וההיצע, וישאף להגיע לשיווי משקל וליעילות פארטו באמצעות מנגנון "היד הנעלמה". תחת הנחות אלו אפשר להפעיל שיטות אופטימיזציה בכדי לחזות את התנהגות השחקנים בשוק. בעקבות התפתחות הענף של כלכלה התנהגותית שמצביע על כך שהשחקנים פועלים עם רציונליות מוגבלת והטיות קוגניטיביות, כלכלנים פיתחו מודלים של אופטימיזציה סטוכסטית שמתבססים על תאוריית תוחלת התועלת של ג'ון פון נוימן ואוסקר מורגנשטרן, ועל כלים מתורת המשחקים שמסוגלים להגיע לתוצאות אופטימליות תוך התחשבות בתנאי אי ודאות.[3][4] בעיות רבות במיקרו-כלכלה הן בעיות אופטימיזציה, לדוגמה: בעיית מיקסום התועלת (אנ') (כיצד הקונה יכול למקסם את התועלת שלו) היא בעיית אופטימיזציה.

מקרו-כלכלה[עריכת קוד מקור | עריכה]

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

חקר ביצועים[עריכת קוד מקור | עריכה]

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

הנדסה[עריכת קוד מקור | עריכה]

מציאת ארכיטקטורת מסבך אופטימלית ביחס למחיר

תחומים רבים בהנדסה משתמשים בשיטות אופטימיזציה בתכנון העבודה:

הנדסת חשמל[עריכת קוד מקור | עריכה]

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

הנדסת מערכות תקשורת[עריכת קוד מקור | עריכה]

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

הנדסה אזרחית[עריכת קוד מקור | עריכה]

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

ביולוגיה[עריכת קוד מקור | עריכה]

אופטימיזציה נמצאת בשימוש בביולוגיה מולקולרית, ביולוגיה מתמטית (ובפרט בתתי התחומים שלה: ביואינפורמטיקה וביולוגיה מערכתית), הנדסת חילוף חומרים (אנ') וגנומיקה חישובית.

שיטות אופטימיזציה נמצאות בשימוש במידול מערכות ביולוגיות (אנ'), ובפרט בניבוי מבני חלבונים (אנ') (לדוגמה שיטת Dead-end elimination). תכנון לא ליניארי בשילוב עם סימולציות של מערכות ביוכימיות נמצא בשימוש בחקר של חילופי חומרים.[7] שיטות אופטימיציה סייעו גם ביצירת דגמים בחקר התא ובביולוגיה מולקולרית ובדינמיקה של אוכלוסיות (חיזוי התפתחות של זיהום ומחלות זיהומיות). ולבניית שרשראות מיקרוביולוגיות יעילות, שמשמשות לייצור בין היתר של דלקי מאובנים ותרופות.[8]

למידת מכונה[עריכת קוד מקור | עריכה]

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

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

למידת מכונה מונחית[עריכת קוד מקור | עריכה]

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

למידת מכונה בלתי מונחית[עריכת קוד מקור | עריכה]

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

למידת חיזוק[עריכת קוד מקור | עריכה]

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

בעיות NP באופטימיזציה[עריכת קוד מקור | עריכה]

מחלקת בעיות NP באופטימיזציה (ידועה גם כמחלקת סיבוכיות NPO) ניתנת לחלוקה לסוגי הבעיות הבאות:[10]

  • בעיות במחלקת סכמת קירוב פולינומית מלאה (FPTAS), כלומר ניתן למצוא לבעיות האלו פתרון מקורב ככל שנרצה על ידי אלגוריתם קירוב שסיבוכיותו פולינומית גם בגודל הקלט וגם ב- (כלומר אם הוא גודל או עלות הפתרון האופטימלי עבור קלט זה, האלגוריתם מחזיר תשובה שהיא לפחות עבור בעיית מציאת מקסימום או קטנה מ- בעבור בעיית מציאת מינימום, בזמן פולינומי גם בגודל הקלט וגם ב-). לדוגמה המחלקה מכילה את בעיית תרמיל הגב.[11]
  • בעיות במחלקת סכמת קירוב פולינומית (PTAS), כלומר ניתן למצוא לבעיות האלו פתרון מקורב ככל שנרצה על ידי אלגוריתם קירוב בסיבוכיות פולינומית לגודל הקלט בהתייחס ל- כקבוע (מה שמאפשר שהאלגוריתם יהיה אקספוננציאלי ביחס ל-).
  • בעיות במחלקת APX, כלומר ניתן למצוא פתרון מקורב על ידי אלגוריתם קירוב בסיבוכיות פולינומית. לדוגמה המחלקה מכילה את בעיית הספיקות המרבית שאינה מוכלת ב-PTAS.[12]
  • בעיות שניתן למצוא להן פתרון מקורב בסיבוכיות שתהיה בסדר גודל פולינומי בלוגריתם של גודל הקלט. לדוגמה, לבעיית כיסוי הקבוצות ניתן למצוא באופן יעיל פתרון לבעיה הקרוב לאופטימום, בסיבוכיות שתהיה בסדר גודל פולינומי בלוגריתם של גודל הקבוצה שאותה רוצים לכסות.

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ J. Nocedal, S. J. Wright, Numerical Optimization, New York: Springer, עמ' 3, ISBN 978-0-387-30303-1
  2. ^ 1 2 Du, D. Z.; Pardalos, P. M.; Wu, W. (2008). "History of Optimization". in Floudas, C.; Pardalos, P. Encyclopedia of Optimization. Boston: Springer. עמ' 1538–1542. 
  3. ^ Dorfman, Robert (1969). "An Economic Interpretation of Optimal Control Theory". American Economic Review 59 (5): 817–831. JSTOR 1810679. 
  4. ^ A.G. Malliaris (2008). "stochastic optimal control," The New Palgrave Dictionary of Economics, 2nd Edition. ISBN 978-1-349-95121-5
  5. ^ Rotemberg J. Woodford M. (1997) An Optimization-Based Econometric Framework for the Evaluation of Monetary Policy 12 "NBER Macroeconomics Annual": 297–346. doi:10.2307/3585236
  6. ^ Bandler, J.W.; Biernacki, R.M.; Chen, Shao Hua; Grobelny, P.A.; Hemmers, R.H. (1994). "Space mapping technique for electromagnetic optimization". IEEE Transactions on Microwave Theory and Techniques 42 (12): 2536–2544. Bibcode:1994ITMTT..42.2536B. doi:10.1109/22.339794. 
  7. ^ Mendes, P. Mendes; Kell, D. (1998). "Non-linear optimization of biochemical pathways: applications to metabolic engineering and parameter estimation". Bioinformatics 14 (10): 869–883. ISSN 1367-4803. PMID 9927716. doi:10.1093/bioinformatics/14.10.869. 
  8. ^ Kim, J. and J.L. Reed. 2010. OptORF: Optimal metabolic and regulatory perturbations for metabolic engineering of microbial strains. BMC Systems Biology, 4:53.
  9. ^ Sra, S; Nowozin, S; Wright, S. J (ספטמבר 2011). Optimization for Machine Learning. עמ' 403–405. ISBN 9780262537766. 
  10. ^ Juraj Hromkovič, Algorithmics for Hard Problems, Springer, 2, 2004, ISBN 978-3-540-44134-2
  11. ^ Katherine Lai,The Knapsack Problem and Fully Polynomial Time Approximation Schemes (FPTAS)2006
  12. ^ J. Håstad, Some optimal inapproximability results, Proc. 28th Annual ACM Symp. on Theory of Computing (1997), El Paso, Texas, p. 1-10