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

(הופנה מהדף בעיית אופטימיזציה)

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

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

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

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

הצורה הסטנדרטית

עריכה

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

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

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

   
   

כאשר:

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

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

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

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

 

אזי השוויון הבא יתקיים לכל   עצמים בתיק ו-   עצמים בתיק ששווי מחירם מקסימלי:

 

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

היסטוריה

עריכה

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

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

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

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

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

שיטות אופטימיזציה ישירות

עריכה

שיטות אופטימיזציה איטרטיביות

עריכה
 
שלב באלגוריתם פרנק-וולף
  ערך מורחב – שיטה איטרטיבית

אופטימיזציה רציפה

עריכה

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

אחת מאמות המידה החשובות בהקשר של שיטות איטרטיביות הוא מספר הפעמים שנדרשים לשערך את ערך הפונקציה, שכן שערוך הפונקציה עשוי להיות יקר. עבור פונקציה בעלת 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. (eds.). Encyclopedia of Optimization. Boston: Springer. pp. 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. doi:10.1093/bioinformatics/14.10.869. ISSN 1367-4803. PMID 9927716.
  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. pp. 403–405. ISBN 9780262537766. {{cite book}}: (עזרה)
  10. ^ Juraj Hromkovič, Algorithmics for Hard Problems, 2, Springer, 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