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

Размещено на http://www.allbest.ru/

ГК и ВО России

НГТУ

Кафедра АСУ

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

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

Группа: АС-513

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

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

Новосибирск 1997

Содержание

Введение

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

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

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

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

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

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

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

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

Введение

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

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

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

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

Вначале рассмотрим случай, когда допустимая область S определена системой линейных ограничений, так что рассматриваемая задача имеет вид минимизировать f(х) при условиях Ахb, Ех=е.

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

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

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

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

ПРИМЕР

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

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

-x1+2x24

3x1+2x212

-x10

-x20

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

-d1+2d20,

3d1+2d20.

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

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

линейный минимизация зойтендейк

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

Пусть задана допустимая точка х. Как показано в лемме, ненулевой вектор и является возможным направлением спуска. Естественный подход к построению такого направления заключается в минимизации f(х)Td. Заметим, однако, что если существует вектор d, такой, что f(х)Td <0, А1d0, Е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 или РЗ равно нулю.

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

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

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

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

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

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

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

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

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

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

Шаг 2. Положить равным оптимальному решению еле-., дующей задачи линейного поиска:

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

Итерация 1

Поиск направления. В точке имеем. Кроме того, в точке x1 активными являются только ограничения неотрицательности переменных, так что l = {3,4}. Задача для нахождения направления имеет вид

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

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

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

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

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

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

Итерация 2

Поиск, направления.

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

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

при условии

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

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

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

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

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

при условии

Итерация 3

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

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

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

Результаты вычислений по методу Зойтендейка для случая линейных ограничений

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

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

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

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

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

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

ТЕОРЕМА. Рассмотрим задачу минимизации f(х) при условиях gi (х)0, i=1, ...,m.. Пусть х--допустимая точка, а I--множество индексов активных в этой точке ограничений, т. е. Предположим, кроме того, что функции f и gi для дифференцируемы в х, а функции gi для непрерывны в этой точке. Если при, то вектор d является возможным направлением спуска.

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

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

Чтобы найти вектор d, удовлетворяющий неравенствам для, естественно минимизировать максимум из и для. Обозначим этот максимум через z. Вводя нормирующие ограничения. Для каждого j, получим следующую задачу для нахождения направления.

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

ТЕОРЕМА. Рассмотрим задачу минимизации f(х) при условиях gi(х)0, i = 1,..., m. Пусть х--допустимая точка, а. Рассмотрим следующую задачу нахождения направления:

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

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

Доказательство. Оптимальное значение целевой функции в сформулированной задаче нахождения направления равно нулю в том и только в том случае, если система неравенств при не имеет решения. По теореме для того, чтобы эта система не имела решения, необходимо и достаточно, чтобы существовали такие числа uo и ui.

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

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

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

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

Пусть (zk, dk) -- оптимальное решение. Если zk=0, то остановиться; xk является точкой Ф. Джона. Если zk < 0, то перейти к шагу 2.

Шаг 2. Взять в качестве ^ оптимальное решение следующей задачи одномерной минимизации:

ПРИМЕР. Рассмотрим задачу

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

Итерация 1

Поиск направления. В точке х1 = (0.00, 0.75)T имеем а множество индексов активных ограничений есть I= {3}. Задача нахождения направления имеет вид

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

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

минимизировать 62--2.5--3.375

при условии 00.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--z0, -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,5692-- 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 показан процесс поиска оптимума.

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

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

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

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

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

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

Пусть xk--допустимая точка и l= {i. gi(хk)==0}. Решим следующую задачу линейного программирования:

Искомое направление dk является касательным к ограничениям-равенствам и к некоторым активным нелинейным ограничениям-неравенствам. Линейный поиск вдоль dk н последующее возвращение в допустимую область приводят в точку хk+1, после чего процесс повторяется.

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

Напомним задачу определения направления как для случая линейных, так и нелинейных ограничений-неравенств. Если заданная точка близка к границе, определяемой одним из ограничений, и если это ограничение не используется в процессе нахождения направления движения, то может случиться так, что удастся сделать только маленький шаг и мы окажемся на границе, определяемой этим ограничением. На рис. 9 в точке х активным является только первое ограничение. Однако точка х близка к границе, определяемой вторым ограничением. Если множество I в задаче определения направления задать в виде I= {1}, то оптимальным будет направление d и до выхода на границу допустимой области можно сделать только маленький шаг. Если же в множество активных ограничений включить оба ограничения, т. е. положить I={1, 2), то решение задачи Р определения направления даст вектор и, который обеспечивает большие возможности для движения в рамках допустимой области. Таким образом, это наводит на мысль о том, что в качестве множества I следует брать совокупность индексов почти активных ограничений. Точнее, вместо множества {i: gi(х)=0} в качестве I следует брать множество {i, gi(х)+е0}, где е>0--достаточно малое число. Метод возможных направлений не обязательно сходится к точке Ф. Джона. Это следует из того, что соответствующее алгоритмическое отображение незамкнуто. При более формальном использовании введённого здесь понятия почти активного ограничения можно установить замкнутость алгоритмического отображения и, следовательно, сходимость общего алгоритма.

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

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

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

Размещено на Allbest.ru

...