Метод допустимых направлений Зойтендейка

Назначение сервиса. Онлайн-калькулятор используется для нахождения минимума функции двух переменных методом допустимых направлений Зойтендейка.
Количество ограничений, gi(x)
Правила ввода функций:
  1. Все переменные выражаются через x1,x2
  2. Все математические операции выражаются через общепринятые символы (+,-,*,/,^). Например, x12+x1x2, записываем как x1^2+x1*x2.
В задачах с ограничениями линеаризуются и ограничения и целевые функции, а направления необходимо выбирать так, чтобы они приводили к допустимым точкам .
Рассмотрим задачу с ограничениями в виде неравенств
f(x) → min,
, . (1)
Пусть x0 - начальная точка, удовлетворяющая ограничениям:
, .
Предположим, что некоторые ограничения являются активными в точке x0:
, .
Вектор d определяет допустимое направление для поиска, если d - направление спуска, т. е.
▽f(x)d < 0 (2)
и точки луча x(α) = x0 + α d, где α ≥ 0 (3)
являются допустимыми на небольшом расстоянии от x0.
Неравенство ▽f(x)d < 0 получается следующим образом.
Разложим в ряд Тейлора функцию f(x) в точке x0:
f(x)=f(x0)+▽fT(x)(x-x0).
В направлении спуска в допустимых точках должно выполняться неравенство: f(x)<f(x0), следовательно, ▽f(x0)(x0)<0.
Вводя обозначение x- x0=d, получим искомый результат.
Точки x(α) будут допустимыми, если для всех активных ограничений выполняется условие:
, (4)
Так как по предположению
, и ,
то выражение (4) эквивалентно следующему условию для d:
. (5)
Основная идея: на каждом шаге итерации определяется допустимое направление, т. е. вектор d и скалярный параметр θ>0, такие, чтобы выполнялись следующие неравенства:
, , , (6)
а значение θ выбирается по возможности большим.
При реализации на ЭВМ допустимые направления удобно нормировать, вводя границы
, . (7)
Такой способ выбора вектора d обеспечивает разумный компромисс между движением внутрь области допустимых значений без нарушения ограничений и движением по направлению наискорейшего спуска.
После того, как вектор d выбран, очередное приближение может быть определено поиском минимального значения α вдоль прямой
x=x0 + α d0(8)
до тех пор, пока либо f(x) не достигнет экстремума, либо пока какое-либо из ограничений не окажется нарушенным.
Обычно для каждого ограничения gi(x)≥0 находятся значения αi>0, при которых
gi(x0 + α d0)=0, (9)
а затем определяется как наименьшее из αi
.
При известном значении можно использовать любую процедуру одномерного поиска для определения α, которое минимизирует функцию
f(x0 + αd0) на отрезке .

Основной алгоритм Зойтендейка

В данной допустимой точке определяется множество индексов тех ограничений, которые активны в xt в пределах заданной погрешности ε , т. е.
,
где ε - заданная погрешность.
Полная итерация метода возможных направлений состоит из следующих трех этапов:
Шаг 1. Решить ЗЛП:
θ → max

, , , .
Пусть dt и θt - полученное решение.
Шаг 2. Если θt ≤ 0, то конец, т. к. дальнейшее улучшение невозможно.
Иначе:
Найти .
Если не существует , положить , например, .
При поиске как может оказаться, что не для всех будет выполняться равенство gi(xt+αdt)=0; значит, мы определяем сразу It множество индексов, для которых gi=0.
Шаг 3. Найти такое αt, что
.
Положить xt+1 = xt + αtdt и продолжить решение.
При определении множества активных ограничений It и α учитывается погрешность, роль которой рассматривается ниже.
Критерии останова процесса итераций:
1. y ≤ 0
2. |▽f(Xk)| < ε
3. Δf(X) = |f(Xk) - f(Xk-1)| < ε
4. ΔX = |Xk - Xk-1| < ε

Пример 1.
;
;
.
Начальное допустимое значение x0=(3;-1); f(x0) = 16.
Вычислим градиент в точке x0:
;
;
.
Вычислим значение функций g1 и g2 в точке x0=(3;-1):
g1(3;-1)=4; g2(3;-1)=3.8.
Таким образом, нет активных ограничений: I0={} и первая подзадача принимает вид
θ → max
-8d2 + θ ≤ 0
-1 ≤ di ≤ 1
Находим оптимальное решение: θ =8; d*=(0;1)
Теперь на луче x=x0+αd,
, α > 0
требуется найти точку, в которой он пересекает границу области S.
Подставим эту точку в первое ограничение:
g1(x) = 2*3 – (-1+α)2 -1 = α2 - 2α – 4 = 0, -1.2361 ≤ α ≤ 3.2361
С учетом α > 0, получим 0 < α ≤ 3.2361
g2(α) = 9 – 0.8(3)2 – 2(-1+α) = 3.8α – 2, 0 ≤ α ≤ 1.9
Отсюда α = min{3.2361; 1.9} = 1.9
Исследуем отрезок 0 < α ≤ 1.9 для определения экстремальной точки функции
f(α) = (3 - 3)2 + (-1+α-3)2 = (α-4)2 → min
Поэтому α = 4 < 1.9
x1 = x0 + αd = (3; 0.9)

2-я итерация:
x1 = (3; 0.9)
g1(x1) = 4,19
g2(x2) = 0
Таким образом, активное ограничение g2: I0={2}
; ;
.
Далее решается ЗЛП:
θ → max
0*d1 -4.2d2 + θ ≤ 0
-4,8d1 -2d2 - θ ≥ 0
-1 ≤ di ≤ 1
Решение этой задачи d1=(-1;0.774) и θ=3,25.
Поиск на луче x = x1 + αd1
, α > 0
требуется найти точку, в которой он пересекает границу области S.
Подставим эту точку в первое ограничение:
g1(x) = 2*(3-α) – (0.9+0.774α)2 -1 = 0.599α2 + 3.393α – 4.19 = 0, -6.706 ≤ α ≤ 1.04
С учетом α > 0, получим 0 < α ≤ 1.04
g2(α) = 9 – 0.8(3-α)2 – 2(0.9+0.774α), 0 M α ≤ 4.065
Отсюда α = min{1.04; 4.065} = 1.04
Исследуем отрезок 0 ≤ α ≤ 1.04 для определения экстремальной точки функции
f(α) = (3-α - 3)2 + (0.9+0.774α -3)2 = 1.599α2 – 3.25α +4.41→ min
Поэтому α = 1.01 < 1.04
x1 = x0 + αd = (1.99; 1.68)
g1(x1) = 0,15
g2(x2) = 2.46
Таким образом, нет активных ограничений: I0={}
Итеративный процесс можно продолжить подобным образом вплоть до достижения точки минимума x*(2.5; 2) в пределах заданной погрешности. Итерации показаны на рисунке.

Рис. 1 – Область допустимых значений

В алгоритме Зойтендейка учитываются только активные ограничения в данной допустимой точке, при этом получается зигзагообразный процесс, замедляющий решение, а в некоторых случаях приводящий к "заеданию" - тип ложной сходимости.
К методам, свободным от этих недостатков, можно отнести метод -возмущений и метод Топкинса и Вейнотта.
Методами допустимых направлений нельзя непосредственно пользоваться для решения задач с нелинейными ограничениями-равенствами hk(x)=0. В этом случае эти ограничения-равенства необходимо ослабить, допустив ограниченное перемещение вне поверхности, задаваемой ограничениями
- ε ≤ hk(x) ≤ ε.
Однако если ε мало, то одномерный поиск осуществляется небольшими шагами и скорость процесса невелика. С другой стороны, если допускается ограниченное движение вне границ области допустимых значений S, облегчающее выбор допустимого направления, то итеративное решение соответствующих ограничениям уравнений нужно проектировать на область S (рис 2).

Рис. 2
Другим существенным недостатком метода допустимых направлений является необходимость решения подзадач ЛП.

Открыть диалог Discus Помощь в решении