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

Для решения задач безусловной минимизации функции широко применяют приближенные методы, в основе которых лежит вычисление производных первого порядка функции [1], [6], [8], [12]-[15]. Такие методы обычно называют градиентными. Рассмотрим один из них – метод градиентного спуска.

Пусть - выпуклая дифференцируемая во всем пространстве функция. Требуется найти ее точку минимума .

Опишем метод градиентного спуска [1], [12]. Метод предполагает выбор начального приближения – некоторой точки . Общих правил выбора точки в методе градиентного спуска нет. В тех случаях, когда из геометрических, физических и других соображений есть информация об области расположения точки минимума, то начальное приближение стараются выбрать поближе к этой области.

Будем считать, что некоторая начальная точка уже выбрана. Тогда метод градиентного спуска заключается в построении последовательности по правилу

(16)

Число из (6) называют длиной шага или шагом метода градиентного спуска.

Если , то шаг можно выбрать так, чтобы .

Если , то - стационарная точка. В этом случае процесс (16) прекращается, и при необходимости проводится дополнительное исследование поведения функции в окрестности точки для выяснения того, достигается ли в точке минимум функции или не достигается. В частности, если - выпуклая функция, то согласно критерию оптимальности в стационарной точке всегда достигается минимум.

Существуют различные способы выбора в методе (16). В зависимости от способа выбора можно получить различные варианты метода градиентного спуска. Укажем наиболее часто применяемые на практике способы выбора .

1) Метод с дроблением шага. На практике достаточно малое часто выбирают так, чтобы выполнялось условие монотонного убывания функции:

, .

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

2) Метод наискорейшего спуска. На луче

,

направленном по антиградиенту, введем функцию одной переменной , и определим из условий

, . (17)

Метод (16), (17) называется методом наискорейшего спуска. Для определения на каждом шаге решается одномерная задача минимизации (17), для чего можно использовать методы, рассмотренные нами ранее.

Приведем пример, когда величина , определенная условием (17), существует и может быть выписана в явном виде.

Например, пусть дана квадратичная функция

где – симметричная неотрицательно определенная матрица порядка ; , – вектора из , – скалярное произведение из .

- выпуклая функция, и ее производные вычисляются по формулам , .

Поэтому метод (6) в данном случае будет выглядеть так:

Таким образом, метод градиентного спуска для функции (18) представляет собой известный итерационный метод решения системы линейных алгебраических уравнений .

определяется по формуле

. (19)

Таким образом, метод наискорейшего спуска для квадратичной функции (18) заключается в построении последовательности точек по формулам (16), (19).

3) Метод с константой Липшица. Пусть функция , т.е. функция и градиент удовлетворяет условию Липшица:

для любых точек , а постоянная называется константой Липшица.

Если константа известна, то в (16) в качестве может быть взято любое число, удовлетворяющее условиям

,

где , - положительные числа, являющиеся параметрами метода.

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

В качестве условия окончания метода градиентного спуска обычно используется близость к нулю градиента , т.е. выполнение неравенств

или

, (20)

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

Пример 1. Минимизировать в функцию

методом градиентного спуска с дроблением шага, завершив вычисления при .

Решение. Выбрав начальное приближение и , построим последовательность

,

записывая результаты вычислений в таблицу 3.

Таблица 3.

Итак, .

Пример 2. Дана задача безусловной минимизации

.

Точка - начальное приближение. Сделать два шага итераций метода наискорейшего спуска.

Решение. 1 шаг. Формула (16) при имеет вид

Найдем градиент или производную функции :

.

Найдем в точке :

.

Для определения шага составим функцию при :

.

Найдем точку , подставив сюда начальное приближение и производную :

.

Найденную точку подставим в функцию

,

тогда

.

В силу выпуклости функции , найдем из условия : , отсюда

.

Сделаем первый шаг по методу наискорейшего спуска:

.

Точка первого приближения найдена. Далее, если в условии задачи оговорена точность, с которой требуется найти точку минимума, то на каждом шаге итерации надо вычислять норму градиента из условия (20). Поэтому сначала найдем градиент функции в точке

,

а затем вычислим :

.

2 шаг. Формула (16) при имеет вид

Для определения шага составим функцию при :

.

Найдем точку , подставив сюда первое приближение и производную :

.

Найденную точку подставим в функцию

,

тогда

.

В силу выпуклости функции , найдем из условия : , отсюда .

Сделаем второй шаг по методу наискорейшего спуска:

.

Точка второго приближения найдена. Найдем градиент функции в точке

,

а затем вычислим :

.

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