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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

\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.