Ф.П. Васильев - Методы оптимизации

УДК 519.6 (075.8) ББК 22.19 В 19 ОГЛАВЛЕНИЕ В 19 Предисловие Часть 9 9 9 14 1б 17 20 24 28 32 38 Глава Глава 43 43 53 58 6? 83 86 94 94 100 !05 !32 Научное издание Васильев Федор Павлович МБТОДЫ ОПТИМИЗАЦИИ Глвва Глава 1ЯВ1ч! 5 — 88688 — 056 — 9 © Факториал Пресс, 2002. 9 785886 880564 Васильев Ф. П.

Методы оптимизации. — Мс Издательство «Факториал Пресс», 2002. — 824 с. 15ВМ 5 — 88688-056 — 9. Книга содержит численные методы решения задач оптимизации. Приводятся теоретическое обоснование и краткие характеристики этих методов. Рассматриваются задачи минимизации функций в конечномерных и.бесконечномерных пространствах, а также задачи оптимального уцрааления »процессами, описываемыми системами обыкновенных диффе енциальных уравнений и ураэнений в частных производных. Д' ля студентов вузов по специальности «Прикладная математика», и специалистов, связанных с решением задач оптимизации, Формат ?ох!00/16. Уел. печ.

л. 67. Бумага офсетная № 1. Гарнитура литературная. Подписано к печати 25.12.2001. Тираж 500 экз. Заказ № 5! 82. Издательство «Факториал Пресс», 117449, Москва, а/в 331; ЛР ИД № 003!6 от 22.10.1999. е/гпа11: 1ас1ог!а1чмша1!.сошрпе1хп; 511р://ччввг.сошрпе1.гп/1ас1ог1а!.

Отпечатано с готовых диапозитивов издательства «Факториал Пресс» в ППП типографии «Наука» Аквдемиздатцентра «Наука» РАН, 121099, Москва Г-99, Шубинский пер., 6. Оригинал-макет подготовлен с использованием издательской системы АР-ТВХ. 1. КОНВЧНОМВРНЫВ ЗАДАЧИ МИНИМИЗАЦИИ. ПРИНЦИП МАКСИМУМА.

ДИНАМИЧВСКОВ ПРОГРАММИРОВАНИЕ,...,... 1. Методы минимизации фуннций одной переменной 1. Постановка задачи 2. Классический метод 3. Метод деления отреака пополам 4.Метод золотого сечения. Симметричные методы 5. Об оптимальных методах 6. Метод ломаных 7. Методы покрытий . 8. Выпуклые функции одной переменной 9. Метод касательных 2. Классическая теория экстремума функций многих переменных 1. Постановка задачи, Теорема Вейерштрасса 2.

Классический метод решения задач на безусловный экстремум 3. Задачи на условный экстремум. Необходимые условия первого порядка 4. Необходимые условия экстремума второго порядка.............. 5. Достаточные условия зкстремума 6. Вспомогательные предложения 3. Элементы линейного программирования 1. Постановка задачи 2. Геометрическая интерпретация. Угловые точки 3. Симплекс-метод. Антициклин 4. Поиск начальной угловой точки 5.

Условие разрешимости задач линейного программирования. Теоремы двой- ственности 4. Элементы выпуклого анализа 1. Выпуклые множества . 2, Выпуклые функции 3. Сильно выпуклые функции 4. Проекция точки на множество 5. Отделимость выпуклых множеств б. Субгрвдиент. Субдифференциал 7. Равномерно выпуклые функции 8. Обоснование правила множителей Лагранжа 9. Теорема Куна — Таккера. Двойственная задача 5. Методы минимизации функций многих переменных 1. Градиентный метод 2. Метод проекции градиента З.Метод проекции субградиента 4. Метод условного градиента 5. Метод возможных направлений 4 4 $ 4 9 5 9 $ 9 Глава $ $ 9 9 9 137 148 148 159 176 182 188 197 206 211 2!7 234 234 249 258 263 269 ОГЛАВЛЕНИЕ ОГЛАВЛЕНИЕ 339 348 356 368 371 376 376 387 406 788 8!6 820 Список литературы Предметный указатель Список обозначении 430 459 462 462 474 479 486 493 493 494 500 519 539 554 565 57! 582 6 6.

Проксимзльный метод 6 7. Метод линеаризации $8. Квадратичное программирование 6 9. Метод сопряхгенных направлений 6 10. Метод Ньютона $!!. Непрерывные ыетоды с переменной метрикой 6 12.Метод покоординатного спуска . $13. Метод покрытия в многомерных задачах $ !4.Метод модифицированных функций Лагранжа $15.Метод штрафных функций 6 16. Доказательство необходимых условий акстремума первою и второго порядков с помощью штрафных функций $ !7,Метод барьерных функций $18,Метод нагруженных функций $19.

О методе случайного поиска $20. Общие замечания Г л з в а 6, Принцип максимума Понтрягина 5 1. Постановка задачи оптимального управления $2. Формулировка принципа максимума. Примеры $3. Доказательство принципа максимума 6 4. Принцип максимума для задач оптимального управления с фазовыми ограничениями $5. Связь между принципом максимума и классическим взриационным исчис- лением Г л а в а 7. Динамическое программирование $1. Схема Беллмена Проблема синтеза длк дискретных систем 6 2. Схема Моисеева......,...,...,...,...,... 6 3.

Проблема синтеза для систем с непрерывным временем $4. Достаточные условия оптимальности Часть В. МИНИМИЗАЦИЯ В ФУНКЦИОНАЛЬНЫХ ПРОСТРАНСТВАХ РЕГУЛЯРИЗАЦИЯ. АППРОКСИМАЦИЯ Г л в в а 8. Методы минимизации в функциональных пространствах, 5 1.

Предварительные сведения. Обозначения ....,, ...., ..., ...,, $2. Теорема Вейерштрасса в функциональных пространствах 6 3. Дифференцирование. Условия оптимвльности 6 4. Методы минимизации $5, Градиент в задаче оптимального управления со свободным правым концом $6, Градиент в задаче оптимального управления с дискретным временем 6 7, Оптимальное управление процессом нагрева стержня 6 8.

Оптимальное управление колебательными процессами ......, ..... $9. Оптимальное управление процессами, описываемыми уравнением Гурса— Дарбу 6 10, Взаимодвойственные задачи управления и наблюдения 6 11. Метод моментов ..., ..., ...., ..., ...,,, Глава 9. Методы решения неустойчивых задач оптимизации 6 1.

Постановка задачи. Устойчивые и неустойчивые зюгачи минимизации... 6 2. Методы регуляризации для решения неустойчивых задач первого типа $3, Стабилизатор. Леммы о регуляризации 6 4.Метод стабилизации 6 5. Метод невязки 6 6.Метод квззирешений ..............., ..., ......., .... 278 284 288 292 300 308 3!О 315 3!7 323 591 595 605 617 617 625 632 639 655 658 6 7. Методы регуляризации с расширением множества ......,...,... 662 6 8.

Регуляризованный метод проекции градиента ............,.... 669 6 9. Регуляризованный метод условного градиента .........,... „... 678 6 10. Регуляриаованный проксимяльный метод.................... 685 6!!. Регуляризованный метод Ньютона ........................ 690 $12. Регуляризованный непрерывный метод проекции градиента .....,... 697 $ !З.Метод динамической регуляризации ......., ........., ..... 703 Глава ! О. Аппроксимация экстремальных вадач ...........,,..., 710 $1. Разностная аппроксимация квадратичной задачи оптимального управления ..., ................, ............., ..., ... 710 $2, Общие условия аппроксимации ..................., ......

719 6 3, Разностная аппроксимация для квадратичной задачи с фазовыми ограничениями ........., ...................... г...., ... 726 $4. Регуляризация аппроксимаций экстремальных задач ............. 733 $5. Разностнзя аппроксимация квадратичной задачи с переменной областью управления, ........., .........,, „ ........, ..., .. 742 6 6. Аппроксимация задачи быстродействия ...,, ..., ...., ..., ...

750 $7. Разностная аппроксимация задачи об оптимальном нагреве стержня ... 757 6 8. Об аппроксимации мвксиминных задач ..., ...,, ............ 775 ПРЕДИСЛОВИЕ ПРЕДИСЛОВИЕ Первые задачи геометрического содержания, связанные с отысканием наименьших и наибольших величин, появились еще в древние времена. Развитие промышленности в ХУП вЂ” ХУП! веках привело к необходимости исследования более сложных задач на экстремум и к появлению вариационного исчисления. Однако лишь в ХХ веке при огромном размахе производства и,осознании ограниченности ресурсов Земли во весь рост встала задача оптимального использования энергии, материалов, рабочего времени, большую актуальность приобрели вопросы наилучшего в том или ином смысле управления различными процессами физики, техники, экономики н др.

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

Потребности развития самой вычислительной математики также привели к необходимости исследования таких задач на максимум и минимум, как, например, задачи наилучшего приближения функций, оптимального выбора параметров итерационного процесса или узлов интерполирования, минимизации невязки уравнений и т. д. На математическом языке такие задачи могут быть сформулированы как задачи отыскания экстремума (максимума или минимума) некоторой функции или функционала 7(и), выражающего собой качество (цену) управления и из заданного множества 77 некоторого пространства. Требование принадлежности управления и некоторому множеству У выражает собой ограничения, обычно вытекающие из законов сохранения, ограниченности наличных ресурсов, возможностей технической реализации управления, нежелательности каких-либо запрещенных (аварийных) состояний и т. п.

Задачи отыскания экстремума функции 7(и) на множестве У принято называть экстремальными задачами. Заметим, что задача максимизации функционала 7(и) на множестве У эквивалентна задаче минимизации функционала —,7(и) на том же множестве У, поэтому можно ограничиться рассмотрением задач минимизации. В настоящее время теория экстремальных задач обогатилась фундаментальными результатами, появились ее новые разделы, такие как линейное, выпуклое, стохастнческое программирование, оптимальное управление и др.

Потребности практики способствовали бурному развити>о методов приближенного решения экстремальных задач. Появление быстродействующих электронных вьп>ислительных машин (ЭВМ) сделало возможным эффективное решение многих важных прикладных экстремальных. задач, которые ранее из-за своей сложности представлялись недоступными. В настоящей книге излагаются элементы теории экстремальных задач, а также основы наиболее часто используемых на практике методов приближенного решения экстремальных задач, теоретическое обоснование и краткая характеристика этих методов.

Книга написана как учебное пособие для студентов факультетов и отделений прикладной математики университетов, технических вузов. В основу книги положен курс лекций по численным методам решения экстремальных задач, который автор в течение М яда лет читает на факультете вычислительной математики и, кибернетики осковского университета. Заманчиво было бы изложить теорию и методы минимизации сразу в общем виде на языке функционального анализа, охватив при этом как частный случай многие методы минимизации функций конечного числа переменных. Однако такой способ изложения, несмотря на свою привлекательность и удобства для читателя-математика, видимо, все же труден дня первого знакомства с предметом, не говоря уже о том, что он не может отразить всю специфику конечномерных задач.