Метод градиента в чистом виде формирует шаг по переменным как функцию от градиента R(x) в текущей точке поиска. Простейший алгоритм поиска min R(x) записывается в векторной форме следующим образом:
или в скалярном виде:
- порядковый номер аргумента,
Величина рабочего шага в направлении градиента h grad R(x) зависит от величины градиента, который заранее учесть трудно, и от коэффициента пропорциональности шага h, с помощью которого можно управлять эффективностью метода.
Поиск каждой новой точки состоит из двух этапов:
1) оценка градиента R(x) путем вычисления частных производных от R(x) по каждой переменной хj,
2) рабочий шаг по всем переменным одновременно.
Величина h сильно влияет на эффективность метода. Большей эффективностью обладает вариант метода, когда шаг по переменной определяется направляющими косинусами градиента.
где cosφ j =
В этом случае величина рабочего шага не зависит от величины модуля градиента, и ею легче управлять изменением h. В районе оптимума может возникать значительное "рыскание", поэтому используют различные алгоритмы коррекции h.
|
|
Наибольшее распространение получили следующие алгоритмы:
MathCAD
1. hi = const = h (без коррекции);
2. hi = hi-1 /2, если R(xi) < R(xi-1); hi = hi-1, R(xi) > R(xi-1);
3. hi = hi-1, если a1≤ a ≤a2; hi =2 hi-1, еслиa1>a; если a2 < a.
где a — угол между градиентами на предыдущем и текущем шаге; a1 и a2 — заданные пороговые значения выбираются субъективно (например, a1 = π/6, a2 = π/3).
Вдали от оптимума направление градиента меняется мало, потому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами R(x) большой), поэтому h сокращается (третье выражение).
Для оценки частных производных используются разностные методы:
1. Алгоритм с центральной пробой
2. Алгоритм с парными пробами
где gj — пробный шаг по j -й переменной, выбираемый достаточно малым для разностной оценки производной.
Первый алгоритм требует меньших затрат по сравнению со вторым (обычно затраты выражаются количеством вычислений критерия оптимальности), но позволяет получить решение менее точно, чем второй, и эта погрешность зависит от величины пробного шага.
На рис. приведена одна из возможных траекторий поиска минимума двумерной функции градиентным методом (наряду с другими ниже рассматриваемыми методами).
Условием окончания поиска может являться малость модуля градиента R(x), т.е. | grad R(x) | <e.
Рис. Иллюстрация получения производной с центральной и парными пробами.