Метод наискорейшего спуска

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

Описание алгоритма метода наискорейшего спуска.

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

2. Условие оптимальности (критерий остановки алгоритма). Алгоритм заканчивает работу, если приближение оптимально, т.е. . При практическом применении метода задается малое число , определяющее точность вычислений и тогда условие остановки алгоритма или аналогичное ему условие . При выполнении этого условия вычисления прекращаются и минимальное значение и .

3. Выбор направления спуска. За направление спуска выбирается направление наискорейшего убывания функции в точке , это направление, противоположной направлению градиента в этой точке. Следовательно, координаты вектора , задающего направление спуска, определяются как частные производные в точке : .

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

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

Описываемый алгоритм спуска сходится, если исследуемая функция удовлетворяет следующим условиям:

1. Функция определена, выпукла и непрерывна во всем пространстве;

2. ;

3. Функция имеет всюду непрерывные частные производные первого и второго порядков.

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