Градиентные методы

Метод градиентного спуска
Суть метода градиентного спуска заключается в том, что в каждой i-й точке алгоритма вычисляется градиент [a = z1 - 2*z2 + z3], определяются направление движения и шаг. Так как за один шаг невозможно достичь точки минимума целевой функции, то строится последовательность точек, переходя от одной точки к другой, достигают точки минимума. В точке минимума все элементы вектора градиента принимают значение нуля. Для определения координат очередной точки используют направление, противоположное градиенту (антиградиент), а размер шага можно определить по различным правилам.

Два основных класса правил определения размера шага
С фиксированным коэффициентом изменения размера шага и с оптимальным подбором размера шага. Каждый класс правил содержит несколько конкретных методов поиска минимума. Для случая с фиксированным коэффициентом изменения размера шага координаты точки на k-м шаге определяются по формуле: x^k=x^(k-1)-Sk
Знак минус определяет направление движения против градиента (при поиске минимума целевой функции). Размер шага Sk на k-й итерации определяется по формуле: Sk=dk*grad ƒ(x^(k-1)) где dk— коэффициент изменения шага, как правило, меньше единицы.

Алгоритм метода градиентного спуска с использованием фиксированного коэффициента изменения шага
Задать координаты стартовой точки
Задать значения
Вычислить значение целевой функции, значения первых производных в текущей точке по каждой координате и определить антиградиент
Определить, достигнут ли минимум целевой функции, т. е. выполняется ли неравенство . Если «да», то перейти к шагу 8. Если «нет», то перейти к шагу 5

Алгоритм метода градиентного спуска с использованием фиксированного коэффициента изменения шага
Вычислить размер шага по формуле Sk=dk*grad ƒ(x^(k-1))
Определить, надо ли уменьшать коэффициент изменения шага. Если неравенство не выполняется, то коэффициент изменения шага уменьшают в 2 раза, dk = 0,5 d(k-1) и переходят к шагу 5. Если неравенство выполняется, то переходят к шагу 7
Определить координаты текущей точки по формуле Sk=dk*grad ƒ(x^(k-1)) и перейти к шагу 3.
Вывод координат точки минимума х и значения целевой функции в точке минимума ƒ(x). Останов алгоритма.

Пример

Решение