Метод половинного деления

Метод основан на делении текущего отрезка [о b,], где содержится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точ­ках, отстоящих от середины отрезка на е / 2, где е — погрешность решения задачи оптимизации.

Если R(x + е /2) > R(x - е /2), то максимум располагается на правой половине текущего отрезка [а, b], в противном случае — на левой.

Процесс поиска завершается при достижении отрезком [а, b ] величины заданной погрешности е.

К недостаткам метода относится его работоспособность только для одноэкстремальных функций R(x) (т.е. таких, которые содержат один экстремум того типа, который мы ищем в задаче), так как в других случаях при сравнении двух критериев в сосед­них точках невозможно правильно выбрать следующий интервал, где находится максимум.

На рис. 14 приведены три этапа метода половинного деления. Сплошными вертикальными линиями отмечены середины отрезков, а пунктирными — вычисляемые значения критерия оптимальности слева и справа на е/2 от середин.

МНОГОМЕРНАЯ БЕЗУСЛОВНАЯ ГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ

Концепция методов

Рассматриваются методы построения улуч­шающих последовательностей при отыскании экстремума функции R(x) без активных ограничений. Активными принято называть такие ограничения, на границе которых находится решение. Если известно, что решение лежит строго внутри допустимой области, например, в случае ограничений типа неравенств, то такие ограничения лучше выводить из задачи на этапе ее постановки. Кстати, следует отметить, что ограничения типа равенств всегда активные.

Величина шага х в рекуррентном соотношении

Xⁱ⁺¹ =хⁱ +хⁱ

вычисляется с использованием градиента целевой функции R(x), т.е.

хⁱ = f (grad R(xⁱ)),

при этом шаг может определяться с использованием градиента в одной (текущей) или в двух (текущей и предыдущей) точках. Направление градиента, как известно, показывает направления наискорейшего возрастания функции, а его модуль — скорость этого возрастания.

Рис. 17. Иллюстрация траекторий поиска минимума функции градиентными методами: 1 — оптимум; 2 — траектория метода градиента; 3 — траектория метода тяжелого шарика; 4 — траектория метода наискорейшего спуска;

5 — траектория метода сопряженных градиентов; 6 — начальные точки траекторий

лишь одна из возможных траекторий.

Кроме того, для всех приве­денных траекторий выбраны различные начальные условия, с тем чтобы не загромождать построения. На этом и последующих рисунках зависимость R(x₁,x₂) приведена в виде линий уровня на плоскости в координатах x₁ –x₂.

МЕТОД ГРАДИЕНТА

Метод градиента в чистом виде формирует шаг по переменным как функцию от градиента R(x) в текущей точке поиска. Простейший алгоритм поиска minR(x) записывается в векторной форме следующим образом:

xⁱ⁺¹ =xⁱ-hgradR(xⁱ),

или в скалярном виде:

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

Поиск каждой новой точки состоит из двух этапов:

1) оценка градиента R(x) путем вычисления частных производных от R(x) по каждой переменной х_j;

2) рабочий шаг по всем переменным одновременно.

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

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

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

1. hⁱ =const =h (без коррекции);

2. hⁱ =h^i-1/2, еслиР(хⁱ)< R(x^i-1); hⁱ =h^i-1, ecлиR(xⁱ)>R(x^i-1);

3. hⁱ=h^i-1, если ₁   ₂; hⁱ=2h^i-1, если ₁  ; ,

где  — угол между градиентами на предыдущем и текущем шаге; ₁, и ₂; — заданные пороговые значения выбираются субъективно (например, ₁ =П/6, ₂ = П /3).

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

Для оценки частных производных используются разностные методы:

1. Алгоритм с центральной пробой

2. Алгоритм с парными пробами

где g_i — пробный шаг по i-й переменной, выбираемый достаточно малым для разностной оценки производной.

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

На рис. 17 приведена одна из возможных траекторий поиска минимума двумерной функции градиентным методом (наряду с другими ниже рассматриваемыми методами).

Условием окончания поиска может являться малость модуля градиента R(x), т.е. |grad R(x)\< .