Задачи оптимизации в евклидовом пространстве
Рефераты >> Математика >> Задачи оптимизации в евклидовом пространстве

Иногда, стремясь ускорить сходимость метода, величину подбирают так, чтобы при переходе от к вдоль направления спуска обеспечивалось наибольшее возможное убывание целевой функции. Другими словами, находят из условия минимума функции одной переменной :

,

Где номер определяется номером шага . Такой выбор приводит к меньшему числу шагов для достижения заданной точности. Однако выполнение каждого шага сопряжено с решением задачи минимизации функции одной переменной, что приведет к дополнительным вычислениям. Кроме того, нахождение точного значения в этой задаче не всегда возможно; если же вместо точного значения использовать приближенное, то может нарушаться условие убывания .

Блок-схема поиска минимума функции методом покоординатного спуска.

3. Градиентные методы

Ненулевой антиградиент указывает направление, небольшое перемещение вдоль которого из приводит к значению функции меньшему, чем . Это замечательное свойство антиградиента лежит в основе градиентных методов, согласно которым на -й итерации полагают , т.е.

, , .

Рис. 2.

3.1. Эти методы отличаются друг от друга способом выбора величины шага .

1) На практике нередко довольствуются нахождением какого-либо , обеспечивающего условие монотонности:

. (8)

С этой целью задаются какой-либо постоянной и на каждой итерации берут . При этом для каждого проверяют условие монотонности, и в случае его нарушения дробят до тех пор, пока не восстановится монотонность метода. Время от времени полезно пробовать увеличить с сохранением условия монотонности.

2) Часто величину рекомендуют выбрать так, чтобы имело место более жесткое условие убывания, чем (8):

, (9)

Где - некоторая фиксированная константа. Здесь также сначала фиксируют некоторое (например, ), одинаковое для всех итераций, а затем при необходимости уменьшают его до тех пор, пока не будет выполнено неравенство (8).

3) В методе наискорейшего спуска (рис. 3) величину определяют в результате минимизации функции одной переменной :

. (10)

Функция в точке достигает минимума, поэтому ее производная в этой точке равна нулю:

Последнее равенство означает ,что направление спуска на -й итерации ортогонально направлению спуска на предыдущей -й итерации (рис. 3). Таким образом, кривая движения по методу наискорейшего спуска представляет собой ломаную, соседние звенья которой взаимно ортогональны, причем звено, соединяющее и , лежит в гиперплоскости, касательной к поверхности уровня .

Рис. 3.

4) Возможно априорное задание величин из условий

, ; , . (11)

Например, в качестве можно взять , где , а число таково, что . В частности, если , , то получим . Такой выбор в (8) очень прост для реализации, но не гарантирует выполнения условия монотонности и, вообще говоря, сходится медленно.


Страница: