در بهینهسازی ریاضی ، شرایط کاروش–کون–تاکر (KKT) شرایط لازم مرتبه اول برای یک راه حل در مسئله بهینهسازی محدب غیرخطی میباشند. هنگامی که مسئله اولیه محدب باشند شرایط KKT برای نقاط بهینه مسئله اولیه و مسئله دوگان صادق هستند، یا به عبارت دیگر فاصله دوگانی صفر میباشد. شرایط KKT نقش مهمی در بهینهسازی بازی میکند. موارد بسیار کمی هست که بتوان شرایط KKT را به صورت تحلیلی حل کرد. در بیشتر موارد باید از الگوریتمهای بهینهسازی استفاده کرد.[ ۱]
مسئله بهینهسازی غیرخطی
ویرایش
مسئله بهینهسازی غیرخطی به شکل زیر را در نظر بگیرید:
m
i
n
i
m
i
z
e
f
(
x
)
s
u
b
j
e
c
t
t
o
g
i
(
x
)
≤
0
;
i
∈
{
1
,
…
,
m
}
h
j
(
x
)
=
0
;
j
∈
{
1
,
…
,
ℓ
}
{\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 در مسائل بهینهسازی محدب دارای چهار شرط زیر است:
۱-مسئله اولیه شدنی باشد
g
i
(
x
∗
)
≤
0
,
for
i
=
1
,
…
,
m
{\displaystyle g_{i}(x^{*})\leq 0,{\text{ for }}i=1,\ldots ,m}
h
j
(
x
∗
)
=
0
,
for
j
=
1
,
…
,
ℓ
{\displaystyle h_{j}(x^{*})=0,{\text{ for }}j=1,\ldots ,\ell \,\!}
۲-مسئله دوگان شدنی باشد
μ
i
≥
0
,
for
i
=
1
,
…
,
m
{\displaystyle \mu _{i}\geq 0,{\text{ for }}i=1,\ldots ,m}
۳-شرط Complementary slackness برقرار باشد
μ
i
g
i
(
x
∗
)
=
0
,
for
i
=
1
,
…
,
m
.
{\displaystyle \mu _{i}g_{i}(x^{*})=0,{\text{ for }}\;i=1,\ldots ,m.}
۴-شرط ایستا برقرار باشد
−
∇
f
(
x
∗
)
=
∑
i
=
1
m
μ
i
∇
g
i
(
x
∗
)
+
∑
j
=
1
ℓ
λ
j
∇
h
j
(
x
∗
)
,
{\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,λ,μ در چهار رابطه فوق به دست میآید، که این مقادیر پاسخهای بهینه مسئله اولیه و دوگان هستند.[ ۲]
↑ Boyd, Stephen, and Lieven Vandenberghe (۲۰۰۴ ). Convex optimization . Cambridge university press.
↑ Edwin Kah Pin Chong,An Introduction to Optimization,September 23, 2011