Файл: Методы возможных направлений.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 10.04.2024

Просмотров: 40

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Методы возможных направлений Оглавление Введение 21. Метод Зойтендейка 32. Построение возможных направлений спуска 63. Алгоритм метода Зойтендейка в случае линейных ограничений 94. Алгоритм Зойтендейка в случае нелинейных ограничений-неравенств 135. Модификация метода возможных направлений 18Заключение 22Список использованных источников 23 Введение Методы возможных направлений – наиболее исследованный класс методов выпуклого программирования (задачи выпуклого программирования – это такие задачи нелинейного программирования, в которых целевые функции и функции ограничений выпуклы). Подробное описание данных методов было произведено в работах Зойтендейка1. Хотя сходимость к глобальному минимуму может быть доказана только в случаях задач выпуклого программирования, тем не менее методы возможных направлений сходятся к локальному минимуму и в применении к задачам нелинейного программирования вообще. Цель данной работы - рассмотреть сущность методов возможных направлений. 1. Метод Зойтендейка Типичным представителем класса методов возможных направлений является метод Зойтендейка. На каждой итерации метода находят возможное направление спуска, а затем проводят оптимизацию вдоль этого направления. Для изложения идеи метода введем ряд необходимых понятий2:Рассмотрим задачу минимизаци   при условии, что  , где  – непустое множество.Ненулевой вектор   называется возможным направлением в точке  , если существует такое  , что   для всех  . Вектор   называется возможным направлением спуска в точке  , если существует такое  , что   и   для всех  .Сначала рассмотрим случай, когда ограничения линейные и задача НП имеет вид:минимизировать                               (1)при условиях                                (2)                                           (3)где   – матрица порядка  ;   – матрица порядка  ;  —  -мерный вектор;   —  -мерный вектор.Справедливо следующее утверждение.Лемма 1. Рассмотрим задачу минимизаци (1) - (3). Пусть  - допустимая точка и предположим, что  , где  , а  .Ненулевой вектор   является возможным направлением в точке   в том и только в том случае, если   и  . Если, кроме того,  , то   является возможным направлением спуска.Проиллюстрируем геометрически множество возможных направлений спуска на следующем примере.Пример 1. Минимизировать    при условиях Выберем   и заметим, что первые два ограничения являются активными в этой точке. В частности, матрица   из вышеприведенной  леммы 1, равна  . Следовательно, вектор   является возможным направлением тогда и только тогда, когда   т.е. в том случае, если На рис. 1. изображена совокупность этих направлений, образующая конус возможных направлений. Здесь 1 – конус возможных направлений; 2 – конус возможных направлений спуска;  3 – линии уровня целевой функции; 4 – полупространство направлений спуска. Рисунок 1Если вектор   удовлетворяет неравенству  , то он является направлением спуска. Таким образом, совокупность возможных направлений спуска определяется открытым полупространством  . Пересечение конуса возможных направлений с этим полупространством задает множество всех возможных направлений спуска. 2. Построение возможных направлений спуска Пусть задана текущая допустимая точка x. Как показано в лемме 1, ненулевой вектор   будет возможным направлением спуска, если  .  Естественный подход к построению такого направления заключается в минимизации   при условиях:  . Однако, если существует такой вектор  , что  , и выполняются условия а) и б), то оптимальное значение целевой функции сформулированной задачи  равно –   , так как ограничениям этой задачи удовлетворяет любой вектор  , где   – любое большое число.Следовательно, в задачу должно быть  включено условие, которое бы ограничивало вектор  . Такое ограничение называют нормирующим. Возможны различные формы нормирующего ограничения. Ниже приведем три задачи отыскания (наилучшего) направления спуска, в каждой из которых используются различные условия нормировки3:Задача  :      минимизировать         при условиях Задача  : минимизировать  при условиях Задача  : минимизировать  при условиях Задачи   и   являются задачами линейного программирования и, следовательно, их можно решить симплекс-методом.Так как   является допустимой точкой в каждой из приведенных выше задач, а значение целевой функции в этой точке равно 0, то ее оптимальное значение в задачах  ,  ,   не может быть положительным. Если минимальное значение ц.ф. в задачах  ,  ,   отрицательно, то по лемме 6.1 нами построено возможное направление спуска. С другой стороны, если минимальное значение целевой функции равно нулю, то, как будет показано ниже, точка x является точкой Куна-Таккера.Лемма 2. Рассмотрим задачу минимизаци   приусловиях  . Пусть   – допустимая точка, в которой  , где  . Вектор   является точкой Куна-Таккера тогда и только тогда, когда оптимальное значение целевой функции в задачах  ,  ,   равно нулю.Доказательство. Как следует из теоремы Куна-Таккера,   будет точкой Куна-Таккера тогда и только тогда, когда существуют векторы   такие, что .                          (4)Согласно следствию из леммы Фаркаша система (4) разрешима тогда и только тогда, когда система неравенств   не имеет решений, т.е. когда оптимальное значение целевой функции в задачах  ,  ,   равно нулю.Итак, мы показали, как найти возможное направление спуска.Пусть теперь   – текущая точка;   – возможное направление спуска. В качестве следующей точки   выбирается  , где длина шага   определяется из решения следующей задачи одномерной оптимизации:минимизировать   по                  (5)при условиях ,                                    (6) .                                   (7)Предположим, что  . Тогда задачу (5) - (7) можно упростить следующим образом. Заметим, что  . Значит, ограничение (7) излишне. Так как  , то   для всех  . Итак, остается только одно ограничение  , и задача оптимизации (5) - (7) приводится к следующей задаче одномерной оптимизации:минимизировать   по                  (8)при условии  ,где                                              (9)  .                         (10) 3. Алгоритм метода Зойтендейка в случае линейных ограничений Пусть требуется найти   при условиях  .Алгоритм метода состоит из предварительного и основного этапов. Последний в свою очередь состоит из однотипных итераций4:Предварительный этап. Найти начальную допустимую точку, для которой  . Положить   и перейти к основному этапу.Основной этап.  -я итерация. Первый шаг. Пусть задан вектор  . Предположим, что   и  . В качестве возможного направления спуска   взять оптимальное решение следующей задачи:минимизировать                               (11)при условиях                                        (12) .                              (13)Если  , то остановиться, и  – оптимальное решение (точка Куна-Таккера). В противном случае перейти ко второму шагу.Второй шаг. Положить   равным оптимальному решению приведенной ниже задачи одномерной оптимизации:минимизировать  при условии                           ,где   задается формулой (9).Для решения этой задачи можно применить любой метод одномерного поиска, например метод Фибоначчи.Вычислить  , определить новое множество активных ограничений для решения   и переопределить   и  . Заменить   на   и перейти к первому шагу следующей итерации.Рассмотрим задачу, в которой допустимая область задается системой ограничений-неравенств нелинейного типа:минимизировать                             (14)при условиях                                                    (15)В следующей теореме формулируются достаточные условия, при которых вектор   является возможным направлением спуска. Теорема 2. Рассмотрим задачу нелинейного программирования (14), (15). Пусть   – допустимая точка, а   – множество индексов активных  в этой точке ограничений, т.е. . Предположим, кроме того, что функции   для   дифференцируемы в точке  , а функции   для   непрерывны в этой точке. Если  ,   при  , то вектор   является возможным направлением спуска.Доказательство. Пусть вектор   удовлетворяет неравенствам  ,   при  . Сначала укажем, что для   выполняются неравенства   и так как   непрерывны в точке  , то   для достаточно малых  . В силу дифференцируемости функции  ,   имеем   , где   при  . Так как  , то   при достаточно малых  . Следовательно, точка   допустима для малых значений  . Аналогично из   следует, что для достаточно малых    .Таким образом, вектор   является возможным направлением спуска.На рис. 2 показана совокупность возможных направлений в точке  . Здесь использованы такие обозначения: 1 – первое ограничение, 2 – третье ограничение, 3 – четвертое ограничение, 4 – второе ограничение, 5 – возможные направления спуска, 6 – линии уровня целевой функции. Вектор  ,  удовлетворяющий равенству  , является касательным к кривой линии (или поверхности)  . Поскольку функции   нелинейны, то движение вдоль такого вектора может привести в недопустимую точку, что вынуждает требовать выполнения строгого неравенства  . Рисунок 2Чтобы найти вектор  ,  удовлетворяющий неравенствам   ,    для   ,  вполне естественно минимизировать максимум из величин   и    для  .  Обозначим  этот  максимум  через    .  Вводя нормирующие условия  , для всех  , приходим к следующей вспомогательной задаче нахождения возможного направления спуска:минимизировать                             (16)при условиях ,                             (17) ,                      (18) .                         (19)Пусть   – оптимальное решение этой задачи ЛП. Если  , то, очевидно,   – возможное направление спуска. Если же  , то, как будет показано ниже, точка   является точкой Куна-Таккера.Докажем это утверждение. Оптимальное значение целевой функции   в задаче (16) - (19) равно нулю тогда и только тогда, когда система неравенств  ,   при   несовместна. Но, согласно следствию из леммы Фаркаша, для того чтобы эта система не имела решения, необходимо и достаточно, чтобы существовали такие числа  , что (20)и либо  , либо   для некоторого  , а это одно из условий оптимальности теоремы Куна-Таккера. 4. Алгоритм Зойтендейка в случае нелинейных ограничений-неравенств Далее рассмотрим алгоритм Зойтендейка при нелинейных ограничениях-неравненствах5:Предварительный этап. Выбрать точку  , для которой  . Положить   и перейти к основному этапу.Основной этап. Первый шаг. Положить   и решить задачу:минимизировать                             (20)при условиях ,                             (21) .          (22)Пусть   – оптимальное решение задачи (20) – (22). Если  , то конец алгоритма и точка   – оптимальное решение такой задачи одномерной оптимизации. Если  , то перейти ко второму шагу.Второй шаг.минимизировать                   (23)при условии  ,                      (24)где                               .     (25)Положить  , заменить   на   и перейти к первому шагу следующей итерации.Пример 4. Рассмотрим задачу:минимизировать   при условиях   Будем решать эту задачу методом Зойтендейка, начиная поиск из точки  . Заметим, что   Первая итерация. Первый шаг. В точке   имеем  , а множество индексов активных ограничений есть  . При этом  . Задача нахождения возможного направления имеет видминимизировать  при условиях  Можно проверить, решая эту задачу симплекс-методом, что оптимальным решением этой задачи является вектор   и  .Второй шаг. Линейный поиск. Любая точка по направлению   из точки   может быть представлена в виде  , а соответствующее ей значение целевой функции равно  . Максимальное значение  , для которого точка   остается допустимой, равно  . Итак, решаем задачу одномерной минимизации:минимизировать  при условии                                       Оптимальное значение  . Итак,  .Вторая итерация. Первый шаг. В точке   имеем  . Активных ограничений в этой точке нет, поэтому задача определения направления спуска имеет вид:минимизировать zпри условиях  Оптимальным решением является вектор  , а  .Второй шаг. Легко проверить, что  , при котором точка   допустима, равна 0.3472. При этом активным становится ограничение  . Оптимальное значение   находим в результате решения задачи:минимизировать   zпри условии                                   Оно равно 0.3472, так что  . Остальные итерации проводятся аналогично. Результаты вычислений на первых четырех итерациях метода приведены в табл. 1. Таблица 1

5. Модификация метода возможных направлений

Заключение

Список использованных источников


4 Методы возможных направлений [Электронный ресурс]. – Режим доступа: http://iasa.org.ua/lections/iso/6/6.5.htm.

5 Нурминский Е.А. Методы оптимизации: Курс лекций [Электронный ресурс]. – Режим доступа: http://elis.dvo.ru/nurmi/edu/optimization.pdf.

6 Нурминский Е.А. Методы оптимизации: Курс лекций [Электронный ресурс]. – Режим доступа: http://elis.dvo.ru/nurmi/edu/optimization.pdf.

7 Методы возможных направлений [Электронный ресурс]. – Режим доступа: http://iasa.org.ua/lections/iso/6/6.5.htm.

8 Нурминский Е.А. Методы оптимизации: Курс лекций [Электронный ресурс]. – Режим доступа: http://elis.dvo.ru/nurmi/edu/optimization.pdf.

Смотрите также файлы