Лабораторная работа: Методы оптимизации функций многих переменных

, метод Ньютона.

Контрольные вопросы:

Объяснить алгоритмы следующих методов

Метод конфигураций (Хука-Дживса).

Метод деформируемого многогранника (Нелдера Мида).

Метод наискорейшего спуска.

Метод сопряженных направлений и его модификации.

Метод Ньютона и его модификации.

Метод дробления шага.

Лабораторная работа № 2.

1. Методы условной оптимизации

Цель лабораторной работы - закрепление навыков аналитического решения задач оптимизации со смешанными ограничениями с использованием теоремы Куна-Таккера, нахождение седловой точки функции Лагранжа, использование теории двойственности для оценки чувствительности решения задачи оптимизации.

1.1 Теоретический обзор. Решение задачи минимизации со смешанными ограничениями

Общая задача нахождения экстремума функции при наличии ограничений - равенств и ограничений - неравенств записывается в следующем виде:

f (x) → extr, (6)

x ÎX = {x ÎEⁿ : g_i (x ) ≤0, i =1,2,…,r ; g_i (x ) =0, i =r +1, …, m , m -r <n },

где среди функций f ( x) и g_i ( x) могут быть нелинейные.

Активные ограничения - неравенства в точке х* ─ это ограничения, которые выполняются в данной точке в виде равенства.

Пассивные ограничения - неравенства в точке х* ─ это ограничения, которые выполняются в данной точке в виде строгого неравенства.

Если градиенты активных ограничений-неравенств и ограничений-равенств в точке х* линейно независимы, то говорят, что в оптимальной точке выполнено условие регулярности.

Обобщенная функция Лагранжа для задачи со смешанными ограничениями задается как

L ( x, λ₀ , λ) = λ₀ f ( x) + λ_i g_i ( x). ( 7)

При выполнении условия регулярности λ₀ ≠0 и можно положить этот коэффициент равным 1.

Теорема Куна - Таккера (дифференциальная форма необходимого условия минимума). Пусть точка х* - точка локального минимума в задаче математического программирования (6), функцииf, g_{r +1} ,…, g_m дважды непрерывно дифференцируемы в точке х , функции g₁ ,…, g_r дважды непрерывно дифференцируемы в некоторой окрестности точки x . Тогда существует число и вектор такие, что выполняются следующие условия:

условие стационарности обобщенной функции Лагранжа по х :

grad_x L (x*, ,) =0;

условие нетривиальности:

² +² >0,т.е. хотя бы один из множителей Лагранжа отличен от нуля;

условие неотрицательности:

≥0, ≥0, i =1, …, r ,

т.е. множители Лагранжа, соответствующие целевой функции и ограничениям - неравенствам, неотрицательны;