Реферат: Метод Зойтендейка

ГК и ВО России

НГТУ

Кафедра АСУ

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

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

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

Группа: АС-513

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

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

Новосибирск

1997

Содержание:

Введение2

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

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

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

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

Задачи с нелинейными ограничениями-неравенствами 9

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

ограничений-неравенств)11

Учет нелинейных ограничений-равенств 14

Использование почти активных ограничений 15

Список литературы18

Введение

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

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

ОПРЕДЕЛЕНИЕ. Рассмотрим задачу минимизации f (х) при условии, что х ÍS, где f : Е_n -Е₁ , а 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является возможным направлением спуска, если A₁ d£0, Еd= 0 и Ñ f(х)^T d< 0.

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

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

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

ПРИМЕР

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

(x₁ -6)² +(x₂ -2)²

-x₁ +2x₂ £4

3x₁ +2x₂ £12

-x₁ £0

-x₂ £0

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

- d₁ +2d ₂ £0,

3d₁ + 2d₂ £0.

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

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

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

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

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

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

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

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

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

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

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

при условиях

Предположим теперь, что А ^T =(А₁ ^T , А₂ ^T ), а b^T =(b₁ ^T , b₂ ^T ), такчто и .Тогда задачу одномерной мини­ мизации можно упростить следующим образом. Во-первых, за­метим, что Ех_k =е и Еd_k =0, так что ограничение излишне. Так как и для всех l³0. Таким образом, рассматриваемая задача приводится к следующей задаче линейного поиска;

(1)

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

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

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

Основной этап. Шаг 1. Пусть задан х _k . Предположим, что А^T =(А₁ ^T , А₂ ^T ), а b^T =(b₁ ^T , b₂ ^T ),так что . Взять в качестве d_k оптимальное решение следующей задачи(заметим, что вместо этой задачи можно использовать Р2 или РЗ):

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

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

Итерация 1

Рис. 2

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

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

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

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

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

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

Итерация 2

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

Рис 3.

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

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

при условии

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

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

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

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

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

при условии

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

Рис 4.

Итерация 3

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

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

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

Таблица 1

Рис. 5. Пои ск решения методом Зойтендейка (случай линейных ограничений).

В табл. 1 приведены результаты вычислений для рассмо­тренной задачи. На рис. 10.5 изображен процесс поиска решения в соответствии с описанным алгоритмом.

Задачи с нелинейными ограничениями-неравенствами

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

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

при условиях g _i (х) £0,i=1, ...,m.

В теореме формулируются достаточн ые условия, при которых вектор d является возможным направлением спуска.

Ри с. 6. Совокупность возможных н аправлений спуска в задаче с нелиней­ными ограничен иями. 1— 1- е ограни чение; 2—3-е ограничение; 3—4-е ограни­чение; 4— 2-е ограничение; 5— возможные направления спуска; 6— линии уровня целевой функции.

Доказательство. Пусть вектор и удовлетворяет неравенствам и при . Для выполняютсянеравенства , и так как g_i непрерывн ы в точке х, то для достаточно малых . В силу дифференцируемости функций g_i при имеем

где при . Так как , то при достаточно малых . Следовательно, при i = 1, . . ., m, т.е. точка допустимая для достаточно малых положи тельных значений . Аналогично из следует, что для достаточно малых > 0 имеем . Следов ательно, вектор и является возможным направлением спуска.

На рис. 6 показана совокупность возможных направлений спуска в точке х. Вектор d , удовлетворяющий равенству , является касательн ым к множеству в точке х. Поскольку функции g_i нелинейны, движение вдоль такого вектора d может привести в недопустимую точку, что вы­нуждает нас тре бовать выполнения строгого неравенства .

Пусть (z, d)—оптимальное решение этой задачи линейного про­граммирования. Если z <0, то очевидно, что d—возможное направление спуска. Если же z= 0, то, как показано ниже, те­кущая точка является точкой Ф. Джона.

Точка х является точкой Ф. Джона для исходной задачи тогда и только тогда, когда оптимальное значение целевой функции задачи поиска направления равно нулю.

Точка х является точкой Ф. Джона для и сходной задачи тогда и только тогда, когда опти мальное значение целевой функции задачи поиска направле ния равно нулю.

Это и есть условие Ф. Джона.

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

Начальный этап. Выбрать начальную точку х₁ , для которой g_i (x_i )£0 при i= 1, ..., m. Полож ить k= 1 и перейти к ос­новному этапу.

Основной этап. Шаг 1. Положить и ре­шить следующую задачу:

Пусть ( z_k , d_k ) — оптимальное решени е. Если z_k =0, то остано­виться; x_k является точкой Ф. Джона. Если z_k < 0, то перейти к шагу 2.

где. Положить . заменить k на k+ 1 и перейти к шагу 1.

Решим эт у задачу методом Зойтендейка. Начнем процесс из точки .Отметим, что

Итерация 1

Можно легко проверить, используя симплекс-метод, что оптимальным решением этой задачи является вектор

Ли нейный поиск. Любая точка по направлению d ₁ == (1.00, —1.00)^T из точки x_i = (0.00, 0.75) ^T может быть представлена в виде ,а соответствующее ей значение целевой функци и равно . Макси­мальное значение, для которого остается допустимой точкой, равно == 0.414. При этом значении l активным ста­новится ограничение . Значение l получается из решения следующей задачи одномерной ми нимизации:

минимиз ировать 6l² —2.5l—3.375

при условии 0£l£0.414

Оптимальное значение равно l ₁ = 0.2083. Следовательно, х ₂ = (x₁ + l₁ d₁ ) -( 0.2083,0.5417)^T .

Итерация 2

Поиск направления. В точке x₂ = (0.2083, 0.5417) ^T имеем ( х₂ )= (— 4,2500, —4.2500) ^T Активных ограничений в этой точке нет, и поэтому задача определения направления имеет вид

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

при условиях —4.25d₁ —4.25d₂ —z£ 0,

-1< d₁ <1, j =1, 2.

Оптимальным решением является вектор d₂ =(1, 1) ^T , а z₂ = -8.50.

Линейный поиск. Можно легко проверить, что мак­ симальное l, при котором точка x₂ +ld₂ допустима, равно l_max == 0.3472. При этом активным становится ограничение . Значение l₂ получается минимизацией при условии и, оче­видно, равно l₂ = 0.3472, так что х_з = х ₂ +l ₂ d₂ = (0.5555, 0.8889)^T .

Итерация 3

Оптимальным решением является вектор.

Лин ейный поиск. Максимальное значение l при котором точка x _з + l d_з допустима, равно l_max = 0,09245. При этом l ак­ти вным становится ограничение . Значение l₃ полу­чается минимизациейпри условии 0,09245. Оптимальным решением этой за­дачи являетсяl₃ = 0.09245, так что = (0.6479, 0.8397)^T .

Итерация 4

Поиск, направления. Для точки х₄ = (0.6479, 0.8397) ^T имеем =(— 3 .0878, —3.9370)^ а I ={2}. Задача определения направления имеет вид

Оптимальным решением этой задачи является вектор d₄ = (-0.5171, 1.0000) ^T и z₄ = — 2.340.

Линейный поиск. Максимальное значение К , для которого точках₄ + ld₄ допустима, равно l _{m ах} = 0.0343. При этом огра­ничение становится активным. Значение l₄ полу­чается минимизацией f (x₄ + ld₄ ) == 3,569l ² — 2.340l —6.4681 при условии и равно l ₄ = 0.0343. Следовательно, новой точкой является x₅ == x₄ + l₄ d₄ = (0.6302, 0.8740)^T .Значе­ ние целевой функции в этой точке равно -6.5443, т. е. сравня ю со значением —6.5590 в оптимальной точке (0.658872, 0.808226)^T .

В табл. 2 приведены результаты вычислений на первых четырех итерациях метода. На рис. 7 показан процесс поиска оптимума.

Таблица 2

Рис 7

Учет нелинейных ограничений-равенств

М етод возможных направлений может быть модифицирован на случай, когда имеются нелинейные ограничения-равенства. Для иллюстрации обратимся к ри с. 8, который отвечает единствен­ ному ограничению-равенству. Для заданной допустимой точки х _k , в этом случае не существует ненулевого направления d, та­кого, что при для некоторого положи­тельного d. Это затруднение можно преодолеть, если двигаться вдол ь касательного направлени я d_k , для которого , а затем скорректировать движение и возвратиться в до­ пустимую область.

Рис. 8. Нелине йные ограничения-равенства. 1 —касательное н аправл ени е; 2 — корректирующее движение в допусти мую область.

Чтобы быть более точным, рассмотрим следующую задачу:

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

при условиях g_i (х)£0, i= 1,..., m,

h_i (х)= 0, i =1, ...,i.

Рис. 9. Использование поч ти активных ограничений. 1 — опти мальное решение; 2— линии уровня целевой функции; 3—1-е ограничение; 4— 2-е ограничение.

Использование почти активных огран ичений

Напомним задачу определения направлени я как для случая ли­ нейных, так и нелинейных ограничений-неравенств. Если задан­ная точка близка к границе, определяемой одним из ограниче­ний, и если это ограничени е не используется в процессе нахож­дения направления движения, то может случиться так, что удастся сделать только маленький шаг и мы окажемся на гра­нице, определяемой этим ограничением. На рис. 9 в точке х активным является только первое ограничение. Однако точка х близка к границе, определяемой вторым ограничением. Если м ножество I в задаче определения направления задать в виде I ={ 1}, то оптимальным будет направление d и до выхода на границу допустимой области можно сделать только маленький шаг. Если же в множество активных ограничений включить оба ограничения, т. е. положи ть I={1, 2) , то решение задачи Р

определения направления даст вектор и , который обеспечивает большие возможности для движения в рамках допустимой об­ласти. Таким образом, это н аводи т на мысль о том, что в ка­честве множества I следует брать совокупность индексов почти активных ограничений. Точнее, вместо множества { i: g_i (х)= 0} в качестве I следует брать множество { i ,g_i (х)+е ³0}, где е>0—достаточно малое чи сло. Метод возможных направлений не обязательно сходится к точке Ф. Джона. Это

следует из того, что соответствующее алгоритмическое отображение незамкнуто. При более формальном использовании введённого здесь понятия почти активного ограничения можно установить замкнутость алгоритмического отображения и, следовательно, сходимость общего алгоритма.

Список литературы:

1. М. Базара, К. Шеттл «Нелинейное программирование. Теория и алгоритмы» М.: Мир 1982

2. Д. Химмельблау «Прикладное нелинейное программирование» М.: Мир 1975