kReese.net

Karush-קון-טאקר (EZ) תנאים, לפעמים המכונה קון-טאקר התנאים, תנאים כי בעיה תכנות קוי צורך להיפגש כדי להיות אופטימלי. התנאים KKT מרחיב את שיטת מכפילי Lagrangian ידי המאפשר אילוצי אי שוויון, בניגוד מכפילי לגראנז' אשר מאפשרים רק אילוצי שוויון.

הבה נבחן בעיה אופטימיזציה לא לינארית:

לצמצם $f(x)$
בכפוף: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

אנו נותנים $x^{*}$ לייצג את נקודת המינימום היחסי עבור הבעיה שלנו, אשר גם מספק כמה ההסמכה אילוץ. עם זאת, אז אנחנו יכולים להניח כי עבור כל אלמנט קיים וקטור $\lambda_j \left ( j = 1, \ldots, l \right )$ , איפה l מייצג את מספר אילוצי שוויון, ו $\mu_i\left ( i = 1, \ldots, m \right )$ , איפה מ ' מייצג את מספר אילוצי אי שוויון. אלה קבועים, $\lambda_j$ ו $\mu_i$ , נקראים מכפילי KKT.

על מנת התנאים KKT שיתקיים בעיה תכנות קוי (NLP), אז כל שלושת התנאים חייבים להתקיים [1-4]. חוזר ומציג שוב את הכדאיות Primal מה הבעיה מדינות, כי אי השוויון ואילוצים על שוויון $x^*$ חייבים להתקיים על מנת הבעיה להיות אופטימלי:

$\left.\begin{matrix} h\left ( x^* \right )=0\\ g\left ( x^* \right )\leq0 \end{matrix}\right\} \textrm{primal feasibility (PF)}$

התנאי השני הוא ידוע כתנאי את הכדאיות כפולה. בכך קובע תנאי, אלא verbosely, כי כל אלמנט $\mu_i$ חייב להיות גדול מאפס, וכי stationarity של הבעיה חייב להיות שווה 0.

$\left.\begin{matrix} \bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0\\ \lambda_i \in \mathbb{R}\\ \mu_i \geq 0 \end{matrix}\right\}\textrm{dual feasibility (DF)}$

Stationarity של הבעיה הוא:

$\bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0$

בעוד השניים האחרים הם פשוט תנאים אני ו מ ' חייבים לעמוד על מנת $x^*$ יהיה אופטימלי.

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

$\mu_i g_{i} \left ( x^* \right ) = 0$

כאשר שלושה תנאים אלו מתקיימים, פגשנו את התנאים KKT ואת הפתרון שלנו, $x^*$ , היא הפתרון האופטימלי לבעיה NLP. יש אולי אחד או יותר x במרחב אשר עומד בתנאים. כל נקודה במרחב את הבעיה שבה כל אלמנט שלאניו -מ ', כזה tuple (x, אני, מ ') לספק את התנאים KKT נקראים נקודות KKT. גזירת אילוצים אלה ניתן למצוא [1,2]

אילוצים כישורים

כאמור, את הנקודות שאנחנו בודקים צריך לפגוש כמה ההסמכה כדי נקודה שיש לקחת בחשבון. הכשרה רוב אילוץ ידוע הוא הכשרה לינארי אילוץ העצמאות (לליק), אשר פשוט קובע כי $h_{j}(x^*)$ ו $g_{i}(x^*)$ תלויות באופן ליניארי מהשני בנקודה $x^*$ . Mangasarian-Fromovitz אילוץ ההסמכה (MFCQ) באופן דומה קובע לליק עם תוספת של להיות חיובי lineraly עצמאי בבית $x^*$ . [5]

יש מוקדמות אילוץ אחר, עם זאת, להרגיע את לליק. במוקדמות האילוץ סלייטר ניתן להשתמש בעיות קמור. אם קיימת נקודה x כזה $h_{j}(x^*) =$ ו $g_{i}(x^*) < 0$ לכל i,j פעיל $x^*$ , אז התנאי צפחה מחזיקה. [5,6]

סוגים אחרים של מוקדמות אילוץ קיימים, אבל שלושת אלה נראים להיות הנפוץ ביותר KKT ההסמכה.

[1] קון, H. ואת טאקר, א, “קוי תכנות” PNAS של 2 ברקלי סימפוזיון 1951, pp. 481-492.
[2] Karush, וו, “ומינימום של פונקציות של מספר משתנים עם אילוצים כמו אי שוויון סייד”. M. Sc. מסה, אונ. of Chicago, שיקגו, Il, 1939.
[3] קון, ז. “Karush-קון-טאקר theorema”, לאינטרנט: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, אוני CDSEM. מנהיים, 2006.
[4]McCarl, ב. ו ספרין, ט, “אופטימיזציה תנאי קוי”, Ch. 12, יישומי תכנות מתמטי באמצעות מערכות אלגברית. לאינטרנט: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. קאראס, E. ו ריביירו, A. אילוצים הכשרה עבור תכנות לינארית, דווח טק, אונ. של פאראנה.
[6] להגיע, D. ו Zalinescu, ג. “על הצורך הכשרה תנאים מסוימים אילוצים בתכנות קמורה”, כתב העת של ניתוח קמורה, 11 (1), 2004. pp 95-110.

במדעי המחשב ג'ורנל הוראה

הודעות אחרונות

Karush-קון-טאקר תנאי

אילוצים כישורים