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



                               ГК и ВО России
                                    НГТУ
                                 Кафедра АСУ


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

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



Факультет:  АВТ
Группа:     АС-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(х)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  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,
-10—достаточно малое число. Метод возможных направлений не обязательно
сходится к точке Ф. Джона. Это
следует из того, что соответствующее алгоритмическое отображение
незамкнуто. При более формальном использовании введённого здесь понятия
почти активного ограничения можно установить замкнутость алгоритмического
отображения и, следовательно, сходимость общего алгоритма.
Список литературы:

1. М. Базара, К. Шеттл «Нелинейное программирование. Теория и алгоритмы»
   М.: Мир 1982
2. Д. Химмельблау «Прикладное нелинейное программирование» М.: Мир 1975
-----------------------
[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]



[pic]

[pic]

[pic]

[pic]

[pic]