Умови Каруша-Куна-Такера

Умови Каруша — Куна — Такера — необхідні умови оптимальності розв'язку математичної задачі нелінійного програмування при виконанні деяких умов регулярності^[⇨]. Названі на честь авторів: Вільяма Каруша, ^[en] і ^[en].

Нехай маємо наступну задачу оптимізації:

${\displaystyle \min \limits _{x}f(x)}$

при виконанні умов

${\displaystyle g_{i}(x)\leqslant 0,h_{j}(x)=0}$

де ${\displaystyle f(\cdot )}$ — функція, що мінімізується, ${\displaystyle g_{i}(\cdot )\ (i=1,\ldots ,m)}$ — функції обмежень-нерівностей і ${\displaystyle h_{j}(\cdot )\ (j=1,\ldots ,l)}$ — функції обмежень-рівностей.

Необхідні умови

Припустимо, що задана функція мети (функція значення якої слід мінімізувати) ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ і обмежуючі функції ${\displaystyle g_{i}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ і ${\displaystyle h_{j}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$.

Позначимо ${\displaystyle {\mathcal {A}}(x^{*})}$ підмножину ${\displaystyle \{1,\ldots ,m\}}$ для елементів якої в обмеженнях-нерівностях виконується рівність ${\displaystyle g_{i}(x)=0.}$ Припустимо, що дані функції є неперервно диференційованими в точці ${\displaystyle x^{*}}$ . Якщо ${\displaystyle x^{*}}$ є локальним мінімумом, що задовольняє деякі умови регулярності, то існують константи, ${\displaystyle \mu _{i}\ (i=1,\ldots ,m)}$ і ${\displaystyle \lambda _{j}\ (j=1,\ldots ,l)}$ такі що виконуються властивості:

Стаціонарність

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

Допустимість

${\displaystyle g_{i}(x^{*})\leqslant 0,\quad i=1,\ldots ,m}$

${\displaystyle h_{j}(x^{*})=0,\quad j=1,\ldots ,l\,\!}$

Двоїста допустимість

${\displaystyle \mu _{i}\geqslant 0,\quad i=1,\ldots ,m}$

Спряженість

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

Умови регулярності

• Найпоширенішою умовою регулярності є умова лінійної незалежності градієнтів:

якщо для локального мінімуму ${\displaystyle x^{*}}$ вектори ${\displaystyle \nabla g_{i}(x^{*}),\quad i\in {\mathcal {A}}(x^{*}),\quad \nabla h_{j}(x^{*})\quad j=1,\ldots ,l\,\!}$ — лінійно незалежні, то в точці ${\displaystyle x^{*}}$ виконуються умови Каруша — Куна — Такера.

• Умови Мангасар'яна — Фромовіца. Якщо для локального мінімуму ${\displaystyle x^{*}}$ існує вектор ${\displaystyle d\in \mathbb {R} ^{n},}$ для якого:

1. ${\displaystyle \nabla g_{i}(x^{*})^{T}d>0,\quad i\in {\mathcal {A}}(x^{*})}$
2. ${\displaystyle \nabla h_{j}(x^{*})^{T}d=0,\quad j=1,\ldots ,l}$
3. Вектори ${\displaystyle \nabla h_{j}(x^{*}),\quad j=1,\ldots ,l\,\!}$ — лінійно незалежні,

то в точці ${\displaystyle x^{*}}$ виконуються умови Каруша — Куна — Такера.

Достатні умови

В деяких випадках необхідні умови є також достатніми для оптимальності. Зокрема це відбувається якщо функція ${\displaystyle f}$ і обмеження-нерівності ${\displaystyle g_{j}}$ є неперервно диференційовними опуклими функціями, а обмеження-рівності є афінними функціями. Ця ж властивість виконується також якщо функція мети і обмеження-нерівності є так званими інвексними функціями.

Див. також

• Лема Фаркаша
• Умова Слейтера

Література

• М. П. Моклячук Основи опуклого аналізу. К.:ТвіМС, 2004. — 240с.
• R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of Optimization Theory and Applications, vol. 125, no2, pp. 473—485 (2005).
• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. .
• J. Nocedal, S. J. Wright, Numerical Optimization. Springer Publishing. .