אנליזה וקטורית - מציאת ערכי קיצון

חלק ראשון, שבו אנו מוצאים ערכי קיצון מקומיים

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

מה שמתעסקים איתו בחדו”א הוא סיטואציה פשוטה יחסית, שבה המערכת מתוארת על ידי פונקציה \( f:\mathbb{R}\to\mathbb{R} \) שהיא “נחמדה”, במובן זה שהיא גזירה. הרעיון הוא שאפשר להשתמש בנגזרת של \( f \) כדי לאתר מייד את כל נקודות המקסימום ומינימום הנקודתיות של הפונקציה; ובתקווה, אם אין הרבה כאלו, בדיקה קצרה תעלה מה מהן היא המבוקשת שלנו (שעבורה הערך הוא הטוב ביותר אבסולוטית עבור בחירת פרמטרים חוקית). זה לא עובד תמיד טוב, אבל זה עובד טוב מספיק כדי שזה יהיה שימושי ביותר. הטכניקה עצמה מאוד פשוטה - בכל נקודת קיצון מקומית של הפונקציה, הנגזרת שלה חייבת להתאפס (ההפך לאו דווקא נכון). הסיבה פשוטה: ניקח למשל נקודת מקסימום מקומית. כל עוד הפונקציה “עדיין לא הגיעה” אל נקודת המקסימום אבל היא קרובה אליה, היא עולה אליה; ומייד אחרי נקודת המקסימום היא יורדת ממנה. זה אומר שממש לפני ההגעה לנקודת הקיצון הנגזרת היא חיובית ומייד אחרי היא שלילית. זה מכריח את הנגזרת באותה נקודה להיות “בו זמנית חיובית ושלילית”, כלומר בהכרח 0.

בסדרת הפוסטים הנוכחית אנחנו מתעסקים באנליזה וקטורית, כלומר בפונקציות ממשיות מרובות משתנים. אז יש לנו פונקציה \( f:\mathbb{R}^{n}\to\mathbb{R} \) ואנחנו רוצים לפתור את אותה בעיה - למצוא נקודות קיצון. קל לחשוב על הנקודות הללו בצורה ציורית כאשר \( n=2 \) - אפשר לחשוב על \( f \) כאילו היא מתארת מפה טופוגרפית, במובן זה שלכל נקודה \( \left(x,y\right) \) במפה הדו-ממדית נתון לנו גם הגובה של אותה נקודה, \( f\left(x,y\right) \). נקודת מקסימום היא “פסגת הר” ונקודת מינימום היא “תחתית עמק”. וזה מה שאנחנו רוצים למצוא.

הניחוש הנאיבי ביותר הוא שאותה אינדיקציה שעבדה במימד אחד תעבוד גם ב-\( n \) ממדים: אם יש לפונקציה נקודת קיצון ב-\( a\in\mathbb{R}^{n} \), אז \( Df\left(a\right)=0 \) (כאשר כאן \( 0 \) מציין את טרנספורמציית האפס, טרנספורמציה לינארית שמחזירה 0 עבור הכל). למרבה השמחה, הניחוש הנאיבי הזה עובד, ואוכיח זאת עוד רגע; למרבה הצער, בכל זאת יש חלק קשה יותר, והוא הסיווג של נקודות הקיצון הפוטנציאליות, שמטרתו להכריע מי הן נקודות הקיצון האמיתיות ומי הן אנומליות לא קשורות.

בואו ניתן כמה הגדרות פורמליות. כרגיל, כל מה שאנחנו מניחים על \( f \) הוא שהיא מוגדרת על קבוצה פתוחה \( U\subseteq\mathbb{R}^{n} \); אין צורך להניח שהיא מוגדרת בכל מקום. עבור \( f \) כזו, אנחנו אומרים ש-\( a\in U \) היא נקודת מקסימום מקומית אם קיימת סביבה \( V \) של \( a \) ב-\( U \) (“סביבה” היא קבוצה פתוחה שמכילה את \( a \)) כך ש-\( f\left(a\right)\ge f\left(x\right) \) לכל \( x\in V \). באופן דומה מגדירים גם נקודות מינימום.

עכשיו, בואו נגדיר נקודה קריטית של \( f \) בתור נקודה \( a \) שבה \( f \) אינה גזירה, או שהיא גזירה אבל \( Df\left(a\right)=0 \). המשפט הראשון שלנו אומר שאם \( a \) היא נקודת קיצון אז היא נקודה קריטית; אבל יכולות להיות נקודות קריטיות שאינן נקודות קיצון, וקוראים להן נקודות אוכף (כי נקודה שנמצאת על מושב האוכף היא דוגמה יפה לנקודה שבה הנגזרת מתאפסת אבל היא אינה נקודת קיצון). האתגר יהיה לזהות, בהינתן נקודה קריטית, האם היא נקודת קיצון או לא.

ההוכחה שנקודת קיצון היא קריטית מתבססת על רדוקציה למקרה החד ממדי. אם הפונקציה לא גזירה בנקודה, אז על פי הגדרה הנקודה היא נקודת קיצון; לכן אני מניח ש-\( Df\left(a\right) \) מוגדרת. כדי להראות ש-\( Df\left(a\right)=0 \) אני צריך להוכיח שהטרנספורמציה הזו מחזירה 0, לא משנה על איזה וקטור היא מופעלת. ומה זו “הפעלה” של הנגזרת על וקטור \( u \)? אם תזכרו, כי דיברנו על זה מזמן מזמן, זה מה שנותן לנו את הנגזרת המכוונת של \( f \) בכיוון \( h \), שהוגדרה כך: \( \lim_{h\to0}\frac{f\left(a+hu\right)-f\left(a\right)}{h} \). עכשיו, בואו נגדיר פונקציה \( \phi:\mathbb{R}\to\mathbb{R} \) על ידי \( \phi\left(h\right)=f\left(a+hu\right) \). אז קיבלנו ש-

\( Df\left(a\right)\cdot u=\lim_{h\to0}\frac{f\left(a+hu\right)-f\left(a\right)}{h}=\lim_{h\to0}\frac{\phi\left(h\right)-\phi\left(0\right)}{h}=\phi^{\prime}\left(0\right) \)

עכשיו, אם \( a \) היא נקודת קיצון של \( f \), אז \( 0 \) היא נקודת קיצון של \( \phi \), ולכן \( \phi^{\prime}\left(0\right)=0 \) (מהמשפט על נקודת קיצון במקרה החד ממדי), וסיימנו: ראינו ש-\( Df\left(a\right)\cdot u=0 \) לכל \( u \) ולכן \( Df\left(a\right)=0 \). אז זה היה קל, כמובטח. מה הלאה?

בואו נראה שתי דוגמאות פשוטות כדי לקבל תחושה של נקודת קיצון אל מול נקודת אוכף. נתחיל מ-\( f\left(x,y\right)=x^{2}+y^{2} \) - גרף של הפונקציה הזו נראה כמו מין קערית שכזו. הגרדיאנט קל לחישוב: \( \nabla f=\left(2x,2y\right) \). הוא מתאפס בדיוק בנקודה אחת: \( x=y=0 \). לכן זו הנקודה היחידה שעשויה להיות נקודת קיצון, וקל לראות במקרה הזה שמדובר על נקודת מינימום. מסקנה: אין נקודות מקסימום בכלל, אחרת היינו מקבלים עוד נקודות קריטיות.

עכשיו בואו נעבור לדבר על האוכף. נתבונן ב-\( f\left(x,y\right)=x^{2}y+y^{2}x \). הגרדיאנט שלה הוא \( \nabla f=\left(2xy+y^{2},2yx+x^{2}\right) \). אז קיבלנו מערכת של שתי משוואות בשני נעלמים עבור \( \nabla f=0 \). אם \( y=0 \) אז \( 2yx+x^{2}=0 \) גורר ש-\( x=0 \) ולכן פרט לנקודת הקיצון הברורה ב-\( x=y=0 \) אנחנו יכולים להניח בהמשך הניתוח ש-\( x\ne0 \) וגם \( y\ne0 \) ולכן אפשר לחלק בהם. כעת, אם \( 2xy+y^{2}=0 \) נחלק ב-\( y \) ונקבל \( y=-2x \), ובאופן סימטרי \( x=-2y \) מתקבל מהמשוואה השניה. קיבלנו \( x=-2y=4x \), מה שגורר \( x=0 \), וזו סתירה להנחה שלנו שהוא שונה; לכן הנקודה הקריטית היחידה היא \( x=y=0 \). קל לראות שזו לא נקודת קיצון על ידי הסתכלות בישר \( x=y \): עליו, הפונקציה היא \( \phi\left(x\right)=f\left(x,x\right)=2x^{3} \) ולכן עבור \( x>0 \) נקבל ערך חיובי ועבור \( x<0 \) נקבל ערך שלילי, ומכאן ש-\( \left(0,0\right) \) היא לא נקודת קיצון. זו סיטואציה דומה למה שקורה במימד אחד עם, למשל, \( \tan x \).

אז איך מבדילים בין נקודת קיצון ובין “סתם” נקודה קריטית? בחדו”א של משתנה יחיד היה מבחן שעבד טוב במקרה שבו הפונקציה היא “נחמדה מספיק” - אם היא הייתה גזירה פעמיים, אז הנגזרת השניה שלה נתנה לנו את המידע הדרוש. אם הנגזרת השניה בנקודה הקריטית הייתה חיובית, הנקודה הייתה נקודת מינימום; אם היא הייתה שלילית, זו הייתה נקודת מקסימום; ואם היא הייתה 0 אז זו הייתה נקודה קריטית שאינה נקודת קיצון.

האינטואיציה כאן היתה פשוטה. בנקודת מינימום, רגע לפני הנקודה הפונקציה יורדת, כלומר בעלת נגזרת שלילית; רגע אחרי הנקודה הפונקציה עולה, כלומר בעלת נגזרת חיובית; זה אומר שבסביבות הנקודה, הנגזרת היא פונקציה עולה (בהתחלה שלילית, אחר כך 0, לבסוף חיובית). אם היא פונקציה עולה, אז הנגזרת שלה היא חיובית. שיקול דומה מטפל גם בנקודת מקסימום. ומה קרה ב-\( \tan x \), למשל? הפונקציה היא עולה כל הזמן, כלומר הנגזרת היא חיובית כל הזמן (למעט בנקודה הקריטית עצמה, שם היא 0). אבל בהתחלה הנגזרת היא פונקציה יורדת (מתחילה מאוד גדולה ולאט לאט קטנה עד שהיא מגיעה ל-0) ואחרי הנקודה הקריטית היא מתחילה לעלות מחדש. כלומר, בנקודה הקריטית הנגזרת היא חיובית קודם וחיובית אחר כך, כלומר הנקודה הקריטית היא נקודת מינימום של הנגזרת, ולכן הנגזרת השניה היא 0.

היינו שמחים להכליל את הטיעון הזה ל-\( n \) ממדים, וזה אכן מה שנעשה; אפשר להסיק את הקריטריון החד ממדי מהתוצאה שנראה. אבל למרבה הצער, הקריטריון שלנו יהיה מסובך משמעותית יותר מאשר במקרה החד משמעי, ודורש היכרות עם אלגברה לינארית. הקושי הוא בכך שאנחנו צריכים למצוא הכללה כלשהי ל”נגזרת השניה” של מימד אחד. הרי אצלנו “נגזרת” היא כבר לא פונקציה \( f:\mathbb{R}^{n}\to\mathbb{R} \) כמו הפונקציה שאותה גזרנו; היא אופרטור שלכל נקודה במרחב מתאים טרנספורמציה לינארית (או מטריצה, איך שתעדיפו להסתכל על זה), ואי אפשר לגזור את זה. אז אנחנו משתמשים במשהו אחר - מטריצה \( n\times n \) שכוללת את כל הנגזרות החלקיות המעורבות מסדר שני. המטריצה הזו נקראת הסיאן.

מה זו נגזרת חלקית אנחנו כבר יודעים - פשוט גוזרים את הפונקציה רק על פי משתנה בודד ומתייחסים ליתר בתור פרמטרים. ראינו כבר שאם \( f \) גזירה אז הנגזרת שלה ניתנת לתיאור בתור וקטור הנגזרות החלקיות של \( f \). נגזרת חלקית “מסדר שני” היא מה שמתקבל כשגוזרים נגזרת חלקית שוב, ו”מעורבת” אומר שאפשר לגזור שוב על פי כל אחד מהמשתנים. אני מסמן \( \frac{\partial^{2}f}{\partial x\partial y} \) את מה שמתקבל כשאני גוזר את \( f \) קודם כל לפי המשתנה \( x \) ואז לפי המשתנה \( y \). למשל, עבור פונקציית נקודת האוכף \( f\left(x,y\right)=x^{2}y+y^{2}x \) אנחנו יודעים ש-\( \frac{\partial f}{\partial x}=2xy+y^{2} \), ולכן אם נגזור שוב לפי \( y \), נקבל ש-\( \frac{\partial^{2}f}{\partial x\partial y}=2x+2y \).

מטריצת הסיאן מתקבלת באופן דומה - הכניסה בשורה ה-\( i \) ובעמודה ה-\( j \) שווה לנגזרת החלקית קודם לפי המשתנה \( x_{i} \) ואחר כך לפי המשתנה \( x_{j} \), כלומר \( \left[H\right]_{ij}=\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}} \). אם נכתוב את ההסיאן של \( f\left(x,y\right)=x^{2}+y^{2} \) נקבל \( \left[\begin{array}{cc}2 & 0\\0 & 2\end{array}\right] \). אם נכתוב את ההסיאן של \( f \) של נקודת האוכף, נקבל \( \left[\begin{array}{cc}2y & 2x+2y\\2x+2y & 2x\end{array}\right] \). שימו לב שזו מטריצה סימטרית, כלומר יוצא שהנגזרת המעורבת קודם לפי \( x \) ואז על פי \( y \) שווה לנגזרת המעורבת קודם על פי \( y \) ואז על פי \( x \); זה לא מקרי וזה תמיד מתקיים אם שתי הנגזרות המעורבות הללו הן רציפות; אנחנו נניח מעכשיו ש-\( f \) היא ב-\( C^{2} \), אחרת המשפט שאני מתאר לא יהיה נכון.

עכשיו אפשר לנסח את הקריטריון שלנו בלשון שאותה יבינו מי שמכירים אלגברה לינארית: אם בנקודה הקריטית ההסיאן הוא מטריצה חיובית לחלוטין (Positive Definite Matrix), אז הנקודה הקריטית היא נקודת מינימום; ואם ההסיאן הוא מטריצה שלילית לחלוטין (Negative Definite Matrix) אז הנקודה הקריטית היא נקודת מקסימום; ואחרת אין לנו מושג מהי הנקודה הקריטית. מן הסתם המושג המרכזי פה הוא “חיובית/שלילית לחלוטין” שתכף אסביר, אבל למי שרוצים את התכל’ס, תנאי שקול לכך שמטריצה תהיה חיובית לחלוטין הוא שכל הערכים העצמיים שלה יהיו חיוביים, ואילו עבור שלילית לחלוטין, שכולם יהיו שליליים. זה מסביר את התוצאה בשתי הדוגמאות שראינו; במקרה הראשון קיבלנו מטריצה שהערך העצמי היחיד שלה הוא 2 החיובי, ולכן הנקודה הקריטית היא נקודת מינימום; ובמקרה השני ההסיאן ב-\( x=y=0 \) הוא מטריצת האפס, שהערך העצמי היחיד שלה הוא 0 שאינו חיובי או שלילי.

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

אנחנו יודעים שכל מטריצה \( A \) מסדר \( n\times n \) מעל שדה \( \mathbb{F} \) מגדירה טרנספורמציה לינארית \( T_{A}:\mathbb{F}^{n}\to\mathbb{F}^{n} \). אבל יש עוד סוג מעניין של העתקה בערך-לינארית שהמטריצה מגדירה: תבנית בילינארית, שהיא פונקציה \( B_{A}:\mathbb{F}^{n}\times\mathbb{F}^{n}\to\mathbb{F} \) שלינארית בכל אחד משני הרכיבים שלה בנפרד, ומוגדרת על ידי \( B\left(v,u\right)=v^{t}Au \) (כלומר, כופלים את המטריצה \( A \) בוקטור העמודה \( u \) כרגיל ומקבלים וקטור ב-\( \mathbb{F}^{n} \), אבל אחר כך כופלים את התוצאה הזו גם בוקטור השורה \( v^{t} \), דהיינו מבצעים מכפלה סקלרית של \( v \) ושל \( Au \)). כל תבנית בילינארית מגדירה, בתורה, גם פונקציה \( g:\mathbb{F}^{n}\to\mathbb{F} \) על ידי \( g_{A}\left(v\right)=B_{A}\left(v,v\right)=v^{t}Av \) (במילים, כופלים סקלרית את \( v \) בתמונה של \( v \) על ידי הטרנספורמציה הלינארית שמוגדרת על ידי \( A \)). לפונקציה כזו קוראים תבנית ריבועית והיא מה שמעניין אותנו כאן. דוגמה פשוטה לתבנית בילינארית היא מכפלה פנימית, ודוגמה פשוטה לתבנית ריבועית שמוגדרת על ידה היא נורמה (כמעט; כזכור, נורמה היא השורש של מכפלה פנימית של וקטור עם עצמו). תבניות בילינאריות וריבועיות מופיעות באינספור מקומות במתמטיקה, הגם שהן קצת פחות נפוצות מטרנספורמציות לינאריות, ולרוב מגיעים אליהן רק בקורס שני באלגברה לינארית.

עכשיו בואו נעזוב את האלגברה הלינארית הכללית ונזכור שאנחנו מדברים על המקרה שבו \( \mathbb{F}=\mathbb{R} \). בממשיים יש יחס סדר - אפשר להגיד “חיובי” ו”שלילי” (אפילו ב-\( \mathbb{C} \) אי אפשר להגיד דברים כאלו). זה מוביל אותנו להגדרה שאנחנו רוצים - \( A \) היא מטריצה חיובית לחלוטין אם התבנית הריבועית שהיא מגדירה מקיימת ש-\( g_{A}\left(x\right)>0 \) לכל \( x\ne0 \) (עבור \( x=0 \) תמיד נקבל \( g_{A}\left(x\right)=0 \), כמובן). בדומה \( A \) היא שלילית לחלוטין אם \( g_{A}\left(x\right)<0 \) לכל \( x\ne0 \). עבור מטריצה מסדר \( 1\times1 \) הקריטריון הזה שקול לכך שהכניסה היחידה של המטריצה תהיה חיובית/שלילית (כי אם \( A=\left[a\right] \) אז נקבל ש-\( g_{A}\left(x\right)=a\cdot x^{2} \)) ולכן קיבלנו פה הכללה של התוצאה עבור \( n=1 \).

כדי להבין למה זה עובד ומאיפה \( H \) הגיעה בכלל אני צריך לשלוף מהכובע שפן שלפחות לעת עתה בחרתי לא לתת לו פוסט, אבל אולי בעתיד כן - פולינומי טיילור. תיארתי אותם פעם בבלוג במקרה החד ממדי, וכנראה שכדאי לתאר אותם בפירוט גם במקרה הרב ממדי, אבל לבינתיים אסתפק בהסבר קצר. כזכור, פולינום טיילור “רגיל” מאפשר לנו לקרב פונקציות מסובכות על ידי פולינומים שמחושבים מתוך כל הנגזרות של הפונקציה בנקודה מסויימת ש”סביבה” מפתחים אותה. פורמלית, \( f\left(x_{0}+h\right)=\sum_{k=0}^{n}\frac{f^{\left(k\right)}\left(x_{0}\right)}{k!}h^{k}+R_{n+1}\left(x_{0},h\right) \), כאשר \( \sum_{k=0}^{n}\frac{f^{\left(k\right)}\left(x_{0}\right)}{k!}h^{k} \) הוא הפולינום, ואילו \( R_{n+1}\left(x_{0},h\right) \) היא פונקציית ה”שארית” שמתארת את הטעות של הפולינום (ומן הסתם לב העניין הוא לחסום את הגודל שלה, מה שיוצא שונה עבור פונקציות שונות ונקודות פיתוח שונות). לפעמים פשוט כותבים טור חזקות אינסופי, \( \sum_{n=0}^{\infty}\frac{f^{\left(n\right)}\left(x_{0}\right)}{n!}h^{n} \), אבל עם הכתיב הזה צריך להיזהר כי לא בהכרח ברור עבור אילו ערכים של \( h \) הטור הזה מתכנס בכלל (עבור \( h=0 \) הוא מתכנס תמיד, אבל פרט לכך? הדיון על רדיוס ההתכנסות של טורי חזקות הוא מעניין בפני עצמו וצריך להציג אותו בבלוג מתישהו) וגם לא ברור שאפילו אם הטור מתכנס, אז \( f\left(x_{0}+h\right) \) שווה לסכום שלו.

פולינומי טיילור של פונקציות \( f:\mathbb{R}^{n}\to\mathbb{R} \) עובדים בצורה דומה, אבל כפי שאתם מנחשים, צריך לזרוק פנימה את כל הנגזרות החלקיות וזה יוצא מתוסבך למדי לכתיבה בלי שמסכימים מראש על כל מני קיצורים. בכל זאת אני לא יכול להתאפק ואציג את הטור המלא של פיתוח סביב \( \left(a_{1},\dots,a_{n}\right) \):

\( \sum_{k_{1}=0}^{\infty}\cdots\sum_{k_{n}=0}^{\infty}\frac{\partial^{k_{1}}}{\partial x_{1}^{k_{1}}}\cdots\frac{\partial^{k_{n}}}{\partial x_{n}^{k_{n}}}f\left(a_{1},\dots,a_{n}\right)\frac{h_{1}^{k1}\cdots h_{n}^{k_{n}}}{k_{1}!\cdots k_{n}!} \)

או במילים: כל איבר בטור הזה מתקבל על ידי כך שגוזרים את \( f \) מספר מסויים של פעמים על פי כל משתנה, כופלים את התוצאה בחזקות מתאימות של כניסות \( \left(h_{1},\dots,h_{n}\right) \) ומחלקים בעצרת מתאימה. בואו נראה דוגמה פשוטה עבור פונקציה \( f\left(x,y\right) \) שהיא ב-\( C^{2} \) ולכן \( \frac{\partial^{2}f}{\partial x\partial y}=\frac{\partial^{2}f}{\partial y\partial x} \); נפתח את הטור עד סדר שני, כלומר עד וכולל ערכי ה-\( k \) שמקיימים \( k_{1}+k_{2}=2 \):

\( f\left(x+h_{1},y+h_{2}\right)=f\left(x,y\right)+\frac{\partial f}{\partial x}\left(x,y\right)h_{1}+\frac{\partial f}{\partial y}\left(x,y\right)h_{2}+\frac{\partial^{2}f}{\partial x^{2}}\left(x,y\right)\frac{h_{1}^{2}}{2}+\frac{\partial^{2}f}{\partial y^{2}}\left(x,y\right)\frac{h_{2}^{2}}{2}+\frac{\partial^{2}f}{\partial x\partial y}\left(x,y\right)h_{1}h_{2}+R_{3}\left(h_{1},h_{2}\right) \)

ואם יש לנו \( n \) משתנים, הכתיב נשאר דומה:

\( f\left(x_{1}+h_{1},\dots,x_{n}+h_{n}\right)=f\left(x_{1},\dots,x_{n}\right)+\sum_{i=1}^{n}\frac{\partial f}{\partial x_{i}}\left(x_{1},\dots,x_{n}\right)h_{i}+\frac{1}{2}\sum_{i,j=1}^{n}\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}}\left(x_{1},\dots,x_{n}\right)h_{i}h_{j}+R_{3}\left(h_{1},\dots,h_{n}\right) \)

כאן אנחנו קצת מרמים בסימון אבל מתקנים את זה בו זמנית: למשל, בסכום מופיעים גם \( \frac{\partial^{2}f}{\partial x_{1}\partial x_{2}} \) וגם \( \frac{\partial^{2}f}{\partial x_{2}\partial x_{1}} \) למרות שהאיבר הזה (אלו שתי הצגות שונות לאותו איבר, כי אמרתי שבמקרה שלנו הנגזרות המעורבות שוות) אמור להופיע רק פעם אחת. אז יש לי ספירה כפולה, אבל זה מתקזז עם הכפל ב-\( \frac{1}{2} \) שהוספתי שם (אם תשימו לב, בנוסחה המקורית אם גזרנו פעמיים לפי אותו משתנה צריך לכפול ב-\( \frac{1}{2!} \) ואם גזרנו לפי שני משתנים שונים לא עושים את זה).

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

\( f\left(x+h\right)=f\left(x\right)+\nabla f\left(x\right)\cdot h+\frac{1}{2}H_{x}\left(h\right)+R_{3}\left(h\right) \)

במילים אחרות, הגרדיאנט של \( f \) הוא “האיבר הראשון” בפיתוח טיילור של \( f \), וההסיאן \( H \) הוא “האיבר השני”. האנלוגיה למקרה החד ממדי (שבו האיבר הראשון בפיתוח הוא הנגזרת הראשונה, והאיבר השני הוא הנגזרת השניה) מובהקת כאן.

איך כל זה רלוונטי לענייננו? כזכור, אנחנו מניחים שב-\( x \) יש ל-\( f \) נקודה קריטית ורוצים לסווג אותה. נקודה קריטית פירושו של דבר ש-\( \nabla f\left(x\right)=0 \), כך שאפשר לכתוב את פיתוח הטיילור גם בתור

\( f\left(x+h\right)-f\left(x\right)=\frac{1}{2}H_{x}\left(h\right)+R_{3}\left(h\right) \)

נניח שההסיאן ב-\( x \) הוא חיובי לחלוטין, ולכן על פי המשפט אמור לנבוע מכך ש-\( x \) היא נקודת מינימום. אם \( x \) היא נקודת מינימום של \( f \), אנחנו מצפים שאגף שמאל יהיה חיובי עבור כל ה-\( h \)-ים בסביבה קרובה מספיק של \( x \). ומה קורה באגף ימין? יש לנו קרב ענקים בין ההסיאן ובין \( R_{3}\left(h\right) \), השארית. כאן מגיע טיעון אינפי סטנדרטי - אם ניקח \( h \) “מספיק קטן” אז מצד אחד השארית תהיה קטנה מאוד, ומצד שני ההסיאן יחזיר לנו ערך שהוא יחסית גדול וחיובי, והערך הזה “ינצח” בתחרות. אני אדלג על המשך ההוכחה כי הוא טכני באופן סטנדרטי ואומר בדיוק את זה; הפואנטה המרכזית היא שבגלל שההסיאן הוא פונקציה “נחמדה” (בילינארית) מקבלים שקיים קבוע \( M \) כלשהי כך ש-\( H\left(h\right)\ge M\|h\|^{2} \) לכל \( h \), וזה נותן לנו את ה”יחסית גדול וחיובי” שלנו. הפרטים הטכניים פחות קריטיים פה - מה שמעניין בסיפור הזה, לטעמי, הוא מאיפה ההסיאן הזה צץ בכלל; כשברור שזה הרכיב השני בפיתוח הטיילור של הפונקציה, ושהרכיב הראשון איננו עמנו עוד כי אנחנו בנקודה קריטית, העניין נהיה מאוד ברור.

חלק שני, שבו כל העסק נהיה מאולץ

בתחילת הפוסט אמרתי שבבעיות אופטימיזציה יש לנו לעתים קרובות אילוצים על המערכת, כלומר לא כל פרמטר הוא חוקי. זה מגדיל מייד את רמת הקושי של הבעיה שלנו ועל פניו הופך את כל הטכניקה שראינו עד כה לחסרת תועלת. אתן דוגמה פשוטה. נסתכל על הפונקציה \( f:\mathbb{R}^{2}\to\mathbb{R} \) המוגדרת על ידי \( f\left(x,y\right)=x \). בבירור אין לה לא נקודת מינימום ולא נקודת מקסימום בשום מקום ולכן הטכניקה שראינו קודם לא תסייע לנו עם העיסוק בה בכלל. מצד שני, אם נוסיף למערכת את האילוץ שהקלטים ל-\( f \) חייבים להילקח רק ממעגל היחידה, אז ברור שפתאום יש ל-\( f \) מקסימום ב-\( \left(1,0\right) \) ומינימום ב-\( \left(-1,0\right) \). אבל איך מוצאים את זה?

לפני שנפתור את הבעיה הזו, צריך להבין מה המשמעות של “אילוץ”. עבורנו זה אומר שנתונה פונקציה \( g:\mathbb{R}^{n}\to\mathbb{R} \) כלשהי ונתון \( c\in\mathbb{R} \), ואנחנו מגדירים אילוץ על ידי המשוואה \( g\left(x\right)=c \). כלומר, מותר לחפש את הפתרון רק בקרב ה-\( x \)-ים שמקיימים \( g\left(x\right)=c \). בדוגמה שלי, \( g\left(x,y\right)=x^{2}+y^{2} \) ואילו \( c=1 \). כפי שבטח כבר ברור לכם, השיטה הזו להבעת אילוצים היא נוחה מאוד ומאפשרת לתאר שלל יצורים גאומטריים (ראינו כרגע מעגל; קו ישר מתואר על ידי \( g\left(x,y\right)=ax-by \) עבור \( a,b \) כלשהם, וכדומה).

כעת, נניח ש-\( g \) היא פונקציה “נחמדה” - גזירה. נסמן ב-\( S \) את המרחב שמוגדר על ידי \( S=\left\{ x\in\mathbb{R}^{n}\ |\ g\left(x\right)=c\right\} \) (מעכשיו אקרא לו “משטח” כי בתלת מימד משוואות כאלו מגדירות משטחים; שם מדויק יותר למקרה הכללי שבו אני עוסק הוא יריעה אבל זה מושג לא טריוויאלי ואני לא רוצה להיכנס להגדרה שלו כרגע), וניקח \( x_{0}\in S \) כלשהו. הנה אבחנה מיידית שבלבלה אותי בצורה יוצאת דופן כשרק למדתי את הנושא הזה: \( \nabla g\left(x_{0}\right) \) הוא אורתוגונלי ל-\( S \) בנקודה \( x_{0} \). הגרדיאנט של הפונקציה שמגדירה את המשטח ניצב למשטח באותה נקודה. למה זה מבלבל? כי לעתים קרובות נהוג להגדיר את הגרדיאנט של פונקציה בנקודה כלשהי בתור הוקטור שמצביע על הכיוון שבו היא “הכי תלולה”. אם הגרדיאנט ניצב למשטח, הוא מצביע על כיוון שבו הפונקציה בכלל לא גדלה, וזה נראה הכי לא נכון שרק אפשר. אז למה זה מסתדר?

זה מסתדר כי עשיתי מיש-מש מכל העסק. הגרדיאנט לא ניצב לפונקציה; הוא ניצב למשטח שהפונקציה מגדירה בצורה מסויימת. מה שבלבל אותי בשעתו הוא שאפשר להגדיר משטחים בשתי דרכים שונות. דרך אחת, כללית פחות, היא לכתוב \( z=f\left(x,y\right) \) ובכך לתאר את המשטח \( S=\left\{ \left(x,y,f\left(x,y\right)\right)\ |\ x,y\in\mathbb{R}^{2}\right\} \); הדרך השניה, הכללית יותר, היא לכתוב \( S=\left\{ \left(x,y,z\right)\ |\ F\left(x,y,z\right)=c\right\} \). שימו לב שבדרך הראשונה אנחנו משתמשים בפונקציה של שני משתנים ובשניה בפונקציה של שלושה משתנים כדי להגדיר את אותו הדבר - משטח ב-\( \mathbb{R}^{3} \). אם יש לי פונקציה \( f:\mathbb{R}^{2}\to\mathbb{R} \) ואני רוצה להציג את המשטח שמוגדר על ידה בדרך הראשונה בעזרת דרך ההצגה השניה, אני פשוט אגדיר \( F\left(x,y,z\right)=z-f\left(x,y\right) \) ו-\( c=0 \); לכן דרך ההצגה השניה כללית יותר. היא כללית יותר ממש (כלומר, יש דברים שאי אפשר לעשות בדרך הראשונה) כי למשל אני יכול לתאר את כדור היחידה על ידי \( F\left(x,y,z\right)=x^{2}+y^{2}+z^{2} \) ו-\( c=1 \), אבל אין לי דרך לעשות את זה באמצעות הצגת קואורדינטת ה-\( z \) כפונקציה של שתי האחרות (כי עבור אותם \( x,y \) עשויים להיות שני ערכי \( z \) אפשריים שונים על המשטח).

הנה הוכחה זריזה לכך שהגרדיאנט ניצב למשטח שהפונקציה מגדירה. הרעיון הוא לקחת מסלול כלשהו במשטח שעובר דרך \( x_{0} \) ולהראות שהגרדיאנט ב-\( x_{0} \) ניצב אליו. בלי להיכנס לעובי ההגדרות, מסלול הוא פונקציה גזירה \( c:\left[0,1\right]\to\mathbb{R}^{n} \), ומסלול במשטח \( S\subseteq\mathbb{R}^{n} \) מקיים את הדרישה ש-\( c\left(\left[0,1\right]\right)\subseteq S \), ונניח ש-\( c\left(0\right)=x_{0} \). עכשיו, הרעיון במסלול שעובר דרך \( S \) הוא שכל נקודה בו מקיימת את האילוץ שמגדיר את \( S \). נניח שהאילוץ הזה הוא \( F\left(x\right)=c \), אז \( F\left(c\left(t\right)\right)=c \) לכל \( t\in\left[0,1\right] \). עכשיו אפשר להשתמש בכלל השרשרת, לגזור ולקבל ש-\( DF\left(c\left(0\right)\right)\cdot Dc\left(0\right)=0 \), או בסימון קצת שונה, ש-\( \nabla F\left(x_{0}\right)\cdot c^{\prime}\left(0\right)=0 \). עכשיו, \( c^{\prime}\left(0\right) \) הוא בדיוק שיפוע המשיק ל-\( c \) ב-\( x_{0} \), ואילו \( \nabla F\left(x_{0}\right) \) הוא הגרדיאנט של \( F \), וקיבלנו שהמכפלה הפנימית שלהם היא 0 - כלומר, הם ניצבים.

עכשיו בואו נפתור את הבעיה של אופטימיזציה-עם-אילוצים. הפתרון הוא סוג של הכללה של מה שראינו קודם. קודם בדקנו איפה הגרדיאנט של \( f \) מתאפס. ההכללה שלנו תהיה לבדוק איפה הגרדיאנט של \( f \) שווה לצירוף לינארי של האילוצים. המקדמים של האילוצים נקראים “כופלי לגראנז'”, והשיטה נקראת על שמם - שיטת כופלי לגראנז’.

הנה הניסוח הפורמלי. נניח שיש לנו פונקציה \( f:\mathbb{R}^{n}\to\mathbb{R} \) שהיא מה שאנחנו רוצים לאפטמז, ופונקציות אילוצים \( g_{1},\dots,g_{k}:\mathbb{R}^{n}\to\mathbb{R} \) עם קבועים \( c_{1},\dots,c_{k} \) שמגדירות קבוצה \( S \) (כלומר, האילוץ הוא \( g_{i}\left(x\right)=c_{i} \) עבור \( 1\le i\le k \)). נניח ש-\( x_{0} \) היא נקודה שמקיימת את כל האילוצים (\( g_{i}\left(x_{0}\right)=c_{i} \)) וש-\( \nabla g_{i}\left(x_{0}\right)\ne0 \), ושיש ל-\( f|_{S} \) מקסימום או מינימום מקומי ב-\( x_{0} \) (הסימון \( f|_{S} \) פירושו “\( f \) מצומצמת ל-\( S \)”), אז קיימים \( \lambda_{1},\dots,\lambda_{k}\in\mathbb{R} \) כך ש-\( \nabla f\left(x_{0}\right)=\lambda_{1}\nabla g_{1}\left(x_{0}\right)+\dots+\lambda_{k}\nabla g_{k}\left(x_{0}\right) \). זה אומר שכשאנחנו מחפשים נקודות קיצון, אנחנו מקבלים מערכת של משוואות שנקודות הקיצון חייבות להיכלל בפתרונות שלה.

בואו נראה איך זה עובד במקרה של דוגמת המעגל שנתתי קודם. מכיוון ש-\( f\left(x,y\right)=x \) אז \( \nabla f=\left(1,0\right) \), ומכיוון ש-\( g\left(x,y\right)=x^{2}+y^{2} \), אז \( \nabla g=\left(2x,2y\right) \). משוואת כופלי לגראנז’ נותנת לנו כאן את המשוואה \( \left(1,0\right)=\lambda\left(2x,2y\right) \) שמתורגמת בתורה לשתי משוואות פשוטות:

\( 2x\lambda=1 \)

\( 2y\lambda=0 \)

מהמשוואה הראשונה ברור ש-\( \lambda\ne0 \) ולכן מהשניה קיבלנו ש-\( y=0 \) הוא הכרחי. הנקודות היחידות שמקיימות את האילוץ \( g\left(x,y\right)=1 \) ומקיימות \( y=0 \) הן \( \left(1,0\right) \) ו-\( \left(-1,0\right) \) ועבור כל אחת מהן יש, כמובן, \( \lambda \) שפותר את המשוואה. קיבלנו ששתי אלו הן נקודות הקיצון שלנו, וזה אכן מה שהתחלתי ממנו.

חסרים לנו עוד שני דברים - אינטואיציה למה כל זה עובד, והוכחה. את ההוכחה המלאה אני לא אביא כאן, ובמקום זה אתן דגש חזק על הרעיונות הכלליים. הדבר הראשון שצריך להבין הוא שנתתי למעלה את הגרסה ה”שימושית” של המשפט - קחו את הגרדיאנט של \( f \), אז הוא צירוף לינארי של הגרדיאנטים של האילוצים. זה משהו שקל להשתמש בו פרקטית, אבל זו לאו דווקא הדרך הקלה ביותר לחשוב על המשפט. אז הנה ניסוח כללי יותר של המשפט: אם \( S \) הוא משטח, \( x_{0}\in S \) היא נקודה על המשטח ו-\( f \) היא פונקציה כך של-\( f|_{S} \) יש נקודת קיצון ב-\( x_{0} \), אז המישור המשיק ל-\( S \) בנקודה \( x_{0} \) מוכל בגרעין של \( \nabla f\left(x_{0}\right) \). אם אני אסמן את המישור המשיק ל-\( S \) בנקודה \( x_{0} \) בתור \( T_{x_{0}}S \) אז אפשר לכתוב פשוט \( T_{x_{0}}S\subseteq\ker\left(\nabla f\left(x_{0}\right)\right) \) (אתם אמורים להכיר גרעין כי זה מושג בסיסי באלגברה לינארית; אוסף כל הנקודות שמאפסות את הטרנספורמציה הלינארית \( \nabla f\left(x_{0}\right) \)).

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

הדרך להגיע מהניסוח הזה לניסוח שהצגתי קודם היא דרך תוצאה לא מרתקת במיוחד באלגברה לינארית: נניח ש-\( f:\mathbb{R}^{n}\to\mathbb{R} \) היא טרנספורמציה לינארית ו-\( G:\mathbb{R}^{n}\to\mathbb{R}^{m} \) היא טרנספורמציה לינארית, אז \( \ker G\subseteq\ker f \) אם ורק אם קיימים \( \lambda_{1},\dots,\lambda_{m} \) כך ש-\( f=\sum\lambda_{i}G_{i} \), כאשר \( G_{i} \) הוא ההטלה של \( G \) לרכיב ה-\( i \), כלומר \( G_{i}\left(a\right)=\left[G\left(a\right)\right]_{i} \).

מה שמעניין הוא להבין מה האינטואיציה שמאחורי המשפט הכללי. למה שהוא יהיה נכון? הנקודה הקריטית היא שאם \( S \) הוא משטח שמוגדר בצורה “נחמדה מספיק” אז בהינתן נקודה \( x_{0}\in S \) כלשהי, יש סביבה של \( x_{0} \) שנראית כמו תת-מרחב לינארי של \( \mathbb{R}^{n} \). ההגדרה של “יריעה”, שאני חומק ממנה בפוסט הזה, מפרמלת את הרעיון הזה; בואו נראה דוגמה פשוטה. את המעגל שלנו מתחילת הפוסט אפשר לתאר באמצעות פרמטריזציה: פונקציה גזירה \( p:\mathbb{R}\to\mathbb{R}^{2} \) שמוגדרת על ידי \( p\left(t\right)=\left(\sin t,\cos t\right) \). על ה-\( p \) הזו אפשר להרכיב את \( f \) שלנו, שהיא הפונקציה שאנחנו מנסים לאפטמז, ולקבל את הפונקציה \( \varphi\left(t\right)=f\left(p\left(t\right)\right)=\sin t \). קיבלנו פונקציה במשתנה בודד שמוגדרת מעל \( \mathbb{R} \), כך שאפשר לחפש לה מקסימום ומינימום בדרך הרגילה - גוזרים ומשווים לאפס. תנסו, תראו שזה עובד.

אז גם באופן כללי, אם יש לנו פרמטריזציה של \( S \) בסביבה של \( x_{0} \) מצבנו טוב. בואו נניח ש-\( p:\mathbb{R}^{n}\to\mathbb{R}^{n} \) היא פרמטריזציה שכזו; פירוש הדבר הוא ש-\( p\left(\mathbb{R}^{n}\right) \) הוא סביבה של \( x_{0} \) ב-\( S \). אנחנו מניחים שב-\( x_{0} \) יש ל-\( f \) נקודת קיצון מקומית; בואו נסמן ב-\( a\in\mathbb{R}^{n} \) נקודה שמקיימת \( p\left(a\right)=x_{0} \). אז לפונקציה \( f\left(p\left(t\right)\right) \) יש נקודת קיצון מקומית ב-\( a \), מה שאומר ש-\( D\left[f\left(p\left(a\right)\right)\right] \) תהיה טרנספורמציית האפס. מכלל השרשרת נובע שזה אומר ש-\( Df\left(p\left(a\right)\right)\cdot Dp\left(a\right) \) היא טרנספורמציית האפס.

עכשיו, את \( Df\left(p\left(a\right)\right) \) אנחנו מכירים בסימון קצת שונה. ראשית, \( p\left(a\right)=x_{0} \). שנית, מכיוון ש-\( f \) היא פונקציה שמחזירה סקלר, אני מסמן את \( Df \) ב-\( \nabla f \). כלומר, \( Df\left(p\left(a\right)\right)=\nabla f\left(x_{0}\right) \) הישן והטוב.

שנית, מה זה \( Dp\left(a\right) \)? זכרו ש-\( p \) היא פונקציה שמגדירה לנו משטח; לכן \( Dp\left(a\right) \) מתארת את המישור המשיק למשטח בנקודה \( p\left(a\right)=x_{0} \), מה שסימנתי בתור \( T_{x_{0}}S \) (כן, זה היה נפנוף ידיים). כלומר, לכל קלט שהיא מקבלת, \( Dp\left(a\right) \) מחזירה לנו נקודה ששייכת ל-\( T_{x_{0}}S \).

עכשיו, ראינו שההרכבה של \( \nabla f\left(x_{0}\right) \) על \( Dp\left(a\right) \) היא זהותית אפס. זה אומר שלכל קלט ש-\( Dp\left(a\right) \) מקבלת, הפלט שלה (נקודה ב-\( T_{x_{0}}S \)) יגרום ל-\( \nabla f\left(x_{0}\right) \) להחזיר אפס. מכיוון ש-\( Dp\left(a\right) \) היא פונקציה על כל \( T_{x_{0}}S \) נקבל את התוצאה - \( T_{x_{0}}S\subseteq\ker\nabla f\left(x_{0}\right) \). הפורמליזם פה לא היה מלא אבל אני מקווה שהרעיון ברור עכשיו.