Классификация методов минимизации функций многих переменных

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

Классификация методов: М нулевого порядка (м конфигурации Хука-Дживса;м деформированного многогранника); М первого порядка (м градиентного спуска; м наискорейшего спуска; м наискорейшего покоординатного спуска; м сопряженных градиентов); М второго порядка (м Ньютона; м Ньютона-Рафсона; мЛевенберга-Марквардта)

Общая характеристика методов 0-го порядка

для определения направления спуска не требуется вычислять производные целевой функции. Направление минимизации полностью определяется последовательными вычислениями значений функции, и сводятся к построению траектории спуска{x^k}, вдоль которой целевая функция убывает: f(x^k+1)<f(x^k)

Общая характеристика методов 1-го порядка

Методы первого порядка основаны на свойствах градиента (градиентными методами минимизации). Использование этих методов в общем случае позволяет определить точку локального минимума функции. В градиентных методах, если нет дополнительной информации, то из начальной точки x⁰разумно перейти в точку x¹, лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска антиградиент – f’(x^k) в точке x^k, получаем итерационный процесс вида:

x^k+1=x^k- t_kf’(x^k),t_k>0; k=0,1,2,…

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

Градиентные методы отличаются друг от друга способами выбора величины шага t_k.

Таким образом: Метод нулевого порядка - метод, в котором на каждой итерации используются лишь значения минимизируемых функций; Метод первого порядка - метод, требующий вычисления первых производных минимизируемой функции; Метод второго порядка - методы, требующие вычисления вторых производных;

МЕТОДЫ УСЛОВНОЙ ОПТИМИЗАЦИИ