Градиентные методы гладкой оптимизации. Общая идея градиентного спуска (подъема). Пропорциональный градиентный метод. Полношаговый градиентный метод. Метод сопряженных градиентов

Методы отыскания экстремума, использующие производные, имеют строгое математическое обоснование. Известно, что при отыскании экстремума не существует лучшего направления, чем движение по градиенту.

Градиентом дифференцируемой функции f(x) в точке х [0] называется n -мерный вектор f(x [0] ), компоненты которого являются частными производными функции f(х), вычисленными в точке х [0], т. е.

f'(x [0] ) = (дf(х [0] )/дх ₁, …, дf(х [0])/ дх_n)^T.

Этот вектор перпендикулярен к плоскости, проведенной через точку х [0], и касательной к поверхности уровня функции f(x), проходящей через точку х [0].В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С₀, С₁,..., получим серию поверхностей, характеризующих ее топологию

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f’(х [0] )), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Очевидно, что если нет дополнительной информации, то из начальной точки х [0] разумно перейти в точку х [1], лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р [ k ] антиградиент - f’(х [k] ) в точке х [ k ], получаем итерационный процесс вида

х [ k+ 1] = x [ k ]- a_kf'(x [k] ), а_k > 0; k =0, 1, 2,...

В координатной форме этот процесс записывается следующим образом:

x_i [ k +1]= х_i [ k ] - a_k f(x [k] ) / x_i

i = 1,..., n; k = 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x [ k +l] - x [ k ] || <= e, либо выполнение условия малости градиента

|| f’(x [ k +l] ) || <= g,

Здесь e и g - заданные малые величины.

Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага а_k.

При методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шаг а_k обеспечит убывание функции, т. е. выполнение неравенства

f(х [ k +1] ) = f(x [k] – a_kf’(x [k] )) < f(x [k] ).

Однако это может привести к необходимости проводить неприемлемо большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции либо привести к колебаниям около точки минимума (зацикливанию). Из-за сложности получения необходимой информации для выбора величины шага методы с постоянным шагом применяются на практике редко.

Более экономичны в смысле количества итераций и надежности градиентные методы с переменным шагом, когда в зависимости от результатов вычислений величина шага некоторым образом меняется. Рассмотрим применяемые на практике варианты таких методов.

Поиск по сайту: