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

Назначение сервиса. Онлайн-калькулятор используется для нахождения минимума функции методом наискорейшего спуска или методом Коши (см. пример). Решение оформляется в формате Word.
f(x1,x2) =
Метод отыскания минимума функции
Начиная из точки ( ; ). Точность ξ = . Количество итераций
Правила ввода функций:
  1. Все переменные выражаются через x1,x2
  2. Все математические операции выражаются через общепринятые символы (+,-,*,/,^). Например, x12+x1x2, записываем как x1^2+x1*x2.

В методе наискорейшего спуска в качестве направления поиска выбирается вектор, направление которого противоположно направлению вектора градиента функции ▽f(x). Из математического анализа известно, что вектор grad f(x)=▽f(x) характеризует направление наиболее быстрого возрастания функции (см. градиент функции). Поэтому вектор -grad f (X) = -▽f(X) называется антиградиентом и является направлением наиболее быстрого ее убывания. Рекуррентное соотношение, с помощью которого реализуется метод наискорейшего спуска, имеет вид Xk+1=Xk - λk▽f(xk), k = 0,1,...,
где λk>0 - величина шага. В зависимости от выбора величины шага можно получить различные варианты градиентного метода. Если в процессе оптимизации величина шага λ фиксирована, то метод носит название градиентного метода с дискретным шагом. Процесс оптимизации на первых итерациях можно значительно ускорить, если λk выбирать из условия λk=min f(Xk + λSk).
Для определения λk используется любой метод одномерной оптимизации. В этом случае метод называется методом наискорейшего спуска. Как правило, в общем случае недостаточно одного шага для достижения минимума функции, процесс повторяют до тех пор, пока последующие вычисления позволяют улучшать результат.
Если пространство очень вытянуто по некоторым переменным, то образуется “овраг”. Поиск может замедлиться и идти зигзагами поперек дна “оврага”. Иногда решение невозможно получить за приемлемое время.
Еще одним недостатком метода может быть критерий остановки ||▽f(Xk)|| <εk, так как этому условию удовлетворяет и седловая точка, а не только оптимум.

Пример. Начиная из точки xk=(-2, 3) определите точку xk+1 методом наискорейшего спуска для минимизации функции .
В качестве направления поиска выберем вектор градиент в текущей точке

Проверим критерий остановки . Имеем
Вычислим значение функции в начальной точке f(X1) = 35. Сделаем
шаг вдоль направления антиградиента

Вычислим значение функции в новой точке
f(X2) = 3(-2 + 19λ1)2 + (3-8λ1)2 - (-2 + 19λ1)(3-8λ1) - 4(-2 + 19λ1)
Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции
f’(X2) = 6(-2 + 19λ1) 19 + 2(3-8λ1)( -8) – (73 - 304 λ1) – 4*19
или f’(X2) = 2598 λ1 – 425 = 0.
Получим шаг λ1 = 0.164
Выполнение этого шага приведет в точку

в которой значение градиента , значение функции f(X2) = 0.23. Точность не достигнута, из точки делаем шаг вдоль направления антиградиента .

f(X2) = 3(1,116 – 1,008λ1)2 + (1,688-2,26λ1)2 - (1,116 – 1,008λ1)( 1,688-2,26λ1) - 4(1,116 – 1,008λ1)
f’(X2) = 11,76 – 6,12λ1 = 0
Получаем λ1 = 0.52

загрузка...