Динамическая оптимизация: поиск абсолютного экстремума

ДИНАМИЧЕСКАЯ ОПТИМИЗАЦИЯ
ПОИСК АБСОЛЮТНОГО ЭКСТРЕМУМА

Е.Н. Орёл, О.Е. Орёл

МОНОГРАФИЯ

Москва
ИНФРА-М
2020

УДК 519.6(075.4)
ББК 22.19
 
О65

Орёл Е.Н.
О65  
Динамическая оптимизация: поиск абсолютного экстремума : монография / 
Е.Н. Орёл, О.Е. Орёл. — Москва : ИНФРА-М, 2020. — 163 с. — (Научная мысль). — 
DOI 10.12737/monography_5cecfdb9a678e7.61184426.

ISBN 978-5-16-016233-1 (print)
ISBN 978-5-16-107738-2 (online)

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

УДК 519.6(075.4)
ББК 22.19

Р е ц е н з е н т ы:
Шаповал А.Б., доктор физико-математических наук, доцент, профессор Департамента 
больших данных и информационного поиска, заведующий Научно-учебной лабораторией моделирования и управления сложными системами Национального исследовательского университета «Высшая школа экономики»;
Тищенко А.В., доктор физико-математических наук, профессор, профессор Депар тамента анализа данных, принятия решений и финансовых технологий Финансового 
университета при Правительстве Российской Федерации

ISBN 978-5-16-016233-1 (print)
ISBN 978-5-16-107738-2 (online)
© Орёл Е.Н., Орёл О.Е., 2019

Предисловие ................................................................................................................ 7

Глава 1. Каноническая модель .....................................................................................11

1.1. Примеры ...............................................................................................................................................................................12
1.1.1. Кратчайшие кривые на плоскости Евклида..............................................................................................12
1.1.2. Минимизация издержек при выполнении заказа ...................................................................................16
1.1.3. Задача о движении автомобиля .....................................................................................................................17
1.1.4. Оптимальное распределение инвестиций между предприятиями ...................................................19
1.2. Описание общей модели ................................................................................................................................................21
1.2.1. Система аксиом ...................................................................................................................................................23
1.2.2. Оптимальные траектории ................................................................................................................................24
1.2.3. Функционал времени ........................................................................................................................................25
1.3. Множество траекторий с фиксированной начальной точкой ..........................................................................25
1.3.1. Функционалы, связанные с полем траекторий .......................................................................................27
1.3.2. Общий критерий оптимальности поля .......................................................................................................27
1.3.3. Случай непрерывного времени ......................................................................................................................28
1.3.4. Случай интегрального функционала ...........................................................................................................30
1.4. Кратчайший путь на графе ............................................................................................................................................31
1.4.1. Постановка задачи ..............................................................................................................................................31
1.4.2. Принцип Гюйгенса и алгоритм Дейкстры .................................................................................................31
1.4.3. Формальное описание алгоритма .................................................................................................................32
1.4.4. Пример ....................................................................................................................................................................34

Глава 2. Вариационное исчисление ...............................................................................37

2.1. Обычная постановка задачи .........................................................................................................................................38
2.2. Следствия критерия оптимальности поля ..............................................................................................................38
2.2.1. Связь функции Лагранжа с функцией поля .............................................................................................38
2.2.2. Неравенство Вейерштрасса .............................................................................................................................39
2.2.3. Уравнение Эйлера-Лагранжа .........................................................................................................................39
2.2.4. Система уравнений Эйлера-Лагранжа ........................................................................................................40
2.2.5. Импульс и функция Гамильтона ..................................................................................................................40
2.2.6. Законы сохранения ............................................................................................................................................43
2.3. Поле оптимальных ломаных Эйлера .........................................................................................................................43
2.3.1. Постановка задачи ..............................................................................................................................................44
2.3.2. Переход к классу ломаных линий ................................................................................................................45
2.3.3. Алгоритм построения поля .............................................................................................................................46
2.4. Решение примеров ............................................................................................................................................................47
2.4.1. Кратчайшие кривые на евклидовой плоскости .......................................................................................47
2.4.2. Кратчайшие кривые на плоскости Лобачевского ...................................................................................53

Оглавление

3

2.4.3. Кривые наискорейшего спуска (задача о брахистохроне) ..................................................................55
2.4.4. Минимальная поверхность вращения .........................................................................................................60
2.4.5. Максимизация прибыли в условиях самофинансирования ...............................................................65
2.4.6. Минимизация издержек в рамках вариационного исчисления ........................................................67 

Приложение к главе 2. Вариации и их применение ........................................................70

1. Основная лемма вариационного исчисления ...............................................................................................................71
2. Производная интеграла по параметру .............................................................................................................................72
3. Производная функции вдоль вектора .............................................................................................................................73
4. Вариация ....................................................................................................................................................................................74
5. Уравнение Дюбуа-Реймона .................................................................................................................................................76
6. Следствия ...................................................................................................................................................................................78

Глава 3. Задачи оптимального управления с фиксированным временем ..........................79

3.1. Центральные поля экстремалей Понтрягина .........................................................................................................79

3.1.1. Формулировка задачи .......................................................................................................................................79
3.1.2. Произведение (склейка) процессов и траекторий ..................................................................................80
3.1.3. Экстремали Понтрягина ..................................................................................................................................82
3.1.4. Оптимальность гладкого поля экстремалей .............................................................................................83

3.2. Оптимизация с помощью движения по ячейкам ..................................................................................................87

3.2.1. Недостатки решётчатой структуры ..............................................................................................................88
3.2.2. Ломаные в обобщённом смысле ....................................................................................................................89
3.2.3. Разбиение на ячейки ..........................................................................................................................................91
3.2.4. Алгоритм оптимизации ....................................................................................................................................91
3.2.5. Обоснование алгоритма ....................................................................................................................................93

3.3. Решение экономического примера .............................................................................................................................94

3.3.1. Описание ................................................................................................................................................................94
3.3.2. Построение экстремалей ..................................................................................................................................95
3.3.3. Проверка аналитического критерия ............................................................................................................97

Глава 4. Динамическое программирование .................................................................. 101

4.1. Задачи с фиксированным временем ....................................................................................................................... 102

4.1.1. Многошаговые процессы принятия решений ....................................................................................... 102
4.1.2. Свойства многошаговых процессов принятия решений ................................................................... 103
4.1.3. Функция Беллмана ......................................................................................................................................... 104
4.1.4. Рекуррентное соотношение Беллмана ..................................................................................................... 105
4.1.5. Стратегия ............................................................................................................................................................ 106
4.1.6. Построение оптимального процесса принятия решений .................................................................. 107
4.1.7. Решение задачи об оптимальном распределении инвестиций ....................................................... 107

4.2. Общий случай многошаговых процессов ............................................................................................................. 112

4.2.1. Приближение в пространстве функций .................................................................................................. 112
4.2.2. Функциональное уравнение Беллмана.................................................................................................... 113
4.2.3. Множества траекторий и операторы ........................................................................................................ 114
4.2.4. Последовательные приближения в динамическом программировании ...................................... 116

Глава 5. Автономные задачи оптимального управления ............................................... 119

5.1. Центральные поля в автономных задачах ............................................................................................................ 119

5.1.1. Постановка задачи ........................................................................................................................................... 119
5.1.2. Свойства траекторий ...................................................................................................................................... 120
5.1.3. Принцип максимума Понтрягина.............................................................................................................. 121
5.1.4. Центральное поле траекторий ..................................................................................................................... 122
5.1.5. Импульсы поля и функция Гамильтона-Понтрягина ........................................................................ 123

5.2. Оптимизация маршрутов по ячейкам .................................................................................................................... 124

5.2.1. Дуги и ячейки .................................................................................................................................................... 125
5.2.2. Обобщённый граф ........................................................................................................................................... 126

4

5.2.3. Модифицированный алгоритм Дейкстры .............................................................................................. 127
5.2.4. Игра с Природой .............................................................................................................................................. 129
5.3. Примеры ............................................................................................................................................................................ 132
5.3.1. Движение автомобиля к месту стоянки .................................................................................................. 132
5.3.2. Задача Бушоу .................................................................................................................................................... 134
5.3.3. Задача об остановке маятника .................................................................................................................... 141

Глава 6. Динамическая оптимизация в условиях конфликта и неопределённости .......... 147

6.1. Игра «простое преследование» ................................................................................................................................. 148
6.1.1. Точное решение игры ..................................................................................................................................... 148
6.1.2. Численное решение ......................................................................................................................................... 150
6.2. Игра «шофёр-убийца» .................................................................................................................................................. 152
6.3. Игра двух автомобилей................................................................................................................................................ 153
6.4. Оптимизация при дефиците информации ........................................................................................................... 156
6.4.1. Задача о плоском перевёрнутом маятнике ............................................................................................. 156

Заключение .............................................................................................................. 159

Библиографический список ....................................................................................... 161

Предисловие

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

Когда мы ищем на числовой оси глобальный экстремум гладкой функции одной

переменной, мы прежде всего используем необходимое условие экстремума – в точке
экстремума производная должна обращаться в нуль (принцип Ферма). Основываясь на
этом, мы находим все граничные и стационарные точки (точки, в которых производная
равна нулю) и подсчитываем значения функции в этих точках. Наибольшее значение
дает максимум, а наименьшее – минимум. Конечно, нужно проверить ещё, существует
ли абсолютный экстремум, и на этом исследование можно считать завершённым.

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

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

В конце 17 и начале 18 века были уже решены многие классические задачи вариаци
онного исчисления (брахистохрона, задача Дидоны, кратчайшие кривые на плоскости
Евклида, минимальная поверхность вращения). Для большинства этих задач были действительно найдены кривые, обеспечивающие глобальный экстремум. Но этот факт
принимался на веру, считался самоочевидным и не был в то время строго доказан. Прошло чуть ли не 200 лет прежде чем К. Вейерштрасс разработал подход, связанный с
теорией полей экстремалей, позволивший доказать, что найденные ранее кривые действительно дают глобальный экстремум. Согласно этому подходу, надо исследовать не
одну экстремаль, а семейство экстремалей, однократно покрывающее область дости
7

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

По всей видимости, методика Вейерштрасса, которая не имеет аналогов в теории

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

Разумеется, построение центрального поля в каждом конкретном случае является

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

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

Математик должен уметь не только доказывать теоремы существования и единствен
ности, но и решать задачи. В “Рассуждении о методе” Р. Декарт писал, что сложную
задачу следует разбить на несколько более простых подзадач, но исходная задача не
может считаться решённой, пока не решена последняя из подзадач. В нашем случае
можно найти одну экстремаль и сколько угодно её исследовать с разных точек зрения, но, пока не изучены остальные экстремали с различными правыми (или левыми)
концами, о решении задачи на абсолютный экстремум не может быть и речи.

Выбранный в книге способ изложения, опирающийся на свойство аддитивности

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

8

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

Всюду в тексте доказательства утверждений помещены в треугольные скобки ◁ . . . ▷.

9