Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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

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

 

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

Группа:             АС-513

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

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

 

Новосибирск

1997

 


Содержание:

Введение                                                                                               2

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

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

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

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

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

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

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

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

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

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

Введение

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

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

ОПРЕДЕЛЕНИЕ. Рассмотрим задачу минимизации 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 является возможным направлением спуска, если 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+2d2£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, то оптимальное значение целевой функции в сформу­лированной задаче равно — ¥, так как ограничениям этой за­дачи удовлетворяет любой вектор ld, где l—сколь угодно большое число. Таким образом, в задачу должно быть включено условие, которое ограничивало бы вектор и или оптимальное значение целевой функции. Такое ограничение обычно называют нормирующим. Ниже приведены три задачи построения

 

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

Задачи Р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, так что ограничение                    излишне. Так как            и                                  для всех l³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), нужно найти точку, в которой значение це­левой функции                                                         минимально. Любая точка может быть записана в виде                       , а целевая функция в этой точке принимает вид                                 . Максимальное значение коэффициента 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

 

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

 

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

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

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...