- •Основные понятия.
- •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. Принцип максимума в задаче о быстродействии.
- •Список литературы
1.2. Градиентные методы (продолжение)
Общая схема методов: xk+1 = xk - *f ( x k )
Оценим скорость сходимости для выпуклых функций:
Теорема:
Пусть f (x) дважды дифференцируема и
l*I 2f (x) L*I, где l>0, L>0 x (*), то есть f (x) – выпукла,
тогда при 0 2/L выполняется неравенство:
|| xk –x*|| || x0 –x*||*qk – геометрическая сходимость,
где q = max {|1-*l|,|1-*L |}, при этом min q() = (L-l)/(L+l)<1 и достигается при = *=2/(L+l).
Доказательство: Применим формулу
f (x+y)= f (x)+(x+*y)y d к производной:
f (xk)= f (x*) + 2f (x*+*(xk-x*))( xk-x*) d = Ak*( xk-x*),
где матрица Ak=2f(x*+*(xk-x*))d симметричная и неотрицательно определена.
Из (*) следует l*I Ak L*I. Из определения метода следует
|| xk+1 –x*|| = || xk – *f ( x k ) - x*|| = || xk – x* - * Ak( x k - x*)|| =
= || (I- *Ak)*( x k - x*)|| || I- *Ak ||*|| x k - x*|| (т.к (x,y) ||x||||y||)
Для любой симметричной матрицы А выполняется:
|| I- A|| = max {|1-1|,|1-k|}, где 1,k – соответственно наименьшее и наибольшее собственные числа (значения) матрицы А.
Поэтому || xk+1 –x*|| || xk –x*||*q, где q = max {|1-*l|,|1-*L |}
так как 0 2/L è 0< l <L, то |1-*l| <1, |1-*L |<1 q<1.
Найдем min q()
q()
max =q()
1-l
1-l
1
L-1 * l-1
1-l**= -(1-L*) *=2/(L+ l).
Тогда q(*) = (L-l) / (L+ l)
1.2.1. Градиентный метод с дроблением шага.
Как известно выбор постоянного шага может привести к осложнениям (см. стр.2).
Схема градиентного метода имеет вид xk+1 = xk - tk*f ( x k ). Если шаг выбрать с условием, что f(xk+1) - f(xk) -* tk * || f(xk)|| (*), где 0 < 1, то результат будет значительно лучше.
Иллюстрация:
Необходимо двигаться к х*. В начальной точке проводим касательную к линии уровня и делаем по перпендикуляру к касательной в этой точке, шаг соответствующей величины. Если оказываемся «далеко», то делим шаг пополам, проводим линию уровня, касательную и шагаем по перпендикуляру и т.д.
Алгоритм:
1.Выбираем t=const.
2.Проверяем выполнение соотношения (*).
3.Если выполняется, то вычисляем следующую точку; если не выполняется, тогда длину шага t делим на 2, проверяем (*) è так äалее.
Там, где f ( x ) = 0- останавливаемся.
Теорема(о градиентном метоле с дроблением шага)
Градиентный метод с дроблением шага обеспечивает следующее неравенство: || xk –x*|| const.*qk, где 0<q<1.
Без доказательства.
1.2.2. Метод наискорейшего спуска.
Определяет оптимальное значение шага на каждом такте.
Значение функции, полученное этим методом, меньше чем в предыдущем методе.
Характерная черта метода: градиенты функции в соседних точках ортогональны.
Доказать самостоятельно.
Графическая интерпретация:
В начальной точке проводим касательную к линии уровня и делаем шаг оптимальной величины в направлении перпендикуляра к касательной в данной точке. Получив новую точку, повторяем действия и так далее.
Теорема (о скорости сходимости метода наискорейшего спуска)
Скорость сходимости метода наискорейшего спуска - геометрическая.
, где(L,l -указаны ранее)