Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 8.3. МАКСИМИЗАЦИЯ ВОГНУТОЙ ФУНКЦИИ СУБОПТИМИЗАЦИЕЙ НА МНОГООБРАЗИЯХМетод, представленный в этом параграфе, предназначен для задачи (8.1) с вогнутой функцией Мотивировка. Для того чтобы понять идею, на которой основан метод, рассмотрим задачу (8.1) с вогнутой непрерывно дифференцируемой функцией Ьсли пользоваться обозначением Таккера 2)
и (условие Куна — Таккера 3)
Напомним (упр. 2.13), что при линейных ограничениях условие регулярности выполняется автоматически. Более того, так как Исключение неравенств. Теперь допустим, что мы рассматриваем тесно связанную с (8.1) задачу
Для простоты предположим, что решение задачи (8.39) единственно. Тогда условия Куна — Таккера, показывающие, что х — оптимальная точка для задачи (8.39), могут быть записаны следующим образом. Существует допустимая точка
и (условие Куна — Таккера 3)
Благодаря вогнутости Анализ условий Куна — Таккера обнаруживает, что точка оптимальна для задачи (8.39). По предположению задача (8.39) имеет единственное решение. Следовательно, х является единственным решением задачи (8.39). Таким образом, приходим к следующему выводу: решая задачу (8.39), мы тем самым решаем задачу (8.1). Основное значение этого результата заключается в следующем. Если можно выделить ограничения, активные в окончательном решении задачи (8.1), то в результате решения более простой задачи (8.39) определится решение задачи (8.1). Метод оптимизации, который сейчас будет рассматриваться, основан именно на этом подходе и представляет собой адаптивный метод для определения ограничений, активных в оптимальной точке. Метод эффективен, если задачи типа (8.39) решаются легко (упр. 8.8). Один такой случай, когда Многообразия. Задача (8.39) имеет форму максимизации Рассмотрим многообразия более подробно. В гл. 6 было отмечено, что многообразие подобно линейному подпространству
имеет размерность Процедура субоптимизации на многообразиях. Процедура субоптимизации на многообразиях действует в основном следующим образом. Предположим, что дана точка
определяя оптимальную точку Если Теперь предположим, что Далее процедура продолжается из точки
где В — некоторое подмножество целых чисел
Единственность. Здесь также требуется свойство единственности. Предположим, что у является оптимальной точкой для задачи
Для этой задачи часть условий Куна — Таккера имеет вид
где
Здесь Теперь можно определить свойство единственности. Точка у обладает свойством единственности, если Лемма 8.2. Пусть у является оптимальной точкой для задачи
и пусть у обладает свойством единственности. Полагая, что соотношение
представляет собой часть условий Куна—Таккера для задачи (8.47), предположим, что для некоторого
где Доказательство. Отметим, что так как На основе свойства единственности не могут существовать величины и и
не удовлетворяются и у не является оптимальной точкой для задачи (8.51). Полагая, что у — оптимальная точка для задачи (8.51), получаем
Лемма доказана. Замечание. Короче говоря, лемма утверждает, что если у оптимальна для задачи (8.47) с Теперь дадим строгую формулировку алгоритма максимизации вогнутой функции с помощью субоптимизации на многообразии. Формулировка алгоритма. Пусть дана точка Шаг 1. Определить
Случай Если 0, то происходит останов; Случай Доказательство сходимости за конечное число шагов. Очевидно, что если алгоритм завершает поиск, то у должна быть оптимальной точкой, так как условия Куна—Таккера удовлетворяются. Покажем, что это завершение поиска должцо произойти после конечного числа итераций. Предположения, которые требуются при этом, заключаются в том, что Сначала покажем, что всякий раз, когда реализуется случай 1 и поиск не завершен, целевая функция на следующем шаге должна строго возрасти. В частности, пусть Но вследствие вогнутости Таким образом, доказано, что в случае 1
Теперь мы можем показать, что случай 1 может иметь место лишь конечное число раз. Если реализуется случай 1, то Чтобы доказать искомый результат, нам необходимо теперь лишь установить, что случай 2 может произойти последовательно, без прерывания случаем 1 не более чем конечное число раз. Тогда, поскольку случай 1 реализуется лишь конечное число раз, после конечного числа шагов поиск будет завершен. Предположим, что имеет место случай 2. так что точка Таким образом, размерность многообразия Мы показали, что всякий раз, когда реализуется случай 2, размерность многообразия, используемого в следующей подзадаче, уменьшается. Если случай 2 реализуется подряд достаточное число раз, то это может привести к многообразию нулевой размерности. Но такое многообразие представляет собой точку, например Геометрическая интерпретация. Геометрически в процедуре оптимизации на многообразии мы двигаемся по направлению к точке, которая оптимизирует целевую функцию на многообразии. Если оптимальная точка многообразия допустима, но не является оптимальной для задачи (8.1), то в качестве новой точки берется оптимальная точка многообразия и рассматривается многообразие с размерностью, на единицу большей, так как опускается требование где Упражнения(см. скан) (кликните для просмотра скана) (см. скан) Примечания и ссылки§ 8.1. Этот алгоритм был предложен Франком и Вольфом, хотя доказательство с помощью теоремы сходимости является новым. § 8.2. Выпуклый симплексный метод был предложен Зангвиллом (1967g), а возможность его декомпозиции, так же как и его применимости ко многим матрицам специального вида, была обнаружена Рутенбергом. Выпуклый симплексный метод связан с алгоритмом, разработанным Вольфом (см. Вольф (1962); Лермитт и Бессиер; Фор и Хьюард. См. также Розен (1960) и Бил (1955)). § 8.3. Изложение основано на работе Зангвилла (1967h). Упр. 8 дает краткое введение к вопросу обобщенной обратной матрицы (см. Пенроуз). Обобщенная обратная матрица представляет собой распространение понятия обратной матрицы на матрицы, которые не имеют обратных в обычном смысле. Дополнительные замечанияВ частных случаях задачи максимизации функции при линейных ограничениях упрощаются. Такое упрощение имеет место для сепарабельных целевых функций (см. Чарис и Лемке; или Миллеп). К упрощениям приводят также сетевые формулировки (см. Бил (1959), Хью и Зангвилл (1966b)),
|
1 |
Оглавление
|