Метод Зойтендейка

ГК и ВО России

НГТУ

Кафедра АСУ

Реферат на тему:

Метод Зойтендейка

Факультет: АВТ

Группа: АС-513

Студент: Ефименко Д.В.

Преподаватель: Ренин С.В.

1997

Содержание:

Геометрическая
интерпретация возможного

направления спуска
2

Я хочу описать Вам метод возможных направлений Зойтендейка.
На каждой итерации метода строится возможное направлени
е спуска и затем проводится оптимизация вдоль этого направления.

Следующее определение вводит понятие возможного направления спуска.

ОПРЕДЕЛЕНИЕ. Рассмотрим задачу минимизации f
(х) при условии, что х
ÍS, где f
: Еn
-Е1
, а S—непустое мно­жество из Е
n
. Ненулевой вектор d называется возможным направлением в точке хÍS, если существует такое
d>0, что х
+
lxÍ
S для всех l
Í(0,d). Вектор d называется возможным направлением спуска в точке xÍS, если существует такое d>0, что f
(х+ld)<f(x) и х+ldÍS для всех l
Í(0, 6).

Случай линейных ограничений

Вначале рассмотрим случай, когда допустимая область S опре­делена системой линейных ограничений, так что рассматривае­мая задача имеет вид

мини
мизировать f(х)

при условиях Ах£b,

Ех=е
.

Здесь А—матрица порядка m
´ n,Е
—матрица порядка l ´ n, b есть m-мерный вектор, а е
есть l-
мерный вектор. В следующей лемме приводятся соответствующие характеристики допустимойобласти и формулируются достаточные условия для существо­вания возможного направления спуска. В частности, вектор
dявляется возможным направлением спуска, если A1
d£0, Еd=
0 и Ñ
f(х)T
d<
0.

ЛЕММА. Рассмотрим задачу минимизации f
(х) при условиях Ах
£b и Ех=
е. Пусть х—
допустимая точка, и предположим, что А1
x=b1
и А2
x<b2
, где АT
=(А1
T
, А
2
T
), а bT
=(b1
T
, b2
T
). Тогда ненулевой вектор и
является возможным направлением в точке х в том и только в том случае, если
A1
d£0и Еd
=0. Если, кроме того, Ñ
f(х)T
d<0, то d является возможным направлением спуска.

Геометрическая
интерпретация возможного направления спуска

Проиллюстрируем теперь геометрически на примере множество возможных направлений спуска.

ПРИМЕР

Минимизировать при условиях

(x1
-6)2
+(x2
-2)2

-x1
+2x2
£4

3x1
+2x2
£12

-x1
£0

-x2
£0

Возьмем х=
(2, 3)T
и заметим, что первые два ограничении являются
активными в этой точке. В частности, матрица А
1
из леммы равна А1
=
[-1
3
2
2
]. Следовательно, вектор d
является возможным направлением т
огда и только тогда, когда А
1
d£0, т.е. в том и только в том случае, если

-
d1
+2d
2
£0,

3d1
+
2d2
£0.

На рис. 1, где начало координат перенесено в точку х,
изо­бражена совокупность этих направлений, образующая конус возможных направлений. Заметим, что если сдвинуться на не­
большое расстояние от точки х вдоль любого вектора d, удов­летворяющего двум приведенным выше неравенствам, то оста­немся в допустимой об
ласти.

Если вектор d удовлетворяет неравенству 0>
Ñf(х)T
d=-8d1
+2d2
, то он является направлением спуска. Таким образом, совокупность направлений спуска определяется откры
тым
полупространством {(
d1
,d2
}:
-8d1
+2d2
<
0}
.
Пересече­ние конуса возможных направлени
й с эти
м полупространством задает множество всех возможных направлений спуска.

Рис. 1. Возможные направления спуска,
1
—конус возможных направле­ний: 2 — конус возможных направл
ени
й спуска; 3 — линии уровня целевой функции; 4 — полупространство направлений спуска.

Построение возможных направлений спуска

Пусть задана допустимая точка х.
Как показано в лемме , ненулевой вектор и
является возможным направлением спуска. Естественный подход к построению такого направления заключается в минимизации Ñf(х)T
d. Заметим, однако, что если существует вектор d, такой, что Ñ
f(х)T
d <0, А
1
d£0, Еd=
0, то оптимальное значение целевой функции в сформу­лированной задаче равно —
¥, так как ограничениям этой за­дачи удовлетворяет любой вектор l
d, где l—сколь угодно большое число. Таким образом, в задачу должно быть включено условие, которое ограничивало бы вектор и
или оптимальное значение целевой функции. Такое ограничени
е обычно называют нормирующим. Ниже приведены три задачи построения

Задачи Р1 и РЗ
являют
ся задачами линейного программиро­вания и, следовательно, могут быть решены симплекс-методом. Задача Р2 содержит квадратичное ограничение, но может быть рассмотрена в несколько упрощенном виде. Так как d =
0 является допустимой точкой в каждой из приведен­ных выше задач и так как значение целевой функции в этой точке равно нулю, то ее оптимальное значение в задачах Р1, Р2 и РЗ не может быть положительным. Если минимальное значе­ние целевой функции в задачах Р1, Р2 или РЗ отрицательно, то по лемме построено возможное направление спуска. С другой стороны, если минимальное значение целевой функции равно нулю, то, как показано ниже, х
является точкой Куна —
Таккера.

ЛЕММА. Рассмотри
м задачу минимизации f
(х) при условиях Ах
£b и Ех
=
е.
Пусть х — допустимая точка, для которой А1
x=b и А2
x<b2
, где А
T
=(А1
T
, А2
T
), а bT
=(b1
T
, b2
T
). Тогда х является точкой Куна—Таккера в том и только в том случае, если оптимальное значение целевой функции в задачах Р1, Р2 или РЗ равно нулю.

Доказательство. Вектор х является точкой Куна—Таккера тогда и только тогда, когда существуют векторы u³0 и v, такие, что. По следствию 2 из теоремы эта система разреши
ма в том и только в том случае, если система не имеет решени
й, т. е.
тогда и только тогда, когда оптимальное значение в задачаx
Р1, Р2 или РЗ равно
нулю.

Ли
нейный пои
ск

Только что было показано, как строить возможное направление спуска или убедиться, что текущая точка удовлетворяет условиям Куна—Таккера.
Пусть теперь х
k
—текущая точка, а dk
-возможное направление спуска. В качестве следующей точки xk+1
берется, где длина шага К&
определяется из реше­ния следующей задачи одноме
рной мини
мизации:

Минимизировать

при условиях

Предположим теперь, что А
T
=(А1
T
, А2
T
), а bT
=(b1
T
, b2
T
), такчто и .Тогда задачу одномерной мини­
мизации можно упростить следующим образом.
Во-первых, за­метим, что Ехk
=е и Еdk
=0, так что ограничение излишне. Так как и для всех l³0. Таким образом, рассматриваемая задача приводится к следующей задаче линейного поиска;

(1)

Алгоритм метода Зойтендейка
(случай линейных ограничений)

Ниже приведен алгоритм метода Зойтендейка для минимизации дифференцируемой функци
и f при условии, что .

Начальный этап. Найти начальную допустимую точку х
1
, для которой . Положить k=
1 и перейти к основ­ному этапу.

Основной этап. Шаг 1. Пусть задан х
k
. Предположим, что АT
=(А1
T
, А2
T
), а bT
=(b1
T
, b2
T
),так что . Взять в качестве dk
оптимальное решение следующей задачи(заметим, что вместо этой задачи можно использовать Р2 или РЗ):

Если , то остановиться; х
k
—точка Куна—Таккера,
В противном случае перейти к шагу 2.

Заметим, что .
Решим задачу методом Зойтендейка,
взяв в качестве начальной точки . Каждая итерация алгоритма содержит решение подзадачи, определенной в описании шага 1,
для нахождения направления, а затем линейный поиск вдоль этого направления.

Итерация 1

Рис. 2

Эту задачу можно решить симплекс методом для решения задач линейного программирования. На рисунке 2 показана допустимая область этой задачи.

Линейный поиск. Теперь, двигаясь из точки (0, 0) вдоль направления (1, 1), нужно найти точку, в которой значение це­
левой функции ми
ни
мально. Любая точка может быть записана в виде , а целевая функция в этой точке при
нимает вид
. Максимальное значение
коэффициента l, для ко­торого точка допустима, в
ычисляется по формулам и равно

Следовательно, если —новая точка, то значе
ние по­лучается из решения следующей задачи одномерной миними­зации:

минимизировать —10+2

при условии 0
££ .

Очевидно, что решением является ,
так что

Итерация 2

Поиск,
направления. В точке имеем .

Рис 3.

Кроме того, множество активных ограниче
ний
в точке х2
равно l={2},
так ч
то направление движения получается из решения следующей зад
ачи:

минимизировать

при условии

Читатель может проверить на рис. 3, что оптимальным реше­нием этой задачи линейного программирования является точка,
а соответствующее значение целевой функции равно .

Линейный поиск. При начальной точке х
2
любая точка в на­правлении
d2
может быть представлена в виде
Соответств
ующее ей значение целевой функ­ции
равно

Макси
мальное
значение l для которого точка Х2
+ld2
остается допустимой, определяется в соответствия с (1) следующим
образом:

Таким образом, в качестве ^
берется оптимальное решение сле­дующе
й задачи:

минимизировать

при условии

Оптимальным решением этой задачи является ,т
ак что

Рис 4.

Итерация 3

Поиск направ
ления. Вточке
х3
= имеем Кроме того, множество активных ограни­чений в точке хз
равно l =
{
2},
так что направление движения получается из решения следующей задачи:

Можно легко проверить по рис. 4. что действительно является решением этой задачи ли­нейного программирования. Соответствующее значение целевой функции равно нулю, и процедура заканчивается. Более того, точка является точкой
Куна—Такке
ра.

В этой конкретной задаче функция f выпукла, и по теореме 4.3.7 точка х
является оптимальным решением.

Таблица 1