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

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

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

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

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

שיטות:

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

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

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

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

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

$\frac{U-L}{X_2-L}=\frac{\sqrt{5}+1}{2}\Rightarrow X_2=L+0.618(U-L)$

$\frac{U-L}{U-X_1}=\frac{\sqrt{5}+1}{2}\Rightarrow X_1=L+0.3819(U-L)$

קובץ:Numeriot (9).png

• שלבי השיטה:

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

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

(3) אם $f(X_1)>f(X_2)$ אז $L=X_1$ ו- $X_1=X_2$ ומעדכנים את $X_2$ : $X_2=L+0.618(U-L)$

(4) אם $f(X_1)<f(X_2)$ אז $U=X_2$ ו- $X_1=X_2$ ומעדכנים את $X_1$ : $X_1=L+0.3819(U-L)$

(5) ממשיכים עד להתכנסות $X_1=X_2$ או $f(X_1)=f(X_2)$

• השוואת $f(X_1)=f(X_2)$ היא בעייתית כי יכול להיות מצב שבו אנחנו משני צידיה של נקודת מינימום

  קובץ:Numeriot (10).png

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

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

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

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

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

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

• בשיטה זו נחפש נקודה שמאפסת את הנגזרת של הפונקציה וכך נמצא מינימום. איפוס הנגזרת יעשה כמו מציאת שורש של $f^{\prime }(x)$ באמצעות שיטת ניוטון רפסון.

• שלבים:

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

- קירוב טיילור סביב הניחוש $f^{\prime }(x)=f^{\prime }(x_0)-f^{″}(x_0)(x-x_0)$

- חיתוך עם ציר x: $x=x_0-\frac{f^{\prime }(x_0)}{f^{″}(x_0)}$

- האיטרציה הכללית: $x^{(n+1)}=x(n)-\frac{f^{\prime }(x^{(n)})}{f^{″}(x^{(n)})}$

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

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

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

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

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

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

• שלבי השיטה:

1) מוצאים את גרדיאנט הפונקציה $\mathrm{\nabla }f(x)=(\frac{\partial f}{\partial x_1},\cdots ,\frac{\partial f}{\partial x_n})$

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

${\overrightarrow{X}}^{(0)}=\left(\begin{array}{c}{x}_1^{(0)}\\ x_2^{(0)}\\ ⋮\\ x_n^{(0)}\end{array}\right)$

3) מחשבים גרדיאנט עבור ${\overrightarrow{x}}^{(}0)$ (זיהוי כיוון ירידה מהפתרון הנוכחי).

4) כדי לעדכן את וקטור הפתרון $\overrightarrow{X}$ עלינו לקבוע את גודל הצעד האופטימלי $\alpha$, שיוביל את הפונקציה למינימום ביכוון הירידה.

עדכון הפתרון: ${\overrightarrow{X}}^{(k+1)}={\overrightarrow{X}}^{(k0}-{\alpha }^{(k)}\mathrm{\nabla }f({\overrightarrow{X}}^{(k)})$

• כדי למצוא את ${\alpha }^{(k)}$ האופטימלי נשתמש בשיטה נומרית: התקבלה בעיית אופטימיזציה עם משתנה בודד ${\alpha }^{(k)}$.

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

$X_1^{(k_1)}=X_1^{(k)}-{\alpha }^{(k)}\cdot \mathrm{\nabla }f(X_1^{(k)})$

$⋮$

$X_1^{(k_n)}=X_n^{(k)}-{\alpha }^{(k)}\cdot \mathrm{\nabla }f(X_n^{(k)})$

- נגדיר פונקציה חדשה: $g(\alpha )=f({\overrightarrow{X}}_{({\alpha }_k)}^{(k+1)})$

• נחפש מינימום של $mi{n}_{\alpha }g(\alpha )$ ולאחר מציאת ${\alpha }^{(k)}$ נציב אותו ב- $X^{(k+1)}$ ונקבל ערך לוקטור, נמשיך עד להתכנסות.