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

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

$\min\limits_x f(x)$

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

$g_i(x) \le 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^*) \le 0, \quad i = 1, \ldots, m$

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

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

$\mu_i \ge 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 \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.