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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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