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

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

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

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

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

שיטות:

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

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

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

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

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

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

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

• שלבי השיטה:

(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})$ היא בעייתית כי יכול להיות מצב שבו אנחנו משני צידיה של נקודת מינימום

  

  ואז אנו מפספסים את נקודת המינימום. אם מצב זה קורה, אז ניתן לזרוק את שתי הנקודות $\ X_{1}$ ו- $\ X_{2}$ ולהקטין את התחום כולו, סימטרית ב-20%.

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

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

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

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

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

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

• שלבים:

- מנחשים ניחוש התחלתי $\ x_{0}$

- קירוב טיילור סביב הניחוש $\ f'(x)=f'(x_{0})-f''(x_{0})(x-x_{0})$

- חיתוך עם ציר x: $\ x=x_{0}-{\frac {f'(x_{0})}{f''(x_{0})}}$

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

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

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

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

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

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

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

• שלבי השיטה:

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

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

$\ {\vec {X}}^{(0)}={\begin{pmatrix}x_{1}^{(0)}\\x_{2}^{(0)}\\\vdots \\x_{n}^{(0)}\end{pmatrix}}$

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

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

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

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

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

$\ X_{1}^{(k_{1})}=X_{1}^{(k)}-\alpha ^{(k)}\cdot \nabla f(X_{1}^{(k)})$

$\ \vdots$

$\ X_{1}^{(k_{n})}=X_{n}^{(k)}-\alpha ^{(k)}\cdot \nabla f(X_{n}^{(k)})$

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

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