Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 705790.03.01
К покупке доступен более свежий выпуск Перейти
Поиск глобального (абсолютного) экстремума требуется в большинстве приложений, связанных с экономикой, финансами, искусственным интеллектом и робототехникой. В монографии рассмотрены как методы, использующие необходимые и достаточные условия экстремума, так и прямые методы оптимизации. Материал снабжен многочисленными примерами и рисунками. Для математиков, специалистов в сфере бизнеса и техники, студентов, изучающих модели и методы динамической оптимизации, а также всех интересующихся проблемой поиска глобального (абсолютного) экстремума в задачах оптимального управления и смежных разделах математики.
Орёл, Е. Н. Динамическая оптимизация: поиск абсолютного экстремума : монография / Е.Н. Орёл, О.Е. Орёл. — Москва : ИНФРА-М, 2022. — 163 с. — (Научная мысль). — DOI 10.12737/monography_5cecfdb9a678e7.61184426. - ISBN 978-5-16-016233-1. - Текст : электронный. - URL: https://znanium.com/catalog/product/1771040 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
ДИНАМИЧЕСКАЯ ОПТИМИЗАЦИЯ

ПОИСК АБСОЛЮТНОГО ЭКСТРЕМУМА

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

МОНОГРАФИЯ

Москва

ИНФРА-М

2022

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

Орёл Е.Н.

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

Е.Н. Орёл, О.Е. Орёл. — Москва : ИНФРА-М, 2022. — 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

Глава 1

Каноническая модель

Я верю, что любая научная мысль,
достойная уровня включения её в
некоторую теорию, попадает под
влияние мощи аксиоматического
метода....

– Д. Гильберт

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

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

Множество объектов, на котором ищется экстремум, будет, как правило, обозначать
ся символом Γ. Элементы γ ∈ Γ, в зависимости от контекста будут называться кривыми,
траекториями, процессами управления и т.д. Все они неявным образом связаны с временем t и имеют начальное, α(γ), и конечное, β(γ), состояния. Вопреки традиции, мы
не будем детально изучать вопросы, связанные с локальным экстремумом, хотя они
играют весьма важную роль в задачах механики, физики, техники и т.д. Наш выбор
связан с тем, что существуют прикладные области, такие, как экономика, финансы, робототехника, в которых локальный экстремум не может удовлетворить исследователя
или заказчика. Поэтому под экстремумом мы, как правило, будем понимать именно
глобальный минимум или максимум, а термин оптимальный будем трактовать в естественном смысле, как характеристику объекта, доставляющего глобальный экстремум.
Этим продиктован и способ изложения материала – практически с самого начала мы

11

O

-1
0
1
2
3
4
5
6
7
8
9
10

-5

-4

-3

-2

-1

0

1

2

3

4

5

Рис. 1.1. Задача о кратчайших кривых на плоскости

рассматриваем не одну задачу минимизации, а семейство таких задач, возникающих, когда “...один конец остаётся фиксированным, а второй занимает различные положения”
[46]. Используя это семейство, мы можем быть уверены, что не существует обходного
пути, идущего куда-то в сторону, набирающего там дополнительные баллы, а затем приводящего в терминальную точку. Переходя к примерам, продемонстрируем сказанное
сначала на задаче о кратчайшей кривой на плоскости.

1.1
Примеры

1.1.1
Кратчайшие кривые на плоскости Евклида

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

Математически задача решается в рамках дисциплины вариационного исчисления.

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

В простом варианте рассматриваются кривые как графики функций x(t) на проме
жутке времени [t0, t1], t0 < t1. Строго говоря, x(t) есть значение функции в конкретной
точке t. Для обозначения самой функции в целом будем часто использовать обозначение x(.). Иногда точка в скобках делает формулу слишком громоздкой. В таких случаях
функцию или кривую будем обозначать одной греческой буквой, например, γ.

Сначала выразим длину кривой. Возьмем её небольшой участок. Пусть на нём t

меняется от τi−1 до τi, а x – от ξi−1 до ξi. На малом промежутке можно приближенно считать, что длина кривой равна длине секущей – отрезка, соединяющего точки

12

плоскости (τi−1, ξi−1) и (τi, ξi). По теореме Пифагора, длина этого отрезка равна

Δli =

(τi − τi−1)2 + (ξi − ξi−1)2 =

(Δτi)2 + (Δξi)2.

Если разбить всю кривую на мелкие участки точками (τi, ξi), i = 0, . . . , N, τ0 = t0,
τN =

t1, и сложить длины всех секущих, то получится интегральная сумма

SΔ =

N
i=1

Δli.

Обозначим ε(SΔ) = maxi Δli. Теперь будем переходить ко всё более мелкому разби
ению кривой, неограниченно увеличивая N так, чтобы ε(SΔ) стремилось к нулю. Если
этот предел существует и не зависит от последовательности разбиений, то он называется длиной кривой. Таким образом, длина кривой γ выражается в виде криволинейного
интеграла

J(γ) = lim SΔ =

γ

dl =

γ

√

dt2 + dx2.

Вынося dt из-под корня и полагая x(.) = γ, получим определённый интеграл

J(x(.)) =

t1
t0

1 + ˙x2(t)dt.

Здесь через ˙x(t) обозначена скорость (производная пути по времени) x′(t) = dx(t)

dt . Ве
личина J представляет собой функцию от функции и называется функционалом. Из
свойств интеграла вытекает, что функционал аддитивен. Это значит, что если кривая
разбита на несколько участков, то значение функционала на всей кривой равно сумме значений функционала на отдельных участках. Формально это легко записывается,
если снова обозначить кривую одной буквой, γ = x(.), а разбиение кривой, предположим, на 3 участка δ, ϵ, η понимать как конкатенацию γ = δ ∧ ϵ ∧ η или, проще, как
произведение γ = δϵη. Тогда

J(γ) = J(δϵη) = J(δ) + J(ϵ) + J(η).

Другие свойства разбиения кривой будут рассмотрены в основном тексте.
В общем случае функционал в вариационном исчислении записывается в виде

J(γ) = J(x(.)) =

t1
t0

L(t, x(t), ˙x(t))dt,

где γ = x(.) – вектор-функция, L – функция Лагранжа. Для нахождения экстремума
функционала составляется уравнение Эйлера-Лагранжа

13

К покупке доступен более свежий выпуск Перейти