הצגת המקור של הדף "מבוא לשיטות נומריות/אופטימיזציה"

<u>'''הקדמה'''</u>: בעיית אופטימיזציה משמשות לפתרון בעיות רבות:

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

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

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

<u>'''שיטות:'''</u>

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


<u>'''1) שיטת יחס הזהב'''</u>

* נחפש מינימום בתחום סגור בפונקציה [L, U]   
<u>יש נקודת אופטימום אחת התחום.</u>

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


<math>\ \frac{U-L}{X_2-L} = \frac{\sqrt{5}+1}{2} \quad \Rightarrow \quad X_2=L+0.618(U-L)  </math>

<math>\ \frac{U-L}{U-X_1} = \frac{\sqrt{5}+1}{2}  \quad \Rightarrow \quad X_1=L+0.3819(U-L)  </math>


[[קובץ: Numeriot (9).png|center|thumb|250px| ]]



* שלבי השיטה:

(1) נמצא <math>\ X_1 </math> ו- <math>\ X_2 </math> (לפי הנוסחאות למעלה).

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

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

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

(5) ממשיכים עד להתכנסות <math>\ X_1=X_2 </math>  או <math>\ f(X_1)=f(X_2) </math> 

* השוואת <math>\ f(X_1)=f(X_2) </math>  היא בעייתית כי יכול להיות מצב שבו אנחנו משני צידיה של נקודת מינימום  [[קובץ: Numeriot (10).png|center|thumb|250px| ]]   ואז אנו מפספסים את נקודת המינימום. אם מצב זה קורה, אז ניתן לזרוק את שתי הנקודות  <math>\ X_1 </math> ו- <math>\ X_2 </math> ולהקטין את התחום כולו, סימטרית ב-20%.


* <u>תכונות השיטה:</u>

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

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

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



<u>'''2) שיטת ניוטון'''</u>

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

* שלבים:

- מנחשים ניחוש התחלתי <math>\ x_0 </math> 

- קירוב טיילור סביב הניחוש <math>\ f'(x)=f'(x_0)-f''(x_0)(x-x_0) </math> 

- חיתוך עם ציר x: <math>\ x = x_0 - \frac {f'(x_0)}{f''(x_0)} </math> 

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

* <u>תכונות השיטה:</u> בדומה לשיטת ניוטון רפסון למציאת שורשים.
- התכנסות מהירה

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

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

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



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

* <u>שלבי השיטה:</u>

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

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

<math>\ \vec X^{(0)}= \begin{pmatrix} x_1^{(0)} \\ x_2^{(0)} \\ \vdots \\ x_n^{(0)}  \end{pmatrix} </math>

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

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

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

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

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

<math>\ X_1^{(k_1)}=X_1^{(k)}-\alpha ^{(k)} \cdot \nabla f(X_1^{(k)}) </math>

<math>\ \vdots </math>

<math>\ X_1^{(k_n)}=X_n^{(k)}-\alpha ^{(k)} \cdot \nabla f(X_n^{(k)}) </math>

- נגדיר פונקציה חדשה:
<math>\ g(\alpha)=f(\vec X_{(\alpha _k)}^{(k+1)}) </math>

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

[[קטגוריה:מבוא לשיטות נומריות]]