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