Линейная алгебра и мат. Статистика
жүктеу/скачать 294.26 Kb.
|
- Бұл бет үшін навигация:
- Достоинствами
- Градиентный спуск
- Метод Флетчера
- Backtracking
| Покоординатный спуск
В методе покоординатного спуска в качестве очередного направления выбирается одна из координат . При этом координаты перебираются последовательно либо в случайном порядке. На этапе одномерной оптимизации вдоль очередной координаты можно использовать как точные методы, так и методы неточной оптимизации (например, backtracking или метод Флетчера). Применение метода покоординатного спуска является особенно эффективным в ситуациях, когда задача одномерной оптимизации может быть решена аналитически. В методе покоординатного спуска значение оптимизируемой функции не увеличивается на каждой итерации. При дополнительном предположении об ограниченности снизу на можно показать, что для непрерывно-дифференцируемых функций метод покоординатного спуска гарантированно сходится к локальному минимуму. Более того, для строго выпуклых функций метод сходится с линейной скоростью. Достоинствами метода покоординатного спуска являются: Простота вычисления направлений . В результате метод может применяться, в том числе, в пространствах сверх-большой размерности; Отсутствие требований к вычислению любых производных функции . В результате метод может применяться для случая оракула нулевого порядка. К недостаткам метода следует отнести: Возможность застревания в промежуточной точке для негладких функций . Возможность совершать большое количество очень маленьких шагов даже при оптимизации строго выпуклых функций. Такая ситуация частично связана с неспособностью метода идти по диагонали. Градиентный спуск Вопрос диагонального движения решается в методе градиентного спуска. Известно, что градиент определяет направление наибольшего роста функции в точке . Поэтому в качестве стратегии выбора направления разумно выбрать (так как функция минимизируется). Если на каждой итерации задача одномерной оптимизации решается точно, то такой метод называется методом наискорейшего спуска. Нетрудно убедиться, что в этом методе соседние направления , всегда ортогональны. Наряду с точной оптимизацией по α на каждом шаге, в методе градиентного спуска можно пользоваться различными стратегиями неточной одномерной оптимизации. Рассмотрим некоторые из них: Метод Флетчера, в котором выбирается значение , удовлетворяющее двум условиям: , . По сравнению с наискорейшим спуском количество обращений к оракулу на каждой итерации снижается до среднего значения. Однако, общее количество итераций увеличивается. Backtracking. В этом методе выбирается некоторое фиксированное заранее значение , которое затем сокращается в цикле на некоторую величину до тех пор, пока не будет выполнено первое из условий для метода Флетчера. Такой подход позволяет еще больше сократить среднее число обращений к оракулу на каждой итерации. жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|