- •Основные понятия.
- •1. Безусловная оптимизация (многомерные функции)
- •1.1 Методы первого порядка (градиентные методы)
- •1.1.1. Градиентный метод с постоянным шагом
- •1.1.2. Выпуклые функции и множества
- •Теорема
- •Определение.
- •Без доказательства
- •2.Теорема:
- •1.2. Градиентные методы (продолжение)
- •1.2.1. Градиентный метод с дроблением шага.
- •1.2.2. Метод наискорейшего спуска.
- •Без доказательства
- •1.2.3. Масштабирование
- •1.3. Метод Ньютона.
- •1.4. Многошаговые ( двухшаговые ) методы.
- •1.3.1. Метод тяжелого шарика
- •1.3.2. Метод сопряженных градиентов
- •1.3.3. Модификация Полака-Ривьера
- •1.5. Квазиньютоновские методы
- •1.6. Методы нулевого порядка (методы прямого поиска)
- •1.6.1. Методы аппроксимации
- •Метод покоординатного спуска
- •1.6.3. Метод симплексов (Нелдера-Мида)
- •1.6.4. Метод Пауэлла (сопряженных направлений)
- •1.7. Методы прямого поиска в задачах одномерной минимизации.
- •1.7.1. Метод квадратичной интерполяции.
- •1.7.2. Метод дихотомии ( половинного деления.).
- •1.7.3. Метод «золотого» сечения.
- •1.7.4. Метод Фибоначчи.
- •2. Условная минимизация.
- •2.1 Задача нелинейного программирования.
- •2.1.1. Ограничения типа равенства.
- •2.1.2. Ограничения типа неравенств.
- •2.2. Задача выпуклого программирования
- •2.3. Методы условной минимизации.
- •2.3.1. Метод проекции градиента.
- •2.3.2. Метод условного градиента.
- •2.3.3. Метод модифицированной функции Лагранжа.
- •2.3.4. Метод штрафных функций.
- •2.4. Двойственность звп
- •2.4.1. Двойственность злп
- •3. Линейное программирование
- •3.1. Основные понятия
- •3.2. Геометрическая интерпретация злп.
- •3.3. Условие оптимальности для злп.
- •3.4. Базис и базисное решение.
- •3.5. Симплекс - метод решения злп.
- •3.6 Транспортная задача
- •3.5.1. Построение первоначального опорного плана.
- •3.5.2. Построение оптимального плана. Метод потенциалов.
- •4. Решение переборных задач.
- •4.1. Метод ветвей и границ.
- •4.1.1. Задача о коммивояжере.
- •4.2. Динамическое программирование.
- •4.2.1. Абстрактная схема.
- •4.2.2. Вывод уравнения Беллмана.
- •4.2.3. Методика применения функции Беллмана для решения исходной задачи.
- •4.2.4. Примеры задач динамического программирования
- •5. Вариационное исчисление (ви)
- •5.1. Уравнение Эйлера-Лагранжа.
- •5.1.1. Частные случаи уравнения Эйлера-Лагранжа.
- •5.1.2. Задача о брахистохроне.
- •5.2. Вариационные задачи на условный экстремум.
- •5.2.1. Модельные задачи на условный экстремум.
- •6. Принцип максимума Понтрягина ( на примере задачи оптимального управления ).
- •6.1. Принцип максимума в задаче о быстродействии.
- •Список литературы
2.3.2. Метод условного градиента.
В очередной точке xkлинеаризуют функциюf(x) (в этом «условность» метода, то есть линеаризация и есть «условие» в названии). Затем решают задачуminлинейной функции наXи найденную точкуиспользуют для выбора направления движения.
При этом предполагается:
Задача минимизации линейной функции на Xимеет решение.
Это решение может быть найдено достаточно просто, лучше всего в явной форме.
Нужно указать правило выбора k. Можноkопределить из условия наискорейшего спуска :
В этом случае последовательность xkсходится к специальной точке. В частности для гладких функцийfверно:f(x*)-f* =o(1/k), гдеf* =minf(x) на множествеX.
2.3.3. Метод модифицированной функции Лагранжа.
Функцией Лагранжа в ЗВП называется функция
(x ,) = f(x)+f(x) + (,g(x)), где i0.
Выше была доказана теорема о седловой точке:
Если выполняется соотношение
(x* ,)(x* ,*)(x,*)xRn,0,
то точка x* является оптимальной точкой задачи выпуклого программирования.
Это соотношение можно записать иначе:
(*)(x* ,*) =(x,) =(x,) =f(x*)
Если назвать xпрямыми переменными, адвойственными, то видно, что прямые и двойственные переменные равноправны.
Теорема Куна- Таккера позволяет исходную задачу заменить задачей отыскания седловой точки функции Лагранжа, то есть задачи вида (x,).
Метод Эрроу-Гурвица ориентирован на поиск седловой точки функции (x,).
Метод Эрроу- Гурвица
Сходимость таких методов затруднена в общей ситуации.
Метод модифицированной функции Лагранжа обладает лучшими характеристиками по сравнению с предыдущими методами.
Определим - модифицированная функция Лагранжа:
.
некоторый параметр (штраф)
+ - взятие положительной части.
Свойства модифицированной функции Лагранжа.
Если +k g(x)>0,то
- добавка (штраф) за то, чтоg(x)>0.
(функция Лагранжа),
иначе
Метод модифицированной функции Лагранжа.
Метод сходится к (x* ,*) со скоростью геометрической прогрессии.
2.3.4. Метод штрафных функций.
Идея метода: Сведение задачи с ограничениями к последовательности задач без ограничений.
ЗНП:
min f(x), xX,
X = {xRn, gi(x) 0, i = 1...m}
Определение:
Функция (x), определенная и непрерывная всюду в Rn , называется штрафной функцией для рассматриваемой задачи с ограничениями, если:
Строится однопараметрическое семейство функций:
, где - скалярный параметр, принимающий строго положительные значения.
Алгоритм метода штрафных функций:
Выбираем убывающую последовательность положительных чисел, такую, что .
Сопоставляем каждому к из этой последовательности соответствующую функцию семейства (x,). Получаем последовательность функций (x,1),..., (x,k).
Пусть для каждой функции этой последовательности может быть решена задача безусловной минимизации (одним из рассмотренных ранее методов) :
.
Оказывается, что при некоторых условиях последовательность оптимальных точек для задач без ограничений может сходиться к оптимальной точке для исходной задачи с ограничениями: на Х.
Применяются различные штрафные функции. Наиболее распространена следующая штрафная функция:
, где - «срезка» функции:
=0, если 0
=, если>0
или