Метод Зойтендейка
ГК и ВО России
НГТУ
Кафедра АСУ
Реферат на тему:
Метод Зойтендейка
Факультет: АВТ
Группа: АС-513
Студент: Ефименко Д.В.
Преподаватель: Ренин С.В.
Новосибирск
1997
Содержание:
Введение 2
Случай линейных ограничений 2
Геометрическая интерпретация возможного
направления спуска 2
Построение возможных направлений спуска 3
Задачи с нелинейными ограничениями-неравенствами 9
Алгоритм метода Зойтендейка (случай нелинейных
ограничений-неравенств) 11
Учет нелинейных ограничений-равенств 14
Использование почти активных ограничений 15
Список литературы 18
Введение
Я хочу описать Вам метод возможных направлений
Зойтендейка. На каждой итерации метода строится возможное направлен
ие спуска и затем проводится оптимизация вдоль этого направления.
Следующее определение вводит понятие возможного направления спуска.
ОПРЕДЕЛЕНИЕ. Рассмотрим задачу минимизации
f(х) при условии, что
х⊆S, где
f: Е
nаЕ1, а SтАФнепустое мноВнжество из
Еn. Ненулевой вектор d называется возможным направлением в точке х⊆S,
если существует такое δ>0, что
х
+λx
⊆S для всех
λ⊆(0,δ). Вектор d называется возможным направлением спуска в точке x⊆S, если существует такое δ>0, что
f(х+λd)<f(x) и х+λd⊆S для всех
λ⊆(0, 6).
Случай линейных ограничений
Вначале рассмотрим случай, когда допустимая область S опреВнделена системой линейных ограничений, так что рассматриваеВнмая задача имеет вид
мин
имизировать
f(х)
при условиях
Ах≤b,
Ех
=е.
Здесь АтАФматрица порядка
m × n,
ЕтАФматрица порядка l × n, b есть m-мерный вектор, а
е есть
l-мерный вектор. В следующей лемме приводятся соответствующие характеристики допустимой области и формулируются достаточные условия для существоВнвания возможного направления спуска. В частности, вектор
d является возможным направлением спуска, если A1d≤0, Еd
=0 и
∇f(х)Td
<0.
ЛЕММА. Рассмотрим задачу минимизации
f(х) при условиях
Ах≤b и Ех
=е. Пусть
хтАФдопустимая точка, и предположим, что А1x=b1 и А2x<
b2, где АT=(А1T,
А2T), а bT=(b1T, b2T). Тогда ненулевой вектор
и является возможным направлением в точке х в том и только в том случае, есл
и A1d≤0 и Е
d=0. Если, кроме того,
∇f(х)Td<0, то d является возможным направлением спуска.
Геометрическая интерпретация возможного направления спуска
Проиллюстрируем теперь геометрически на примере множество возможных направлений спуска.
ПРИМЕР
Минимизировать при условиях
(x1-6)2+(x2-2)2
-x1+2x2≤4
3x1+2x2≤12
-x1≤0
-x2≤0
Возьмем
х=(2, 3)T и заметим, что первые два ограничении
являются активными в этой точке. В частности, матрица
А1 из леммы равна А1
=[-13 22]. Следовательно, вектор
d является возможным направлением
тогда и только тогда, когда
А1d≤0, т.е. в том и только в том случае, есл
и
-d1+2
d2≤0,
3d1
+2d2≤0.
На рис. 1, где начало координат перенесено в точку
х, изоВнбражена совокупность этих направлений, образующая конус возможных направлений. Заметим, что если сдвинуться на не
Внбольшое расстояние от точки х вдоль любого вектора d, удовВнлетворяющего двум приведенным выше неравенствам, то остаВннемся в допустимой о
бласти.
Если вектор d удовлетворяет неравенству
0>∇f(х)Td=-8d1+2d2, то он является направлением спуска. Таким образом, совокупность направлений спуска определяется
откры
тым полупространством
{(
d1,d2}:
-8d1+2d2<0
}
. ПересечеВнние конуса возможных направлен
ий с эт
им полупространством задает множество всех возможных направлений спуска.
Рис. 1. Возможные направления спуска
,
1тАФконус возможных направлеВнний: 2 тАФ конус возможных направ
лен
ий спуска; 3 тАФ линии уровня целевой функции; 4 тАФ полупространство направлений спуска.
Построение возможных направлений спуска
Пусть задана допустимая точка
х. Как показано в лемме , ненулевой вектор
и является возможным направлением спуска. Естественный подход к построению такого направления заключается в минимизации ∇f(х)Td. Заметим, однако, что если существует вектор d, такой, что
∇f(х)Td <0,
А1d≤0, Еd
= 0, то оптимальное значение целевой функции в сформуВнлированной задаче равно тАФ
∞ , так как ограничениям этой заВндачи удовлетворяет любой вектор
λd, где λтАФсколь угодно большое число. Таким образом, в задачу должно быть включено условие, которое ограничивало бы вектор
и или оптимальное значение целевой функции. Такое ограничен
ие обычно называют нормирующим. Ниже приведены три задачи построения возможВнного направления спуска, В каждой из этих задач используются различные формы нормировки.
Задачи Р1 и
РЗ являю
тся задачами линейного программироВнвания и, следовательно, могут быть решены симплекс-методом. Задача Р2 содержит квадратичное ограничение, но может быть рассмотрена в несколько упрощенном виде. Так как d
= 0 является допустимой точкой в каждой из приведенВнных выше задач и так как значение целевой функции в этой точке равно нулю, то ее оптимальное значение в задачах Р1, Р2 и РЗ не может быть положительным. Если минимальное значеВнние целевой функции в задачах Р1, Р2 или РЗ отрицательно, то по лемме построено возможное направление спуска. С другой стороны, если минимальное значение целевой функции равно нулю, то, как показано ниже,
х является точкой Куна тАФ
Таккера.
ЛЕММА. Рассмотр
им задачу минимизации
f(х) при условиях
Ах≤b и
Ех
=
е. Пусть х тАФ допустимая точка, для которой А1x=b и А2x<b2, где
АT=(А1T, А2T), а bT=(b1T, b2T). Тогда х является точкой КунатАФТаккера в том и только в том случае, если оптимальное значение целевой функции в задачах Р1, Р2 или РЗ равно нулю.
Доказательство. Вектор х является точкой КунатАФТаккера тогда и только тогда, когда существуют векторы u≥0 и v, такие, что . По следствию 2 из теоремы эта система разреш
има в том и только в том случае, если система не имеет решен
ий, т.
е. тогда и только тогда, когда оптимальное значение в задача
x Р1, Р2 или РЗ равн
о нулю.
Л
инейный по
иск
Только что было показано, как строить возможное направление спуска или убедиться, что текущая точка удовлетворяет условиям КунатАФ
Таккера. Пусть теперь
хk тАФтекущая точка, а
dk-возможное направление спуска. В качестве следующей точки xk+1 берется , где длина шага
К& определяется из решеВнния следующей задачи одном
ерной мин
имизации:
Минимизировать
при условиях
Предположим теперь, что
АT=(А1T, А2T), а bT=(b1T, b2T), так что и . Тогда задачу одномерной мини
Внмизации можно упростить следующим образом
. Во-первых, заВнметим, что Ех
k=е и Е
dk=0, так что ограничение излишне. Так как и для всех λ≥0. Таким образом, рассматриваемая задача приводится к следующей задаче линейного поиска;
(1)
Алгоритм метода
Зойтендейка (случай линейных ограничений)
Ниже приведен алгоритм метода Зойтендейка для минимизации дифференцируемой функц
ии f при условии, что .
Начальный этап. Найти начальную допустимую точку
х1, для которой
. Положить k
= 1 и перейти к основВнному этапу.
Основной этап. Шаг 1. Пусть задан
хk. Предположим, что АT=(А1T, А2T), а bT=(b1T, b2T), так что . Взять в качестве dk оптимальное решение следующей задачи (заметим, что вместо этой задачи можно использовать Р2 или
РЗ):
Если , то остановиться;
хkтАФточка КунатАФ
Таккера, В противном случае перейти к шагу 2.
Шаг 2. Положить равным оптимальному решению
еле
-., дующей задачи линейного поиска:
где определяется в соответствии с (1). Положить
, определить новое множество активных ограничеВнний в и переопределить А1 и
А2. Заменить k на
k+1 и перейти к шагу 1.
Заметим, что
. Решим задачу методом
Зойтендейка, взяв в качестве начальной точки
. Каждая итерация алгоритма содержит решение подзадачи, определенной в описании шага 1
, для нахождения направления, а затем линейный поиск вдоль этого направления.
Итерация 1
Поиск напра
вления. В точке имеем
. Кроме того, в точке x1 активными являются тольВнко ограничения неотрицательности переменных, так что l
= {3,4
}. Задача для нахождения направления имеет вид
Рис. 2
Эту задачу можно решить симплекс методом для решения задач линейного программирования. На рисунке 2 показана допустимая область этой задачи.
Линейный поиск. Теперь, двигаясь из точки (0, 0) вдоль направления (1, 1), нужно найти точку, в которой значение це
Внлевой функции м
ин
имально. Любая точка может быть записана в виде , а целевая функция в этой точке пр
инимает вид
. Максимальное значени
е коэффициента λ, для коВнторого точка допустима,
вычисляется по формулам и равно
Следовательно, если тАФновая точка, то знач
ение поВнлучается из решения следующей задачи одномерной минимиВнзации:
минимизировать тАФ10+2
при условии
0≤ ≤ .
Очевидно, что решением является
, так что
Итерация 2
Поиск
, направления. В точке имеем .
Рис 3.
Кроме того, множество активных
ограниче
ний в точке х2 равно l={2
}, так
что направление движения получается из решения следующей за
дачи:
минимизировать
при условии
Читатель может проверить на рис. 3, что оптимальным решеВннием этой задачи линейного программирования является точка
, а соответствующее значение целевой функции равно
.
Линейный поиск. При начальной точке
х2 любая точка в наВнправлени
и
d2 может быть представлена в
виде Соответст
вующее ей значение целевой функВнци
и равно
Макс
имально
е значение λ для которого точка Х2+λd2 остается допустимой, определяется в соответствия с (1) следующи
м образом:
Таким образом, в качестве
^ берется оптимальное решение слеВндующ
ей задачи:
минимизировать
при условии
Оптимальным решением этой задачи является ,
так
что
Рис 4.
Итерация 3
Поиск напра
вления. В точк
е х
3= имеем
Кроме того, множество активных ограниВнчений в точке
хз равно l
=
{2
}, так что направление движения получается из решения следующей задачи:
Можно легко проверить по рис. 4. что действительно является решением этой задачи лиВннейного программирования. Соответствующее значение целевой функции равно нулю, и процедура заканчивается. Более того, точка является точко
й КунатАФТакк
ера.
В этой конкретной задаче функция f выпукла, и по теореме 4.3.7 точка
х является оптимальным решением.
Таблица 1
Результаты вычислен
ий по методу
Зойтендейка для случая линейных ограничений
Рис. 5. По
иск решения методом
Зойтендейка (случай линейных ограни
чений).
В табл. 1 приведены результаты вычислений для рассмоВнтренной задачи. На рис. 10.5 изображен процесс поиска решения в соответствии с описанным алгоритмом.
Задачи с нелинейными ограничениями-неравенствами
Теперь рассмотрим задачу, в которой допустимая область заВндается системой ограничений-неравенств не обязательно лиВннейных:
минимизировать
f(х)
при условиях
gi
(х)≤0, i=1, ..,m.
В теореме формулируются достаточ
ные условия, при которых вектор d является возможным направлением спуска.
ТЕОРЕМА. Рассмотрим задачу минимизации
f(х) при условиях gi (х)≤0, i=1, ..,m. Пусть хтАФдопустимая точка, а IтАФмножество индексов активных в этой точке ограниВнчений, т.
е.
. Предположим, кроме того, что функции f и gi для дифференцируемы в х, а функции
gi для непрерывны в этой точке. Если при , то вектор d является возможным наВнправле
нием спуска.
Р
ис. 6. Совокупность возможных
направлений спуска в задаче с нелинейВнными ограниче
ниями. 1тАФ 1
-е огран
ичение; 2тАФ3-е ограничение; 3тАФ4-е ограниВнчение; 4тАФ 2-е ограничение; 5тАФ возможные направления спуска; 6тАФ линии уровня целевой функции.
Доказательство. Пусть вектор
и удовлетворяет неравенствам и при . Для выполняются неравенства ,
и так как gi непрерыв
ны в точке
х, то для достаточно малых . В силу
дифференцируемости функций gi при имеем
где при
. Так как , то при достаточно малых . Следовательно, при i
= 1,
.
.
.,m, т.е. точка допустимая для достаточно малых полож
ительных значений . Аналогично из следует, что для достаточно малых
> 0 имеем . Следо
вательно, вектор
и является возможным направлением спуска.
На рис. 6 показана совокупность возможных направлений спуска в точке х. Вектор
d, удовлетворяющий равенству , является касатель
ным к множеству
в точке х. Поскольку функции gi нелинейны, движение вдоль такого вектора d может привест
и в недопустимую точку, что выВннуждает нас тр
ебовать выполнения строгого неравенства .
Чтобы найти вектор d, удовл
етворяющий неравенствам для , естественно мин
имизиВнровать максимум из
и для . Обозначим этот макс
имум через z. Вводя нормирующие ограничен
ия
Для каждого
j, получим следующую задачу для нахождения направления.
Пусть (z, d)тАФоптимальное решение этой задачи линейного проВнграммирования. Если
z<0, то очевидно, что dтАФвозможное направление спуска. Если же z
= 0, то, как показано ниже, теВнкущая точка является точкой
Ф. Джона.
ТЕОРЕМА
. Рассмотрим задачу минимизации
f(х) при условиях
gi(х)≤0, i
= 1
,.., m. Пусть
хтАФдопустимая точка, а
. Рассмотрим следующую задачу наВнхождения направления:
Точка х является точкой Ф. Джона для исходной задач
и тогда и только тогда, когда оптимальное значение целевой функции задачи поиска направления равно нулю.
Точка
х является точкой
Ф. Джона для
исходной задач
и тогда и только тогда, когда опт
имальное значение целевой функции задачи поиска направл
ения равно нулю.
Доказательство. Оптимальное значение целевой функции в сформулированной задаче нахождения направления равно нулю в том и только в том случае, если система неравенств при не
имеет решения. По теореме для того, чтобы эта система
не имела решения, необход
имо и достаточно, чтобы сущест
вовали такие числа uo и
ui, , что
Это и есть условие Ф. Джона.
Алгоритм метода
Зойтендейка (случай нелинейных ограничений-нера
венств)
Начальный этап. Выбрать начальную точку х1, для которой gi(xi)≤0 пр
и
i= 1,
.., m. Поло
жить
k= 1 и перейти к осВнновному этапу.
Основной этап. Шаг
1. Положить и реВншить следующую задачу:
Пусть
(
zk, dk) тАФ оптимальное решен
ие. Если
zk=0, то останоВнвиться; xk является точкой
Ф. Джона. Если zk
< 0, то перейти к шагу 2.
Шаг 2. Взять в качестве
^ оптимальное решение следующей задачи одномерной минимизации:
где
. Положить . заменить k на
k+1 и перейти к шагу 1.
ПРИМЕР. Рассмотрим задачу
Решим э
ту задачу методом
Зойтендейка. Начнем процесс из точки .Отметим, что
Итерация 1
Поиск направления. В точке
х1
= (0.00, 0.75
)T
имеем а множество инде
ксов активных ограничений есть I=
{3
}. При этом Задача нахождения
направления имеет вид
Можно легко проверить, используя симплекс-метод, что оптимальным решением этой задачи является вектор
Л
инейный поиск. Любая точка по направлению
d1== (1.00, тАФ1.00)T из точки xi
= (0.00, 0.75
)T может быть представлена в виде ,а соответствующее ей значение целевой функц
ии равно . МаксиВнмальное значение , для которого остается допустимой точкой, равно
== 0.414. При этом значен
ии λ активным стаВнновится ограничение . Значение λ получается и
з решения следующей задачи одномерной м
инимизации:
миними
зировать 6λ2тАФ2.5λтАФ3.375
пр
и условии 0≤λ≤0.414
Оптимальное значение равно
λ1= 0.2083. Следовательно,
х2
= (x1
+λ1d1)
-(0.2083,0.5417
)T.
Итерация 2
Поиск направления. В точке
x2= (0.2083, 0.5417
)T имеем
(х2)
=(
тАФ4,2500, тАФ4.2500
)T Активных ограничений в этой точке нет, и поэтому задача определения направления имеет вид
минимизировать z
при условиях тАФ4.25d1тАФ4.25d2тАФz
≤0,
-1
<d1<1,
j=1
,2.
Оптимальным решением является вектор
d2=(1, 1
)T, а z2
= -8.50.
Линейный поиск. Можно легко проверить, что мак
Внсимальное λ, при котором точка x2+λd2 допустима, равно λmax
== 0.3472. При этом активным становится ограничение . Значение λ2 получается минимизацией при условии и, очеВнвидно, равно λ2 = 0.3472, так что
хз
=
х2 +
λ2d2
= (0.5555, 0.8889
)T.
Итерация 3
Поиск направления. В точке xз
= (0,5555, 0.8889)T
имеем (хз)
=(тАФ3.5558, тАФ3.5554
)", а множество индексов активных ограничен
ий есть I
={1}. Задача определения направления имеет вид
Оптимальным решением является вектор .
Ли
нейный поиск. Максимальное значение λ при котором точка
xз
+
λdз допустима, равно λmax
= 0,09245. При этом λ акВнт
ивным становится ограничение . Значение λ3 полуВнчается минимизацией при условии 0,09245. Оптимальным решением этой заВндачи является λ3
= 0.09245, так что
= (0.6479, 0.8397
)T.
Итерация 4
Поиск
, направления. Для точки х
4= (0.6479, 0.8397
)T имеем
=(тАФ
3.0878, тАФ3.9370
)^ а
I={2
}. Задача определения направления имеет вид
Оптимальным решением этой задачи является вектор d4
= (-0.5171, 1.0000
)T и
z4=тАФ 2.340.
Линейный поиск. Максимальное значение
К, для которого точка х4
+λd4 допустима, равно
λmах
= 0.0343. При этом ограВнничение становится активным. Значение λ4 полуВнчается минимизацией
f(x4+ λd4)
== 3,569
λ2тАФ 2.340λ тАФ6.4681 при условии и равно
λ4= 0.0343. Следовательно, новой точкой является x5
==x4
+ λ4d4
= (0.6302, 0.8740)
T. Значе
Внние целевой функции в этой точке равно -6.5443, т.
е. сравн
яю со значением тАФ6.5590 в оптимальной точке (0.658872, 0.808226)T
.
В табл. 2 приведены результаты вычислений на первых четырех итерациях метода
. На рис. 7 показан процесс поиска оптимума.
Таблица 2
Рис 7
Учет нелинейных ограничений-равенств
Метод возможных направлений может быть модифицирован на случай, когда имеются нелинейные ограничения-равенства. Для иллюстрации обратимся к р
ис. 8, который отвечает единствен
Внному ограничению-равенству. Для заданной допустимо
й точки
хk, в этом случае не существует ненулевого направления d, таВнкого, что при для некоторого положиВнтельного δ. Это затруднение можно преодолеть, если
двигаться вдо
ль касательного направлен
ия
dk, для которого , а затем скорректировать движение и возвратиться в до
Внпустимую область.
Рис. 8. Нелин
ейны
е ограничения-равенства.
1тАФкасательное
направ
лен
ие
; 2 тАФ корректирующее движение в допуст
имую область.
Чтобы быть более точным, рассмотрим следующую задачу:
минимизировать
f(х)
при условиях gi(х)≤0,
i= 1
,.., m,
hi(х)
=0,
i=1,
..,i.
Пусть
xkтАФдопустимая точка и l=
{i. gi(хk)
==0
}. Решим слеВндующую задачу линейного програ
ммирования:
Искомое направление dk является касательным к ограничеВнниям-равенствам и к некоторым активным нел
инейным ограниВнчениям-неравенствам. Линейный поиск вдоль dk
н последующее возвращение в допустимую область приводят в точку
хk+1, после чего процесс повторяется.
Рис. 9. Использование по
чти активных ограничений. 1 тАФ опт
имальное решение; 2тАФ линии уровня целевой функции; 3тАФ1-е ограничение; 4тАФ 2-е ограничение.
Использовани
е почти активных
ограничений
Напомним задачу определения направлен
ия как для случая л
иВннейных, так и нелинейных ограничений-неравенств. Если заданВнная точка близка к границе, определяемой одним из ограничеВнний, и если это ограничен
ие не используется в процессе нахожВндения направления движения, то может случиться так, что удастся сделать только маленький шаг и мы окажемся на граВннице, определяемой этим ограничением. На рис. 9 в точке х активным является только первое ограничение. Однако точка х близка к границе, определяемой вторым ограничением. Если
множество I в задаче определения направления задать в виде
I=
{1
}, то оптимальным будет направление d и до выхода на границу допустимой области можно сделать только маленький шаг. Если же в множество активных ограничений включить оба ограничения, т.
е. полож
ить I={1, 2
), то решение задачи
Р
определения направления даст вектор
и, который обеспечивает большие возможности для движения в рамках допустимой обВнласти. Таким образом, это
навод
ит на мысль о том, что в каВнчестве множества I следует брать совокупность индексов почти активных ограничений. Точнее, вместо множества
{i:
gi(х)
=0
} в качестве I следует брать множество
{
i, gi(х)
+е≥0
}, где е>0тАФдостаточно малое ч
исло. Метод возможных направлений не обязательно сходится к точке
Ф. Джона. Это
следует из того, что соответствующее алгоритмическое отображение незамкнуто. При более формальном использовании введённого здесь понятия почти активного ограничения можно установить замкнутость алгоритмического отображения и, следовательно, сходимость общего алгоритма.
Список литературы:
- М. Базара, К. Шеттл ВлНелинейное программирование. Теория и алгоритмыВ» М.: Мир 1982
- Д. Химмельблау ВлПрикладное нелинейное программированиеВ» М.: Мир 1975
Вместе с этим смотрят:
Метод касательных решения нелинейных уравненийМетод касательных. Решения нелинейных уравненийМетод математической индукцииМетод прогонки