- •(23) Эргодические и неэргодические случайные процессы. (Тихонов Харисов стр. 69-70)
- •(24) Спектральное описание случайных процессов. Случайный спектр. (Тихонов Харисов стр. 80-82)
- •(29) Методы одномерной оптимизации дихотомии и Фибоначчи.
- •(30) Методы одномерной оптимизации, использующие информацию о производной.
- •(31) Методы многомерной оптимизации.
- •Часть 3. (33-43)
- •(33) Методы многомерной оптимизации первого порядка.
- •(34) Методы многомерной оптимизации второго порядка.
(31) Методы многомерной оптимизации.
Постановка задач многомерной оптимизации
При математической формулировке задачи условной оптимизации целевую функцию выбирают с таким знаком, чтобы решение задачи соответствовало поиску минимума этой функции. Поэтому формулировку общей задачи математического программирования обычно записывают так:
где - множество возможных альтернатив, рассматриваемых при поиске решения задачи. Любую точку называют допустимым решением задачи математического программирования, а само множество – множеством допустимых решений или допустимым множеством. Точку , в которой функция достигает своего наименьшего значения, называют оптимальным решением задачи.
Задачу (1) в дальнейшем будем называть задачей минимизации целевой функции на множестве Q. Но целевая функция может и не достигать на Q наименьшего значения. Тогда говорят о точной нижней грани функции на этом множестве и вместо (1) используют запись:
Отличие этих записей в том, что в первом случае предполагается существование конкретной точки , в которой целевая функция достигает своего наименьшего значения на множестве Q, а во втором случае такая точка может и не существовать.
Сформулируем задачу многомерной безусловной оптимизации: найти минимум функции , при отсутствии ограничений на x, при этом – это скалярная целевая функция, непрерывно дифференцируемая.
Методы численного решения задач многомерной безусловной минимизации многочисленны и разнообразны. Условно их можно разделить на три больших класса в зависимости от информации, используемой при реализации метода.
1. Методы нулевого порядка, или прямого поиска, стратегия которых основана на использовании информации только о свойствах целевой функции.
2. Методы первого порядка, в которых при построении итерационной процедуры наряду с информацией о целевой функции используется информация о значениях первых производных этой функции.
3. Методы второго порядка, в которых наряду с информацией о значениях целевой функции и ее производных первого порядка используется информация о вторых производных функции.
(32) Методы многомерной оптимизации нулевого порядка.
В методах прямого поиска минимума целевой функции (или методах нулевого порядка) используют информацию только о значениях этой функции.
Рассмотрим 2 метода нулевого порядка:
1. метод Гаусса-Зейделя;
2. метод Хука-Дживса.
Метод Гаусса – Зейделя (на одной оси ищем минимальное значение, потом на другой)
В качестве направлений поиска используются координатные векторы Таким образом, в поиске по направлению меняется только переменная , остальные переменные фиксируются.
Задаём начальную точку . Рассматриваем направление поиска . Находим параметр из условий одномерной минимизации Обозначим промежуточную точку . Перейдём ко второму направлению . Находим параметр из условия одномерной оптимизации , обозначим , проходим по всем направлениям координатных осей, определяя Следующая точка . Рассматриваем её как стартовую, далее повторяем процесс поиска по направлениям координатных осей. Процесс поиска останавливаем при выполнении условия – заданная точность.
В качестве оптимального решения выбираем
Метод Хука-Дживса (тут чуть посложнее, ещё выбираем нужное направление)
Эффективность прямого поиска точки минимума ограниченной снизу целевой функции можно повысить, если на каждом k-м шаге поиска соответствующим образом выбирать направление спуска. Для этого на каждом k-м шаге выделяют предварительный этап исследующего поиска. Целью этого этапа является выбор направления спуска путем исследования поведения целевой функции в окрестности точки , найденной на предыдущем шаге. В результате выполнения этапа исследующего поиска находится точка , для которой . Направление спуска, завершающего k-й шаг поиска, определяется вектором .
Исследующий поиск заключается в поиске базовой точки. Перебираем точки вдоль координатных направлений, аналогично методу Гаусса - Зейделя. Если значение целевой функции в пробной точке не превышает значения в исходной, то шаг поиска рассматривается как успешный. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположном направлении. После перебора всех N координат исследующий поиск заканчивается. Полученная точка называется базовой.
Поиск по образцу заключается в реализации единственного шага из полученной базовой точки вдоль прямой, соединяющей её с предыдущей базовой точкой. На k-м шаге переходим к этапу спуска в направлении вектора , при этом . Следующая точка находится по формуле
Ускоряющий множитель λk находим методом одномерной оптимизации при этом , либо задаём постоянным, обычно полагаем .
На рисунке иллюстрируются этапы исследующего поиска и спуска для первых двух шагов поиска точки минимума целевой функции двух переменных при из начальной точки .