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

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

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

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

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

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

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

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

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

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

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

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

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

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

Література[ред.ред. код]

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