Градиентные методы решения задач математического программирования [gradient methods] — методы (вычислительные алгоритмы), основанные на поиске экстремума (максимума или минимума) функции путем последовательного перехода к нему с помощью градиента этой функции.
В случае поиска минимума функции говорят о методе наискорейшего спуска, в случае задачи максимизации — о методе наискорейшего роста (или подъема). При этом необходима строгая проверка решения, ибо градиентный спуск или подъем могут привести к экстремальной точке, которая на самом деле окажется не глобальным, а лишь одним из локальных оптимумов.
- · Формально решение в случае «спуска» состоит в построении последовательности векторов x0, x1 ,…, xn, удовлетворяющих условию
f (x0) > f( x2) >…> f(xn).
Такие последовательности называют релаксационными.
Точки этой последовательности [xk] вычисляются по формуле
xk + 1 = xk + g k pk
где g k — направление спуска, определяемого градиентом, pk — длина шага вдоль этого направления; длина шага может быть постоянной и переменной, причем оптимальный ее размер обеспечивает наискорейший спуск (или подъем).
Среди градиентных алгоритмов: метод растяжения пространства, субградиентный метод выпуклой оптимизации, метод покоординатного спуска.