Иллюстрация понятие градиента

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

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

 В этом методе поиск происходит более крупными шагами, и градиент функции вычисляется в меньшем числе точек. Задача вычисления наилучшего шага может решаться с помощью методов одномерного поиска, например, методом золотого сечения или половинного деления. Величину шага h_k на k-ом шаге поиска можно найти из условия минимума функции Q ( x_k + h_{k *} S_k ):

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

1. Расстояния от найденной точки x_k до точки x_{k -1} меньше погрешности:
2. Разница значений целевой функции в этих точках меньше погрешности:
3. Норма градиента в найденной оптимальной точке меньше погрешности:

Многомерная оптимизация. Метод Ньютона (метод вторых производных).

Метод Ньютона (метод вторых производных)

В соответствии с этим методом на k шаге поиска оптимального значения целевой функции координаты последующих точек определяются по формуле:

Где       - обратная матрица Гессе

Рассмотрим пример нахождения минимума функции Розенброка:

В качестве исходной точки поиска примем точку X0(-0.5; 0.5) со значением функции в исходной точке f(X0)=8.5. Найдем матрицу Гессе:

Вычислим значения частных производных и составляющих градиента:

После вычисления производных получаем матрицу Гессе в виде:

Вычислим [ H] в исходной точке x1=-0.5, x2=0.5

Вычислим значения составляющих градиента в соответствующих точках:

Вычислим матрицу, обратную матрице Гессе:

После преобразований получаем:

Таким образом, после одного шага нахождения минимума функции f( x1, x2) значение функции в вычисленной точке поиска f(x)=2.33, что меньше, чем в исходной точке поиска, что свидетельствует о работоспособности метода.