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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Спряженість

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

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

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

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

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

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

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

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

В деяких випадках необхідні умови є також достатніми для оптимальності. Зокрема це відбувається якщо функція $f$ і обмеження-нерівності $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. ISBN 0-486-43227-0.
• J. Nocedal, S. J. Wright, Numerical Optimization. Springer Publishing. ISBN 978-0-387-30303-1.