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

НАУЧНАЯ МЫСЛЬ I
СЕРИЯ ОСНОВАНА В 2008 ГОДУ





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


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

МОНОГРАФИЯ

2-е издание, переработанное и дополненное






        znanium.com

электронно-библиотечная система

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

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
















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

         ISBN 978-5-16-018768-6 (print)
         ISBN 978-5-16-111670-8 (online)

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

УДК 519.6(075.4)
ББК 22.19
















ISBN 978-5-16-018768-6 (print)
ISBN 978-5-16-111670-8 (online)

                 © Орёл Е.Н., Орёл О.Е., 2019
© Орёл Е.Н., Орёл О.Е., 2023, с изменениями

                Оглавление





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

1  Каноническая модель                                                        11
    1.1 Примеры.............................................................. 12
        1.1.1 Кратчайшие кривые на плоскости Евклида......................... 12
        1.1.2 Минимизация издержек при выполнении заказа..................... 16
        1.1.3 Задача о движении автомобиля................................... 17
        1.1.4 Оптимальное вложение инвестиций в предприятия.................. 18
    1.2 Описание общей модели ............................................... 21
        1.2.1 Система аксиом................................................. 23
        1.2.2 Оптимальные траектории ........................................ 24
        1.2.3 Функционал времени............................................. 25
    1.3 Множество траекторий с фиксированной начальной точкой ............... 26
        1.3.1 Центральные поля траекторий ................................... 26
        1.3.2 Функционалы, связанные с полем траекторий ..................... 27
        1.3.3 Общий критерий оптимальности поля.............................. 28
        1.3.4 Случай непрерывного времени ................................... 28
        1.3.5 Случай интегрального функционала............................... 30

2  Пути на графе                                                              33
    2.1 Элементы искусственного интеллекта в лабиринтных задачах............. 34
        2.1.1 Алгоритм “движение в новые вершины”............................ 35
        2.1.2 Алгоритм Шеннона “Мышь в лабиринте”............................ 38
    2.2 Классические методы оптимизации на графах ........................... 41
        2.2.1 Расстояния между вершинами..................................... 41
        2.2.2 Прокладка оптимального маршрута................................ 42
        2.2.3 Построение матрицы расстояний.................................. 42
        2.2.4 Построение дерева кратчайших путей............................. 47
    2.3 Целенаправленный поиск............................................... 50
        2.3.1 Эвристическая функция.......................................... 50
        2.3.2 Алгоритм Нильсона.............................................. 51
        2.3.3 Свойства алгоритма............................................. 52
    2.4 Оптимизация стратегии ............................................... 53
        2.4.1 Примеры самообучения систем.................................... 53
        2.4.2 Алгоритмы оптимизации стратегии................................ 58

3

Вариационное исчисление                                                    65
    3.1 Обычная постановка задачи............................................ 66
    3.2 Следствия критерия оптимальности поля................................ 66
        3.2.1 Связь функции Лагранжа с функцией поля......................... 66
        3.2.2 Неравенство Вейерштрасса....................................... 67
        3.2.3 Векторное уравнение Эйлера — Лагранжа.......................... 67
        3.2.4 Система уравнений Эйлера — Лагранжа............................ 68
        3.2.5 Импульс и функция Гамильтона .................................. 68
        3.2.6 Законы сохранения.............................................. 71
    3.3  Поле оптимальных ломаных Эйлера..................................... 71
        3.3.1 Постановка задачи ............................................. 72
        3.3.2 Переход к классу ломаных линий................................. 73
        3.3.3 Алгоритм построения поля....................................... 74
    3.4  Решение примеров.................................................... 75
        3.4.1 Кратчайшие кривые на евклидовой плоскости...................... 75
        3.4.2 Кратчайшие кривые на плоскости Лобачевского.................... 81
        3.4.3 Кривые наискорсйшсго спуска (задача о брахистохроне) .......... 83
        3.4.4 Минимальная поверхность вращения............................... 88
        3.4.5 Максимизация прибыли в условиях самофинансирования............. 93
        3.4.6 Минимизация издержек в рамках вариационного исчисления ........ 95
    Приложение к главе 3. Вариации и их применение........................... 98
        1. Основная лемма вариационного исчисления .......................... 99
        2. Производная интеграла по параметру................................100
        3. Производная функции вдоль вектора.................................101
        4. Вариация .........................................................102
        5. Уравнение Дюбуа — Реймона.........................................104
        6. Следствия.........................................................106

4        Задачи оптимального управления с фиксированным временем             107
    4.1  Центральные поля экстремалей Понтрягина.............................107
        4.1.1 Формулировка задачи............................................107
        4.1.2 Произведение (склейка) процессов и траекторий..................108
        4.1.3 Экстремали Понтрягина..........................................110
        4.1.4 Оптимальность гладкого поля экстремалей........................111
    4.2  Оптимизация с помощью движения по ячейкам...........................115
        4.2.1 Недостатки решётчатой структуры................................116
        4.2.2 Ломаные в обобщённом   смысле..................................117
        4.2.3 Разбиение на ячейки............................................119
        4.2.4 Алгоритм оптимизации...........................................119
        4.2.5 Обоснование алгоритма..........................................121
    4.3  Решение экономического примера......................................122
        4.3.1 Описание.......................................................122
        4.3.2 Построение экстремалей.........................................123
        4.3.3 Проверка аналитического критерия ..............................125

4

Динамическое программирование                                            129
    5.1 Задачи с фиксированным временем.....................................130
        5.1.1 Многошаговые процессы принятия решений       .................130
        5.1.2 Свойства многошаговых процессов принятия  решений.............131
        5.1.3 Функция Беллмапа..............................................132
        5.1.4 Рекуррентное соотношение Беллмана ............................133
        5.1.5 Стратегия ....................................................134
        5.1.6 Построение оптимального процесса принятия решений.............135
        5.1.7 Решение задачи об оптимальном распределении инвестиций........135
    5.2 Общий случай многошаговых процессов.................................140
        5.2.1 Приближение в пространстве функций............................140
        5.2.2 Функциональное уравнение Беллмапа.............................141
        5.2.3 Множества траекторий и операторы..............................142
        5.2.4 Последовательные приближения .................................144

6  Автономные задачи оптимального управления                                147
    6.1 Центральные поля в автономных задачах...............................147
        6.1.1 Постановка задачи ............................................147
        6.1.2 Свойства траекторий...........................................148
        6.1.3 Принцип максимума Поптрягипа..................................149
        6.1.4 Центральное поле траекторий...................................150
        6.1.5 Импульсы поля и функция Гамильтона — Понтрягина...............151
    6.2 Оптимизация маршрутов по ячейкам....................................152
        6.2.1 Дуги и ячейки.................................................153
        6.2.2 Обобщённый граф...............................................154
        6.2.3 Модифицированный алгоритм Дейкстры ...........................155
        6.2.4 Игра с Природой ..............................................157
    6.3 Примеры.............................................................160
        6.3.1 Движение автомобиля к месту стоянки ..........................160
        6.3.2 Задача Бушоу..................................................162
        6.3.3 Задача об остановке маятника..................................169

7  Оптимизация в условиях конфликта и неопределённости                      175
    7.1 Игра “простое преследование”........................................176
        7.1.1 Точное решение игры...........................................176
        7.1.2 Численное решение.............................................178
    7.2 Игра “шофёр-убийца”.................................................180
    7.3 Игра двух автомобилей...............................................181
    7.4 Оптимизация при дефиците информации.................................184
        7.4.1 Задача о плоском перевёрнутом маятнике........................184

Заключение                                                                 187

Список использованной литературы                                           189

о

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

6

                Предисловие





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

7

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

8

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

9