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

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

 

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

Группа:             АС-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(х)^Td<0.

ЛЕММА. Рассмотрим задачу минимизации f(х) при условиях Ах£b и Ех=е. Пусть х—допустимая точка, и предположим, что А₁x=b₁ и А₂x<b₂, где А^T=(А₁^T, А₂^T), а b^T=(b₁^T, b₂^T). Тогда ненулевой вектор и является возможным направлением в точке х в том и только в том случае, если A₁d£0 и Еd=0. Если, кроме того, Ñf(х)^Td<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(х)^Td=-8d₁+2d₂, то он является направлением спуска. Таким образом, совокупность направлений спуска определяется открытым полупространством {(d₁,d₂}: -8d₁+2d₂<0}. Пересече­ние конуса возможных направлений с этим полупространством задает множество всех возможных направлений спуска.

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

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

Пусть задана допустимая точка х. Как показано в лемме, ненулевой вектор и является возможным направлением спуска. Естественный подход к построению такого направления заключается в минимизации Ñf(х)^Td. Заметим, однако, что если существует вектор d, такой, что Ñf(х)^Td <0, А₁d£0, Еd= 0, то оптимальное значение целевой функции в сформу­лированной задаче равно — ¥, так как ограничениям этой за­дачи удовлетворяет любой вектор ld, где 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.

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

где         определяется в соответствии с (1). Положить              , определить новое множество активных ограниче­ний в и переопределить А₁ и А₂. Заменить k на k+1 и перейти к шагу 1.

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

Итерация 1

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

Рис. 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 изображен процесс поиска решения в соответствии с описанным алгоритмом.

 

 

Поделиться:

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