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

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

(47)

Таким образом, в данном варианте градиентного спуска на каждой итерации необходимо решить задачу одномерной минимизации (47). Алгоритм метода наискорейшего спуска состоит в следующем:

1. В точке вычисляется значение градиента функции и шага путем решения задачи одномерной минимизации (47).

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

2. Если на i-ом шаге , то в точке вычисляются новые значения градиента и шага и выполняется переход к п.2

3. Критериями останова итерационного процесса служат следующие условия: если минимум вдоль данного направления спуска не может быть определен на последней итерации с помощью формулы (47); при превышении заданного числа итерации; при полученных значениях компонент градиента, меньших по абсолютной величине заданных минимально допустимых значений первой производной минимизируемой функции.

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

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

Пример 7. Определить градиентным методом максимум функции , начав итерационный процесс из точки Х=(4,5) [7].

Решение: В данном случае и .

Итерация 1. Имеем и . Используя необходимое условие экстремума:

Получим

Откуда . Так как , то найденное значение является точкой максимума .

С помощью величины получаем новую точку

Итерация 2. Начальная точка ; Следовательно, является стационарной точкой и дальнейшее перемещение вдоль градиента невозможно. Так как функция z выпуклая, то в найденной точке достигается глобальный максимум (в начальной точке .

Пример 8. Найти минимум функции . Начальная точка (4; -1; 2) и начальный шаг равен 4.

Решение: Очевидно, что минимум равен нулю при . Итерационный процесс приведен в таблице 3.

Таблица 3.

№ итерации	x1	x2	x3	F
1	3,232205	0,023727	-5,16609	13,95128
2	1,189384	2,747488	-4,55811	0,880715
3	1,140915	2,812114	-5,01049	0,555979
4	1,011955	2,98406	-4,9721	0,003597
5	1,008896	2,988139	-5,00066	0,000221
6	1,000754	2,998995	-4,99824	0,0000139

Оптимальное значение находится на 11 шаге при значениях .

Предлагаю ознакомиться с аналогичными статьями: