شرایط کاروش–کون–تاکر

در بهینه‌سازی ریاضی، شرایط کاروش–کون–تاکر (KKT) شرایط لازم بهینگی مرتبه اول برای یک جواب در مسئله بهینه‌سازی محدب غیرخطی می‌باشند. هنگامی که مسئله اولیه محدب باشند شرایط KKT برای نقاط بهینه مسئله اولیه و مسئله دوگان صادق هستند، یا به عبارت دیگر فاصله دوگانی صفر می‌باشد. شرایط KKT نقش مهمی در بهینه‌سازی بازی می‌کند. موارد بسیار کمی هست که بتوان شرایط KKT را به صورت تحلیلی حل کرد. در بیشتر موارد باید از الگوریتم‌های بهینه‌سازی استفاده کرد.^[۱]

مسئله بهینه‌سازی غیرخطی

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

${\displaystyle {\begin{aligned}\mathbf {minimize} \quad &f(x)\\\mathrm {subject\ to} \quad &g_{i}(x)\leq 0;\quad i\in \left\{1,\dots ,m\right\}\\&h_{j}(x)=0;\quad j\in \left\{1,\dots ,\ell \right\}\end{aligned}}}$mtfc

شرایط KKT و دوگان

شرایط KKT مجموعه شرایط لازم بهینگی مرتبه اول برای مسائل بهینه سازی مقید است. شرایط KKT تعمیم ضرایب لاگرانژ برای قیدهای مساوی و نامساوی در یک مساله بهینه سازی مقید است.

اگر دوگان قوی برقرار باشد و مسئله اولیه محدب باشد، شرایط KKT برای شرایط بهینگی لازم و هم کافی می باشد.

شرایط KKT در مسئله بهینه‌سازی محدب

KKT در مسائل بهینه‌سازی محدب دارای چهار شرط زیر است:

۱-مسئله اولیه شدنی باشد

${\displaystyle g_{i}(x^{*})\leq 0,{\text{ for }}i=1,\ldots ,m}$

${\displaystyle h_{j}(x^{*})=0,{\text{ for }}j=1,\ldots ,\ell \,\!}$

۲-مسئله دوگان شدنی باشد

${\displaystyle \mu _{i}\geq 0,{\text{ for }}i=1,\ldots ,m}$

۳-شرط Complementary slackness برقرار باشد

${\displaystyle \mu _{i}g_{i}(x^{*})=0,{\text{ for }}\;i=1,\ldots ,m.}$

۴-شرط ایستا برقرار باشد

${\displaystyle -\nabla f(x^{*})=\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\nabla h_{j}(x^{*}),}$

یک x,λ,μ در چهار رابطه فوق به دست می‌آید، که این مقادیر پاسخ‌های بهینه مسئله اولیه و دوگان هستند.^[۲]