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

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

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

при виконанні умов
де  — функція, що мінімізується,  — функції обмежень-нерівностей і  — функції обмежень-рівностей.

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

Припустимо, що задана функція мети (функція значення якої слід мінімізувати)   і обмежуючі функції   і  .

Позначимо   підмножину   для елементів якої в обмеженнях-нерівностях виконується рівність   Припустимо, що дані функції є неперервно диференційованими в точці   . Якщо   є локальним мінімумом, що задовольняє деякі умови регулярності, то існують константи,   і   такі що виконуються властивості:

Стаціонарність
 
Допустимість
 
 
Двоїста допустимість
 
Спряженість
 

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

якщо для локального мінімуму   вектори   — лінійно незалежні, то в точці   виконуються умови Каруша — Куна — Такера.
  • Умови Мангасар'яна — Фромовіца. Якщо для локального мінімуму   існує вектор   для якого:
  1.  
  2.  
  3. Вектори   — лінійно незалежні,
то в точці   виконуються умови Каруша — Куна — Такера.

Достатні умови ред.

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

Див. також ред.

Література ред.

  • М. П. Моклячук Основи опуклого аналізу. К.:ТвіМС, 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.