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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

- תכנון ותפעול אופטימליים

- אמידת מודלים סטטיסטיים

- פתרון מערכת משוואות לא לינאריות

שיטות:

  1. שיטת יחס הזהב - Golden Section (שיטת תחום).
  2. שיטת ניוטון (שיטה פתוחה).
  3. שיטת הגרדיאנט.


1) שיטת יחס הזהב

  • נחפש מינימום בתחום סגור בפונקציה [L, U]

יש נקודת אופטימום אחת התחום.

  • הרעיון - להקטין את התחום בין איטרציה לאיטרציה ע"י יחס הזהב.



Numeriot (9).png


  • שלבי השיטה:

(1) נמצא ו- (לפי הנוסחאות למעלה).

(2) נחשב את ערכי הפונקציה בנקודות ו-

(3) אם אז ו- ומעדכנים את  :

(4) אם אז ו- ומעדכנים את  :

(5) ממשיכים עד להתכנסות או

  • השוואת היא בעייתית כי יכול להיות מצב שבו אנחנו משני צידיה של נקודת מינימום
    Numeriot (10).png
    ואז אנו מפספסים את נקודת המינימום. אם מצב זה קורה, אז ניתן לזרוק את שתי הנקודות ו- ולהקטין את התחום כולו, סימטרית ב-20%.


  • תכונות השיטה:

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

- התכנסות לינארית

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


2) שיטת ניוטון

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

- מנחשים ניחוש התחלתי

- קירוב טיילור סביב הניחוש

- חיתוך עם ציר x:

- האיטרציה הכללית:

  • תכונות השיטה: בדומה לשיטת ניוטון רפסון למציאת שורשים.

- התכנסות מהירה

- נקודת ההתכנסות יכולה להיות מינימום רו מקסימום.

- עלול להתבדר.

- דורש חישוב נגזרות - חלק בדר"כ כבד בתהליך.


3) שיטת הגרדיאנט (ירידה) - משמשת לאופטימיזציה במשתנים מרובים

  • שלבי השיטה:

1) מוצאים את גרדיאנט הפונקציה

2) בוחרים וקטור פתרון התחלתי

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

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

עדכון הפתרון:

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

- נגדיר משתנים

- נגדיר פונקציה חדשה:

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