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

גרף של פרבולואיד הנתון על ידי הפונקציה $z=f(x,y)=-(x^{2}+y^{2})+4$. המקסימום הגלובלי נמצא בנקודה $(x,y,z)=(0,0,4)$ המסומנת בכחול

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

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

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

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

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

החזר את $\mathbf {x}$ שממזער את $f(\mathbf {x} )$

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

$i\in {\mathcal {I}}$	$c_{i}(\mathbf {x} )\geq 0$
$i\in {\mathcal {E}}$	$c_{i}(\mathbf {x} )=0$

כאשר:

• $\,f\,:\,\mathbb {R} ^{n}\rightarrow \mathbb {R}$ היא פונקציית העלות שצריך למזער.
• ${\mathcal {I}}$ היא קבוצת אי השוויונים, שמגדירה אילוצים על תחום הפונקציה.
• ${\mathcal {E}}$ היא קבוצת שוויונים, שמגדירה אילוצים על תחום הפונקציה.

${\mathcal {I}}$ ו-${\mathcal {E}}$ ביחד נקראות האילוצים (לפעמים גם ההגבלות) של הבעיה.

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

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

${\tilde {f}}\left(\mathbf {x} \right):=-f\left(\mathbf {x} \right),\,{\tilde {f}}\,:\,A\rightarrow \mathbb {R}$

אזי השוויון הבא יתקיים לכל ${x}$ עצמים בתיק ו- ${x_{0}}$ עצמים בתיק ששווי מחירם מקסימלי:

$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)$

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

היסטוריה

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

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

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

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

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

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

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

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

שלב באלגוריתם פרנק-וולף

ערך מורחב – שיטה איטרטיבית

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

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

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

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

אופטימיזציה בדידה

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

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

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

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

תחומים עיקריים

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

שימושים

כלכלה

מיקרו-כלכלה

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

מקרו-כלכלה

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

חקר ביצועים

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

הנדסה

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

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

הנדסת חשמל

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

הנדסת מערכות תקשורת

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

הנדסה אזרחית

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

ביולוגיה

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

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

למידת מכונה

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

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

למידת מכונה מונחית

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

למידת מכונה בלתי מונחית

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

למידת חיזוק

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

בעיות NP באופטימיזציה

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

• בעיות במחלקת סכמת קירוב פולינומית מלאה (FPTAS), כלומר ניתן למצוא לבעיות האלו פתרון מקורב ככל שנרצה על ידי אלגוריתם קירוב שסיבוכיותו פולינומית גם בגודל הקלט וגם ב-$1/\varepsilon$ (כלומר אם $OPT$ הוא גודל או עלות הפתרון האופטימלי עבור קלט זה, האלגוריתם מחזיר תשובה שהיא לפחות $(1-\varepsilon )*OPT$ עבור בעיית מציאת מקסימום או קטנה מ-$(1+\varepsilon )*OPT$ בעבור בעיית מציאת מינימום, בזמן פולינומי גם בגודל הקלט וגם ב-$1/\varepsilon$). לדוגמה המחלקה מכילה את בעיית תרמיל הגב.
• בעיות במחלקת סכמת קירוב פולינומית (PTAS), כלומר ניתן למצוא לבעיות האלו פתרון מקורב ככל שנרצה על ידי אלגוריתם קירוב בסיבוכיות פולינומית לגודל הקלט בהתייחס ל-$\varepsilon$ כקבוע (מה שמאפשר שהאלגוריתם יהיה אקספוננציאלי ביחס ל-$1/\varepsilon$).
• בעיות במחלקת APX, כלומר ניתן למצוא פתרון מקורב על ידי אלגוריתם קירוב בסיבוכיות פולינומית. לדוגמה המחלקה מכילה את בעיית הספיקות המרבית שאינה מוכלת ב-PTAS.
• בעיות שניתן למצוא להן פתרון מקורב בסיבוכיות שתהיה בסדר גודל פולינומי בלוגריתם של גודל הקלט. לדוגמה, לבעיית כיסוי הקבוצות ניתן למצוא באופן יעיל פתרון לבעיה הקרוב לאופטימום, בסיבוכיות שתהיה בסדר גודל פולינומי בלוגריתם של גודל הקבוצה שאותה רוצים לכסות.

ראו גם

• אופטימיזציה קמורה
• אופטימיזציה הרמונית
• תכנון ליניארי
• תכנון לא ליניארי
• חשבון וריאציות

לקריאה נוספת

• Jorge Nocedal, Stephen J. Wright, 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

קישורים חיצוניים

• אופטימיזציה, באתר MathWorld (באנגלית)
• אופטימיזציה (מתמטיקה), באתר אנציקלופדיה למתמטיקה (באנגלית)
• Combinatorial Optimization, אוניברסיטת סטנפורד (באנגלית).
• Convex Optimization, אוניברסיטת סטנפורד (באנגלית).
• פירוט על תחומי אופטימיזציה באתר neos-guide (באנגלית).
• אופטימיזציה, באתר אנציקלופדיה בריטניקה (באנגלית)
• תכנות (מתמטיקה), דף שער בספרייה הלאומית