Методы нулевого порядка
В качестве примера рассмотрим метод покоординатного спуска.
Метод покоординатного спуска (метод Гаусса –Зайделя)
Идея
метода.
Выбирается некоторая начальная точка
.
Делаются пробные шаги вдоль каждой
координаты. Выбирается координата
(поисковая переменная), вдоль которой
наблюдается наибольшее изменение
значения целевой функции. Данная
переменная принимается в качестве
поисковой вдоль данного направления.
Остальные переменные фиксируются. В
поиске по переменной можно воспользоваться
любым методом одномерного поиска.
Движение продолжается до тех пор, пока
значение
целевой функции уменьшается.
Далее в качестве изменяемой переменной
берется следующая
поисковая переменная
и итерационный процесс повторяется.
Другие методы нулевого порядка:
метод прямого поиска (метод Хука-Дживса)
метод вращающихся координат (метод Розенброка)
метод параллельных касательных (метод Пауэлла)
симплекс метод
метод деформируемого многогранника (метод Нелдера–Мида)
Методы первого порядка
В методах первого порядка (градиентные методы) направление спуска совпадает с направлением антиградиента.
Напомним,
что градиентом
дифференцируемой функции
в точке
называется
-мерный
вектор
,
компоненты которого являются
частными
производными функции,
вычисленными в этой точке.
Этот вектор перпендикулярен к плоскости, проведенной через точку , и касательной к поверхности уровня функции , проходящей через точку .
Вектор-градиент
направлен в сторону наискорейшего
возрастания функции в данной точке.
Вектор, противоположный градиенту
,
называется антиградиентом
и направлен в сторону наискорейшего
убывания функции. В
точке минимума градиент функции равен
нулю.
Градиентные методы отличаются друг от друга способами выбора величины шага.
Метод наискорейшего спуска, метод градиента
В
классическом
методе наискорейшего спуска
(методе Коши). в выражении (5) (
)
матрица
принимается равной
,
,
где
–
единичная (
)-матрица.
Направлением движения здесь является
наискорейшее
убывание функции в данной точке:
(11)
Точки
перехода
на следующее направление определяются
с помощью условия (10)
, т. е.
.
Отличием метода градиента от метода наискорейшего спуска заключается в том, что переход на следующее направление определяется с помощью условия (9) ).
На
рисунке направление движения из точки
касается линии уровня в точке
.
Траектория спуска зигзагообразная,
причем соседние звенья зигзага
ортогональны друг другу.
В методе наискорейшего спуска каждое новое направление ортогонально предыдущему, т.к. движение в одном направлении идет до тех пор, пока направление движения не окажется касательным к какой-либо линии постоянного уровня.
Отметим, что в методах наискорейшего спуска и градиента производные критерия оптимизации по варьируемым переменным определяются либо аналитически, либо с помощью разностей:
. (12)
В этой формуле нижний индекс обозначает номер компоненты вектора .
Использование уравнения (12) связано с тем, что, как правило, при оптимизации реальных систем (технических, химико-технологических и др.) вид математической модели и соответственно целевой функции в явном виде не задан. Имеется только алгоритм, который позволяет при заданных значениях поисковых переменных вычислить значение целевой функции.
Достоинство градиентных методов – простота реализации.
Недостатки:
1) метод является линейным – даже при минимизации квадратичной функции процесс поиска ее минимума теоретически бесконечен;
2) для функций с сильно вытянутыми линиями равного уровня (овражные функции) процесс поиска носит явно выраженный зигзагообразный характер и дает слабое продвижение к минимуму; точное определение минимума практически нереально. Направление антиградиента этих функций (см. рис) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.
