כופלי לגראנז'

העקום האדום מתאר את האילוץ g(x, y)=c. העקומים הכחולים הם קווים שווי ערך (קווי גובה) של (f(x, y. הנקודה שבה האילוץ האדום משיק לעקום הכחול היא נקודת מקסימום של (f(x, y לאורך עקומת האילוץ, מכיוון ש-d<sub>1</sub> > d<sub>2</sub>.
במתמטיקה, כופלי לגראנז' הם משתנים מלאכותיים המוספים לפונקציה ממשית בת כמה משתנים, על-מנת למצוא נקודות קיצון מקומיות של הפונקציה בכפוף לאילוצים. משתנים אלה קרויים על-שמו של המתמטיקאי האיטלקי ז'וזף לואי לגראנז', ונעשה בהם שימוש נרחב במתמטיקה, בפיזיקה (בפרט במכניקה אנליטית) ובחקר ביצועים לפתרון בעיות תכנון לא-ליניארי.

השיטה הבסיסית למציאת נקודות קיצון של פונקציה גזירה בעלת כמה משתנים, בתחום פתוח, היא להשוות את הנגזרות החלקיות לאפס. אכן, על פי משפט פרמה, הנגזרות החלקיות מתאפסות בכל נקודת קיצון של פונקציה גזירה בתחום פתוח. בתחום שאינו פתוח, עשויות להיות נקודות קיצון גם על השפה. אילוצים על המשתנים, הנתונים בצורת משוואה כגון <math>\ x^2+y^2+z^2=1</math>, הופכים את התחום לקבוצה סגורה, שכולה שפה, ובכך מונעים את השימוש הישיר בשיטת הנגזרות החלקיות. שימוש בכופלי לגראנז' הופך בעיה עם אילוצים לבעיה בלי אילוצים, ובכך מאפשר להשתמש בהשוואת הנגזרות לאפס.

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

== נכונות השיטה ==
השיטה של כופלי לגראנז' נכונה משום שבכל נקודת קיצון של פונקציה f ב-n משתנים על גבי יריעה המוגבלת על ידי אילוצים, הגרדיאנט של f הוא צירוף ליניארי של וקטורי הגרדיאנט של האילוצים באותה נקודה. בפרט, עבור n-1 אילוצים (המגדירים יחד עקומה ב-<math>\mathbb{R}^n</math>), קו הגובה של f (הניצב לגרדיאנט שלה) ישיק לעקומת האילוצים.

==תיאור השיטה==

שיטת כופלי לגראנז' הופכת את הבעיה של מציאת נקודות הקיצון של פונקציה בת <math>\ n</math> משתנים <math>\ f : D \rightarrow \mathbb{R}</math> (כאשר <math>\ D \subset \mathbb{R}^n</math> הוא תחום פתוח), בכפוף ל-<math>\ k</math> אילוצי שוויון מהצורה <math>\ g_i(x_1,x_2,...,x_n)=0</math>, לבעיה של מציאת נקודות הקיצון של פונקציה בת <math>\ n+k</math> משתנים ללא אילוצים. <math>\ n</math> משתנים הם משתנים של הבעיה המקורית ו- <math>\ k</math> משתנים הם כופלי לגראנז'.

השיטה היא להגדיר פונקציה חדשה:<math>
\begin{align}
& h(x_1, x_2, \ldots,\lambda_1, \lambda_2,\ldots \lambda_k) = \\[4pt]
 {} & f(x_1, x_2, \ldots) + \lambda_1 g_1(x_1, x_2, \ldots)+\lambda_2 g_2(x_1, x_2, \dots))+\cdots \lambda_k g_k(x_1, x_2, \ldots)
\end{align}
</math>

כאשר <math>\ \lambda_i\in \mathbb{R}</math> נקראים כופלי לגראנז. על מנת למצוא נקודת קיצון, נגזור את הפונקציה לפי המשתנים המקוריים - ונקבל <math>\ n</math>משוואות מהסוג <math>\ \frac {\partial h(x_1,x_2,..,x_n,\lambda_1,\lambda_2,...,\lambda_k)}{\partial x_i} = 0</math>, בנוסף ל-<math>\ k</math> האילוצים <math>\ g_i(x_1,x_2,...,x_n)=0</math>. הפתרונות למערכת המשוואות המתקבלות הן הנקודות החשודות כנקודות קיצון, שאותן יש לבדוק פרטנית בדרכים אחרות. סה"כ קיבלנו <math>\ n+k</math>משוואות, עבור <math>\ n+k</math>נעלמים.

==ההסיאן==

ההסיאן של מערכת המשוואות, תחת הנחות מסוימות, מזהה אילו נקודות חשודות הן נקודות מינימום או מקסימום, ואילו הן נקודות אוכף בלבד.

== דוגמאות==
* אנו רוצים למצוא את נקודות הקיצון של הפונקציה <math>\ f(x,y)=xy</math> בכפוף לאילוץ שהנקודות הן על המעגל <math>\ x^2+y^2=1</math>. נגדיר:
:: <math>\ h(x,y,\lambda) = xy + \lambda \left(x^2+y^2-1\right)=0</math>

:המשוואות שנקבל תהיינה:
:: <math>\ \frac{\partial h(x,y,\lambda)}{\partial x} =y + \lambda \frac{\partial \left(x^2+y^2-1\right)}{\partial x}=0</math>
:: <math>\ \frac{\partial h(x,y,\lambda)}{\partial y} =x + \lambda \frac{\partial \left(x^2+y^2-1\right)}{\partial y}=0</math>
::<math>\ \frac{\partial h(x,y,\lambda)}{\partial \lambda} = x^2+y^2-1=0</math>
:פתרון המשוואות ייתן
:: <math>\ y = - 2x \lambda </math>
:: <math>\ x = - 2y \lambda </math>
:ואז <math>\ \lambda = -\frac{y}{2x} </math> ו־<math>\ x^2 = y^2 </math> ו. בעזרת משוואת האילוץ נקבל
:: <math>\ x=\pm \sqrt{\frac{1}{2}}</math> ו־<math>\ y=\pm \sqrt{\frac{1}{2}}</math>.
* פחית היא גליל בנפח <math>\ V</math>. כמות חומר הגלם פרופורציונית לשטח הפנים של הגליל <math>\ A</math> ולכן נחפש את הרדיוס והגובה עבורם שטח הפנים של הגליל הוא מינימלי. לתיאור הגליל דרושים שני המשתנים, רדיוס <math>\ r</math> וגובה <math>\ h</math>. את נקודת הקיצון אנו צריכים למצוא עבור הפונקציה <math>\ A(r,h) = 2\pi r^2 + 2\pi r h</math>, כשהאילוץ הוא <math>\ V=\pi r^2 h \Rightarrow V-\pi r^2 h=0</math>. המשוואות המתקבלות הן:
:: <math>\ \frac{\partial A(r,h)}{\partial r} = - \lambda \frac{\partial {V- \pi r^2 h}}{\partial r}=0</math>
:: <math>\ \frac{\partial A(r,h)}{\partial h} = - \lambda \frac{\partial {V- \pi r^2 h}}{\partial h}=0</math>
: פתרונן נותן:
:: <math>\ 4 \pi r + 2\pi h = \lambda 2\pi r h </math>
:: <math>\ 2\pi r= \lambda \pi r^2 </math>
: ולפיכך, <math>\ \lambda = \frac 2 r </math> ו־<math>\ h= 2 r </math>. ניעזר באילוץ ונקבל <math>\ r= \left(\frac {V} {2\pi}\right)^{\frac 1 3}</math> ו־<math>\ h= \left(\frac {4V} {\pi}\right)^{\frac 1 3}</math>.

== ראו גם ==
* תכנון לא-ליניארי
* משפט קרוש-קון-טוקר 

==קישורים חיצוניים==

* 

קטגוריה:אופטימיזציה רציפה