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

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

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

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

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

$g_i(x)⩽0,h_j(x)=0$

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

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

Припустимо, що задана функція мети (функція значення якої слід мінімізувати) $f:{ℝ}^n\to ℝ$ і обмежуючі функції $g_i:{ℝ}^n\to ℝ$ і $h_j:{ℝ}^n\to ℝ$.

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

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

$\mathrm{\nabla }f(x^{*})+\sum _{i=1}^m{\mu }_i\mathrm{\nabla }{g}_i(x^{*})+\sum _{j=1}^l{\lambda }_j\mathrm{\nabla }{h}_j(x^{*})=0,$

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

$g_i(x^{*})⩽0,i=1,\dots ,m$

$h_j(x^{*})=0,j=1,\dots ,l$

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

${\mu }_i⩾0,i=1,\dots ,m$

Спряженість

${\mu }_i{g}_i(x^{*})=0,i=1,\dots ,m.$

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

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

якщо для локального мінімуму $x^{*}$ вектори $\mathrm{\nabla }{g}_i(x^{*}),i\in 𝒜(x^{*}),\mathrm{\nabla }{h}_j(x^{*})j=1,\dots ,l$ — лінійно незалежні, то в точці $x^{*}$ виконуються умови Каруша — Куна — Такера.

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

1. $\mathrm{\nabla }{g}_i(x^{*}{)}^{T}d>0,i\in 𝒜(x^{*})$
2. $\mathrm{\nabla }{h}_j(x^{*}{)}^{T}d=0,j=1,\dots ,l$
3. Вектори $\mathrm{\nabla }{h}_j(x^{*}),j=1,\dots ,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.