Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

В теорії оптимізації умови Каруша - Куна - Таккера ( англ. Karush - Kuhn - Tucker conditions , KKT) - необхідні умови розв'язання задачі нелінійного програмування. Щоб рішення було оптимальним, повинні бути виконані деякі умови регулярності. Метод є узагальненням методу множників Лагранжа. На відміну від нього, обмеження, що накладаються на змінні, являють собою не рівняння, а нерівності.


1. Історія

Кун і Таккер узагальнили метод множників Лагранжа (для використання при побудові критеріїв оптимальності для задач з обмеженнями у вигляді рівностей) на випадок загальної задачі нелінійного програмування з обмеженнями, як у вигляді рівностей, так і у вигляді нерівностей [1].

Необхідні умови локального мінімуму для задач з обмеженнями досліджуються давно. Одним з основних залишається запропонований Лагранжем перенесення обмежень у цільову функцію. Умови Куна-Таккера теж виведені з цього принципу [2].


2. Постановка завдання

Розглянемо задачу нелінійної оптимізації.

\ Min \ limits_ {x \ in X} f (x)

при умовах g_i (x) \ leqslant 0, \; i = 1 \ ldots m . Вільям Каруш в своїй дипломній роботі знайшов необхідні умови в загальному випадку, коли накладаються умови можуть містити і рівняння, і нерівності. Незалежно від нього до тих же висновків прийшли Гарольд Кун і Альберт Таккер.

3. Необхідні умови мінімуму функції

Якщо \ Hat {x} \ in \ arg \ min f при накладених обмеженнях - рішення задачі, то знайдеться ненульовий вектор множників Лагранжа \ Lambda \ in \ R ^ m такий, що для функції Лагранжа L (x) = f (x) + \ sum ^ m_ {i = 1} \ lambda_i g_i (x) виконуються умови:

  • стаціонарності: \ Min_x L (x) = L (\ hat {x}) ;
  • доповнюючої нежорстких: \ Lambda_i g_i (\ hat {x}) = 0, \; i = 1 \ ldots m ;
  • неотрицательности: \ Lambda_i \ geqslant 0, \; i = 1 \ ldots m .

4. Достатні умови мінімуму функції

Перераховані необхідні умови мінімуму функції в загальному випадку не є достатніми. Існує кілька варіантів додаткових умов, які роблять їх достатніми.

4.1. Проста формулювання

Якщо для допустимої точки \ Hat {x} виконуються умови стаціонарності, яка доповнює нежорстких і неотрицательности, а також \ Lambda_1> 0 , То \ Hat {x} \ in \ arg \ min f .

4.2. Більш слабкі умови

Якщо для допустимої точки \ Hat {x} виконуються умови стаціонарності, яка доповнює нежорстких і неотрицательности, а також \ Exists \ tilde {x}: g_i (\ tilde {x}) <0, \; i = 1 \ ldots m (Умова Слейтера), то \ Hat {x} \ in \ arg \ min f .

Примітки

  1. Умови Куна-Таккера - www.monographies.ru/57-2327
  2. Жілініскас А., Шатляніс В. Пошук оптимуму: комп'ютер розширює можливості. - М.: Наука, 1989, с. 76, ISBN 5-02-006737-7



Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Хорватська куна
Куна (грошова одиниця)
Стандартні умови
Нормальні і стандартні умови
Початкові і граничні умови
Умови Коші - Рімана
Граничні умови для електромагнітного поля
© Усі права захищені
написати до нас
Рейтинг@Mail.ru