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

Матеріал з Вікіпедії — вільної енциклопедії.
Версія від 11:00, 4 червня 2020, створена Vlasenko D (обговорення | внесок) (оформлення)
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

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

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

якщо для локального мінімуму вектори  — лінійно незалежні, то в точці виконуються умови Каруша — Куна — Такера.
  • Умови Мангасар'яна — Фромовіца. Якщо для локального мінімуму існує вектор для якого:
  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.