kReese.net

Karush - کوهن تاکر (KKT) شرایط, گاهی اوقات به عنوان شرایط کوهن - تاکر اشاره, شرایط است که یک مشکل برنامه ریزی غیر خطی نیاز به ملاقات به منظور بهینه. KKT شرایط گسترش روش لاگرانژی افزایش دهندگان اجازه می دهد برای محدودیت های نابرابری, به عنوان دو طرف لاگرانژ که فقط اجازه می دهد محدودیت برابری مخالف.

اجازه دهید یک مسئله بهینه سازی غیر خطی در نظر بگیریم:

به حداقل رساندن $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]. restates امکان سنجی اولیه چه مشکل ایالات, که نابرابری و محدودیت های برابری در $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$

در حالی که دو نفر دیگر به سادگی شرایطی که L و متر باید برآورده و به منظور $x^*$ مطلوب باشد.

شرط سوم است که باید برآورده شده است به عنوان شلی مکمل شناخته شده شده. این وضعیت به سادگی بیان می کند که برای هر MU و محدودیت نابرابری مربوطه آن, محصول از این دو باید در صفر:

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

هنگامی که این سه شرط در, ما با شرایط KKT و راه حل ما, $x^*$ , یک راه حل مناسب برای مشکل NLP. وجود دارد شاید بیش از یک X در فضای که واجد شرایط. هر نقطه در فضا مشکل که در آن هر عنصر ازLومتر, به طوری که تاپل (X, L, متر) برآورده KKT شرایط نامیده می شوند نقطه KKT. اشتقاق از این محدودیت ها را می توان در یافت [1,2]

صلاحیت محدودیت

همانطور که قبلا ذکر شد, نقاط است که ما در حال آزمایش نیاز به مدرک تحصیلی به منظور آشنایی با برخی از نقطه به نقطه در نظر گرفته شود. ترین و شناخته شده صلاحیت محدودیت تحصیلی محدودیت استقلال خطی (LICQ), که به سادگی بیان می کند که $h_{j}(x^*)$ و $g_{i}(x^*)$ خطی مستقل از دیگری در نقطه $x^*$ . صلاحیت محدودیت Mangasarian Fromovitz (MFCQ) دولتها به طور مشابه LICQ با علاوه بر این از که مثبت lineraly مستقل در $x^*$ . [5]

با این حال دیگر مسابقات مقدماتی محدودیت است که باعث شل شدن LICQ وجود دارد. اسلاتر مقدماتی محدودیت را می توان در مشکلات محدب استفاده می شود. اگر وجود دارد به طوری که نقطه X وجود دارد $h_{j}(x^*) =$ و $g_{i}(x^*) < 0$ برای همه من,J فعال در $x^*$ , سپس وضعیت تخته سنگ نگه می دارد. [5,6]

انواع دیگر از مقدماتی محدودیت وجود دارد, اما این سه به نظر می رسد می شود بیشتر به به طور معمول در احراز صلاحیت KKT استفاده می شود.

[1] کوهن, H. و هم Tucker, A., “برنامه ریزی غیر خطی” مجموعه مقالات سمپوزیوم برکلی 2 1951, ص. 481-492.
[2] Karush, W., “حداقل از توابع چند متغیر با نابرابری از جمله موانع جانبی”. کارشناسی ارشد. پایان نامه, دانشگاه. of Chicago, شیکاگو, Il, 1939.
[3] کوهن, M. “قضیه Karush - کوهن تاکر”, اینترنت: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM انگلستان. مانهایم, 2006.
[4]McCarl, B. و Spreen, T., “شرایط بهینه سازی غیر خطی”, کانال. 12, برنامه نویسی ریاضی کاربردی با استفاده از سیستم های جبری. اینترنت: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. Ribeiro و, A. صلاحیت ارجاع محدودیت برای برنامه ریزی غیر خطی, TECH گزارش, دانشگاه. از پارانا.
[6] رسیدن, D. و Zalinescu, C. “بر ضرورت برخی از شرایط تحصیلی محدودیت در برنامه نویسی محدب”, مجله آنالیز محدب, 11 (1), 2004. ص 95-110.

مجله علوم کامپیوتر و آموزش

ارسال های جدید

شرایط Karush - کوهن - تاکر

صلاحیت محدودیت