Нелинейное программирование Практическое занятие 2. - презентация

1 Нелинейное программирование Практическое занятие 2

2 Тема занятия Теория Куна-Таккера

3 Общий вид задачи НЛП (*)

4 Теория Куна-Таккера Существуют различные виды критериев оптимальности (необходимых и достаточных условий оптимальности ) для задачи (*) : –Условия Куна –Таккера 1-го порядка –Условия Куна –Таккера 2-го порядка –Рассмотренные условия оптимальности Лагранжа 1-го порядка –Условия оптимальности, в которых используются правильные штрафные функции

5 Условия Куна –Таккера 1-го порядка (в дифференциальной форме) Необходимое условие – Пусть x* - локальное либо глобальное решение задачи (*) –Ограничение g i (x) называется активным в точке x*, если оно выполняется в ней как строгое равенство, то есть если g i (x*) = 0

6 Условия Куна –Таккера 1-го порядка (в дифференциальной форме) Необходимое условие – пусть функции f(x), g i (x), h i (x) – дифференцируемые в точке x*. – Предположим, что выполняется условие линейной независимости векторов g i (x*) и h i (x*). – Тогда вектор x* и произвольно выбранные векторы и u удовлетворяют условиям Куна -Таккера, а именно:

7 Условия Куна –Таккера 1-го порядка (в дифференциальной форме) Необходимые условия Куна -Таккера (1)

8 Условия Куна –Таккера 1-го порядка (в дифференциальной форме) Необходимые условия Куна –Таккера –Условия Куна -Таккера в форме (1) означают, что в точке x* (локального либо глобального решения) антиградиент целевой функции можно представить в виде линейной комбинации с неотрицательными коэффициентами градиентов функций, задающих активные ограничения в виде неравенств, и градиентов функций, задающих ограничения в виде равенств, т.е в виде линейных комбинаций с неотрицательными коэффициентами внешних нормалей к активным ограничениям в точке x*.

9 Условия Куна –Таккера 1-го порядка (в дифференциальной форме) Достаточное условие – Если функция функции f(x), g i (x) дифференцируемые и выпуклые в точке x*, функции h i (x) – линейные и для точки x* выполняются необходимые условие Куна-Таккера (1) или (1) – то x* глобальное решение задачи (*)

10 Теория Куна-Таккера Задание 1

11 Теория Куна-Таккера Задание 1 –Решить задачу геометрически –Исследовать выполнение условий Куна-Таккера в «угловых» точках Аналитически Геометрически –«Написать» схему решения задачи с помощью условий Куна- Таккера

12 Теория Куна-Таккера Задание 2

13 Теория Куна-Таккера Задание 2 –Решить задачу геометрически –Исследовать выполнение условий Куна-Таккера в «угловых» точках Аналитически Геометрически –«Написать» схему решения задачи с помощью условий Куна- Таккера

14 Теория Куна-Таккера Задание 3

15 Теория Куна-Таккера Задание 3 –Решить задачу геометрически –Исследовать выполнение условий Куна-Таккера в «угловых» точках Аналитически Геометрически –«Написать» схему решения задачи с помощью условий Куна- Таккера

16 Тема следующего занятия Одномерные методы поиска

17 Спасибо за внимание