Метод наискорейшего спуска. Эффект оврагов

Метод наискорейшего спуска.

Более эффективными являются методы, когда на каждой итерации шаг  выбирается из условия:

                                             (8)

- Метод наискорейшего спуска 

Но в них на каждом шаге приходится решать задачу min (8).

Доказательство теоремы о сходимости данного алгоритма

 

Эффект оврагов.

Градиентные методы сходятся со скоростью геометрической прогрессии и если матрица  хорошо обусловлена, то сходимость высокая, но в случае плохой обусловленности – после этой матрицы приходим к эффекту оврагов.

Пример:

                                                                                                                        

                                                                                                                                                                                                                                                                        

Быстрая сходимость по переменной (Спуск в овраг) и медленная сходимость по

Выход

1. Изменение масштабов переменных т.е. приведение к круговой форме

2. Эвристические схемы

а) Пусть в точке  вычислены  - частная производная

Задаём  и полагаем , если

т.е. производим быстрый спуск на дно.

б) Задаём  и полагаем , если , т.е. идём по берегу оврага, вдоль его дна.

3. Метод оврагов (Гельфанд)

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

 

 

Метод покоординатного спуска

Стремление уменьшить объем вычислительной работы на одной итерации приводит к упрощению градиентного метода.

Пусть  - приближение.

Вычислим частную производную по первой координате и примем

, где  - единичный орт оси

Следующая итерация – вычисляют точку

и т.д.

Спуск по всем n – координатам составляет одну внешнюю итерацию.