Глава 2. Численные методы поиска безусловного экстремума
§4. Принципы построения численных методов поиска безусловного экстремума.
Аналитические методы не работают для подавляющего числа задач. Причинами являются: разрывность производных, сложностью решения получаемой системы нелинейных уравнений, неаналитическим или даже неявным заданием функции. Поэтому применяются численные методы.
Большинство
численных методов являются итерационными:
при заданной начальной точке
пошагово генерируются точки
последовательности
,
точнее
,
в которых значения функции сходятся к
минимуму:
.
Достаточно часто
итерационная последовательность
строиться по формуле
,
где
– направление движения (спуска) и
величина шага.
Для выполнения условия убывание функции необходимо
Отсюда видно, что
большой класс образуют методы, где
определяется градиентом функции и его
отдельными составляющими.
Величина шага часто определяется из условия
Сходящаяся к
минимуму функции f
последовательность называется
«минимизирующей», а в случае сходимости
,
к точке
,
эта точка называется точкой минимума.
В зависимости от наибольшего порядка производных, используемых в методе, численные методы делятся на методы нулевого, первого и второго порядков.
§5.1. Методы нулевого порядка в одномерном случае.
5.1.1 Постановка задачи и стратегия поиска
Большинство методов предполагает нахождение аргумента в интервале и унимодальность (т.е. наличие единственного локального минимума на этом интервале) функции.
Замечания. 1) Непрерывная строго выпуклая функция – унимодальна, 2) Методы одномерной оптимизации широко используются при нахождении шага интерационного процесса.
Стратегия методов заключается в выборе итерационных точек. Она может быть пассивной, когда все точки заданы заранее, или активной, когда точки определяются в процессе функционирования метода.
Последовательная стратегия имеет следующие способы реализации:
Применение квадратичной и кубической интерполяции для выбранных точек и поиска минимума построенной интерполяционной кривой в качестве текущего приближения искомого минимума.
Построение последовательности вложенных друг в друга интервалов, содержащих точку минимума.
Стратегия состоит из трёх этапов:
Выбор начального интервала.
Построение последовательности интервалов, содержащих минимум.
Проверку условия окончания процесса поиска.
Алгоритм Свенна
[Swann
W.H.]
определения начального интервала
.
Задать произвольно следующие параметры: номер
,
начальную точку
,
величину шага
.Вычислить значения функции в трёх точках:
.Проверить условие окончания:
;
;условие окончания не выполняется – перейти к шагу 4.
Определить величину
:
;
;
Найти следующую точку
.Проверить условие убывания функции:
;
;k=k+1 и перейти к шагу 5;
.
При последовательной стратегии вычисляется функция в двух точках текущего интервала и на основании унимодальности отбрасывается левая или правая часть интервала.
5.1.2 Метод равномерного поиска
Задать
– начальный интервал, N
– число точек, где вычисляется функция
f(x).
Точки – равноотстоящие. Делаем:
.
5.1.3 Метод деления интервала пополам
Задать
– начальный интервал, l
– требуемая точность, k=0.
Вычислить точки
.
Сравнить эти значения в трёх точках:
;
;
.
5.1.4 Метод дихотомии
Идея метода состоит
в разделении интервала области определения
функции
на две равные части и сравнения значения
функции в двух точках из разных половин.
Выбираемые точки параметризуются
величиной смещения от центра
,
которую целесообразно для эффективности
брать как можно меньше:
,
,
,
5.1.5 Метод золотого сечения
Идея этого метода отличается от предыдущего только тем, что в качестве двух сравниваемых точек выбираются точки золотого сечения.
Определение.
Золотое сечение отрезка
точкой такое, что отношение всего отрезка
к большей части равно отношению большей
части к меньшей. Таких точек имеется
две
,
симметричные относительно середины
отрезка:
. (*)
Дополнительно
точки
производят золотые сечения отрезков
,
соответственно.
Последнее свойство приводит к необходимости вычисления согласно формуле (*) только одного нового значения функции на каждом шаге:
,,
.
5.1.6 Метод Фибоначчи
Идея этого метода аналогична методу золотого сечения и состоит в том, что из двух выбираемых точек одна остаётся такой точкой сравнения и для следующего интервала. Такая стратегия реализует максимальное гарантированное сокращение интервала при заданном количестве вычислений функции и претендует на оптимальность. Параметром метода является количество вычислений функции N. Точки вычисления функции находятся с использованием последовательности из N+1 числа Фибонччи.
Определение. Числа Фибоначчи определяются по формуле
.
Начальные конкретные значения: 1, 1, 2, 3, 5,8, 13, 21,34, 55, 89.
Алгоритм вычислений имеет вид:
найти количество вычислений N по формуле
,
где
– N-ое
число Фибоначчи, начальный интервал,
допустимая длина конечного интервала,
соответственно,
,
,
.
5.1.7 Метод квадратичной интерполяции (Пауэлла [Powell M.J.D.])
Идея этого метода состоит в нахождении трёх точек как можно ближе к минимуму и дальнейшем построении квадратичного интерполяционного полинома, проходящего через эти точки. За точку минимума выбирается точка минимума квадратичного полинома:
параметры метода: начальная точка
,
величина шага
,
– характеристики точности,
,
,
,найти
,вычислить точку минимума и значение функции в этой точке:
.
ЗАНЯТИЕ №7 – 21 марта 2013 – пропущено по болезни.
ЗАНЯТИЕ №8 – 28 марта 2013.
«Многомерный случай безусловных экстремумов. Методы нулевого порядка»
5.2 «Метод конфигураций (Хука-Дживса [R. Hook, T.A. Jeeves])».
Исследование
ведётся от текущей базовой точки
вариациями сдвигов
,
по координатам
в обе стороны (+ и –). В случае успешного
результата делается движение по вектору,
идущему из старой базовой точки
в новую
.
В случае успешного результата спуска
по вектору – делается следующий
аналогичный цикл. В случае неуспешного
– возврат в старую точку
и уменьшение параметров «координатных»
и «векторных»
сдвигов.
5.3 «Метод деформируемого многогранника (Нелдера-Мида [J.A. Nelder, R. Mead])».
В этом методе исследуемые на каждой итерации точки расположены в вершинах выпуклого многогранника. На каждой итерации выбрасывается наихудшая вершина и заменяется на новую вершину, выбранную специальным образом, на основе идеи движения в другую сторону от выброшенной точки. Многогранники в итоге стягиваются в точку-решение.
Параметрами метода являются:
координаты вершин многогранника
,
где n
– размерность пространства координат;
– параметры
отражения, сжатия, растяжения,
соответственно;
– точность решения;k – номер итерации.
Рекомендации по использованию параметров:
– Нелдер и Мид;
– Павиани (D.
Paviani);
– Паркинсон и
Хатчисон [J.M.
Parkinson,
D. Hutchinson].
АЛГОРИТМ.
Задать параметры метода.
Найти «минимальную» (наилучшую)
и «максимальную»
и следующую по максимуму (наихудшие)
вершины.
Найти центр тяжести всех вершин многогранника.
Проверить условие завершения – евклидова норма расстояний от вершин до центра < .
Операция отражения: наихудшей вершины через центр тяжести
и получить новый многогранник,Проверить выполнение условий и сделать модификации вершин:
,
,
– сжатие,
,
– редукция.
5.4 «Метод Розенброка [H.H. Rosenbrok].
В этом методе осуществляется итеративный поиск направления убывания функции с помощью изменяемых дискретных шагов вдоль n векторов ортогонального базиса. Для удачного шага он увеличивается на следующей итерации, для неудачного – уменьшается, с помощью коэффициента. Если зашли в тупик, то строиться новый ортогональный базис. Новый базис поворачивается относительно старого вытегиванием вдоль «оврагов».
Параметрами метода являются:
начальная точка ;
– ортогональный
базис;
– длины шагов для
направлений поиска;
– параметры
растяжения, сжатия, соответственно;– точность решения;
N – максимальное число неудачных серий шагов по всем направлениям на одной итерации.
АЛГОРИТМ.
Задать параметры метода.
– шаг по i-му
направлению.
Дэвис, Свенн и Кемпи [Davies D., Swann W.H., Campey I.G.] модифицировали метод Розенброка, применив метод одномерной оптимизации при поиске вдоль каждого направления .
5.5 «Метод сопряжённых направлений (Пауэлла [M.J.D. Powell])»
5.6 «Методы случайного поиска (Нелдера-Мида [J.A. Nelder, R. Mead])»
ЗАНЯТИЕ №9 – 04 апреля 2013.
6. «Многомерный случай безусловных экстремумов. Методы первого порядка»
6.1 «Метод градиентного спуска с постоянным шагом».
Строиться
последовательность точек
по правилу
Шаг
– задаётся и остаётся постоянным, пока
функция убывает. Иначе, например, делится
попалам. Процесс оканчивается по
условиям: 1)
или 2)
– максимальное число итераций, или 3)
– для двух последних шагов.
Параметры метода
.
Для сильно выпуклой функции метод сходится к минимуму. Для Липцишевых функций метод сходится к стационарной точке.
Пример 6.1.
6.2 «Метод наискорейшего градиентного спуска».
От предыдущего
метода с постоянным шагом отличается
определением оптимального шага:
.
Последняя скалярная задача решается
аналитическим или численными методами
для скалярной задачи.
6.3 «Метод покоординатного спуска».
От предыдущих
методов спуска по градиенту здесь на
каждом цикле вычислений (состоящем из
шагов по всем координатам) производиться
спуск по всем отдельным частным
производным:
.
6.4 «Метод Гаусса-Зейделя [Gauss-Seidel]».
От предыдущего
метода покоординатного спуска с
постоянным шагом отличается определением
оптимального шага:
,
аналогично методу «наискорейшего
градиентного спуска». Последняя скалярная
задача решается аналитическим или
численными методами для скалярной
задачи.
6.5 «Метод Флетчера-Ривса [Fletcher R., Reeves C.M.]».
В этом методе
итеративная последовательность точек
строится по формуле:
.
Шаг определяется из условия оптимальности
.
Рассмотрим
физический смысл этого метода. Пусть
минимизируемая функция является
квадратичной формой
,
.
Тогда вычисление величины
обеспечивает построение последовательности
H-сопряжённых
направлений
.
При этом в точках последовательности
последовательные пары градиентов
функции
взаимно ортогональны:
.
Для квадратичной функции
и положительной матрицы H
> 0 метод сходится не более, чем за n
(размерность вектора x)
шагов.
Для неквадратичных
функций метод не является конечным, при
этом нарушается ортогональность
градиентов и H-сопряжённых
направлений. В этом случае применяется
модификация метода Полака-Рибьера
[Polak
E.,
Ribiere
G.]
с более сложным вычислением коэффициента
.
Кроме того, в отличие от метода
Флетчера-Ривса метод Полака-Рибьера
предусматривает использование итерации
наискорейшего градиентного спуска
после каждых n
шагов.
6.6 «Метод Дэвидона-Флетчера-Пауэлла [Davidon W.C., Fletcher R., Powell M.J.D.]».
Это метод является
обобщением метода наилучшего градиентного
спуска, когда
и
.
Вводится дополнительно
матрица
:
и
,
которая определяется по правилу:
Рассмотрим физический смысл этого метода. Пусть минимизируемая
6.7 «Метод кубической интерполяции»
Находятся две такие точки, где производная имеет разные знаки. Вместе со значениями функции в этих двух точках получаем необходимые данные для построения кубического интерполяционного полинома (имеющего 4 параметра). И находиться его минимум.
ЗАДАЧИ.
7. «Многомерный случай безусловных экстремумов. Методы второго порядка»
7.1 «Метод Ньютона».
Этот классический
метод второго порядка (т.е. использующий
второй дифференциал функции) является
основой для многих других, представляющих
его модификации. Формула для вычисления
итерационной последовательности имеет
вид
Таким образом, вместо шага
например, в градиентном методе,
используется боле сложное выражение –
обратная матрица Гессе вторых частных
производных
.
В этом случае,
.
Формула
получена из следующих соображений.
Напишем разложение в ряд Тейлора в точке
x
с точностью до второго порядка функции
.
– квадратичная форма. Направление
(вектор)
определяется из условия Ферма равенства
0 производной:
.
Таким образом, для
последовательность
является последовательностью минимумов
квадратичных функций
Для тех точек, где не выполнено требование
дополним алгоритм шагом градиентного
спуска
с соблюдением условия убывания значений
функции для
:
Пример 7.1.
7.2 «Метод Ньютона-Рафсона».
Представляющий
модификацию метода Ньютона имеет вид
При этом
.
7.3 «Метод Марквардта».
Представляющий
модификацию метода Ньютона имеет вид
При этом
выбирается таким образом, чтобы матрица
.
ЗАНЯТИЕ №10 – 11 апреля 2013.