Градиентные методы — численные методы решения с помощью градиента задач, сводящихся к нахождению экстремумов функции.
Содержание |
Задача решения системы уравнений:
(1)
с эквивалентна задаче минимизации функции
(2)
или какой-либо другой возрастающей функции от абсолютных величин невязок (ошибок) , . Задача отыскания минимума (или максимума) функции переменных и сама по себе имеет большое практическое значение.
Для решения этой задачи итерационными методами начинают с произвольных значений и строят последовательные приближения:
или покоординатно:
(3)
которые сходятся к некоторому решению при .
Различные методы отличаются выбором «направления» для очередного шага, то есть выбором отношений
.
Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра , минимизирующим величину как функцию от . Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям . Последний метод применим для отыскания max и min таблично заданной функции .
Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :
где выбирается
Выбирают , где все производные вычисляются при , и уменьшают длину шага по мере приближения к минимуму функции .
Для аналитических функций и малых значений тейлоровское разложение позволяет выбрать оптимальную величину шага
(5)
где все производные вычисляются при . Параболическая интерполяция функции может оказаться более удобной.
Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые раз за один шаг.
Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации — метода сопряжённых направлений.
Применение метода к квадратичным функциям в определяет минимум за шагов.
Методы оптимизации | |
---|---|
Одномерные | Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск |
Прямые методы | Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка |
Первого порядка | Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта |
Второго порядка | Метод Ньютона • Метод Ньютона — Рафсона |
Стохастические | Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц |
Методы линейного программирования |
Симплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов |
Методы нелинейного программирования |
Последовательное квадратичное программирование |
Градиентные методы являются методами нулевого порядка, градиентные методы реферат, градиентные методы многомерной оптимизации, градиентные методы скалярной оптимизации.
Ахвердов, Николай Николаевич, Файл:Tursiops truncatus 01.jpg, Вулластон, Бен, Туольсленг, Конрад Вильчински.