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

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

Целевую функцию можно записать в виде

(1)

В результате оптимизации получают значения параметров, обеспечивающих минимум (или максимум) целевой функции. Допустим, имеется выпуклая целевая функция , которую необходимо минимизировать (максимизировать). Можно выделить два типа задач оптимизации:

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

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

(2)

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

Общая схема широкого класса методов приближенного решения Алгоритм задачи безусловной минимизации следующий:

1. Выбор начального приближения.

2. Проверка условия оптимальности. Если оно выполняется, то работа алгоритма заканчивается, иначе – переходим к пункту 3.

3. Определение направления.

4. Определение шага.

5. Вычисление очередного приближения и переход к пункту 2 (проверка условия оптимальности.

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