Математическая постановка задачи

Пусть задана функция n действительных переменных n f (x1, x2, x3, …, xn) = f (x), определенная на множестве X? R, где x — векторстолбец, обозначающий точку в n-мерном евклидовом пространстве с координатами x1, x2, x3, …, xn .

Функция f (x) имеет локальный минимум в точке x*? X, если существует окрестность точки x* такая, что f (x*)? f (x) во всех точках этой окрестности. В n случае глобального минимума в точке x* для всех x? R справедливо неравенство f (x*)? f (x).

Далее будем рассматривать задачу отыскания точек минимума функции n.

f (x), т. е. f (x) > min, x? R. Для приведения же задачи максимизации к задаче минимизации достаточно изменить знак целевой функции.

АНАЛИЗ МЕТОДОВ РЕШЕНИЯ

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

Решается задача минимизации функции (x) на всём пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности {x_k}. В качестве начального приближения выбирается любая точка x₀E_n. Последовательные приближения x₁, x₂, … строятся по следующей схеме:

в точке x_k выбирают направление спуска — S_k;

находят (k+1)-е приближение по формуле.

x_k+1=x_k-h_kS_k.

Направление S_k выбирают таким образом, чтобы обеспечить неравенство f (x_k+1)_k) по крайней мере для малых значений величины h_k. На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет.

Число h_k определяет расстояние от точки x_k до точки х_k+1. Это число называется длиной шага или просто шагом. Основная задача при выборе величины h_k — это обеспечить выполнение неравенства (x_k+1)<(x_k).

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

x_k+1=x_k-h_k cos.

где — cos=.

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

Наибольшее распространение получили следующие алгоритмы:

• 1. (без коррекции);
• 2. если; если

3., если; , если; , если ,.

гдеугол между градиентами на предыдущем и текущем шаге;

и — заданные пороговые значения выбираются субъективно (например,).

Вдали от оптимума направление градиента меняется мало, поэтому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами R (x) большой), поэтому h сокращается (третье выражение).