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

НАУЧНАЯ МЫСЛЬ 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



               Глава 1

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





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


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



11



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



            1.1 Примеры



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


Известно, что задача о кратчайшем расстоянии была решена много веков назад, исходя из здравого смысла. Не только древние люди знали, что отрезок короче любой кривой с теми же концами, но, наверное, весь живой мир опытным путём определил, что быстрее всего до цели можно добраться, двигаясь по прямой.
   Математически задача решается в рамках дисциплины вариационного исчисления. Если зафиксировать начальную точку, то всевозможные отрезки, начинающиеся в ней, будут иметь минимальную длину (рис. 1.1) по сравнению с другими кривыми с теми же концами. Как шутят математики, это не только очевидно, но и можно доказать. В этом разделе ограничимся схемой доказательства, а полные выкладки будут даны позднее.
   В простом варианте рассматриваются кривые как графики функций x(t) на промежутке времени [t₀,t1], t₀ < t-1. Строго говоря, x(t) есть значение функции в конкретной точке t. Для обозначения самой функции в целом будем часто использовать обозначение х(.). Иногда точка в скобках делает формулу слишком громоздкой. В таких случаях функцию или кривую будем обозначать одной греческой буквой, например, у.
   Сначала выразим длину кривой. Возьмем её небольшой участок. Пусть на нём t меняется от т— iо д, ах- от £- до Д На малом промежутке можно приближенно считать, что длина кривой равна длине секущей - отрезка, соединяющего точки


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

12



�лоскости (Tj_₁,^i_₁) и (Ti,^i). По теореме Пифагора, длина этого отрезка равна


△li — (J(Ti - Ti-i)² + (& ⁻ €i-i⁾² — (J(△Ti⁾‘² + (△&)²■

Если разбить всю кривую на мелкие участки точками (ri, £i), i — 0, ■ ■ ■, N, т₀ — t₀, tₙ — ti, и сложить длины всех секущих, то получится интегральная сумма

N
Sa — £ △li.
i=1

   Обозначим e(SA) — maxi △lᵢ. Теперь будем переходить ко всё более мелкому разбиению кривой, неограниченно увеличивая N так, чтобы e(SA) стремилось к нулю. Если этот предел существует и не зависит от последовательности разбиений, то он называется длиной кривой. Таким образом, длина кривой у выражается в виде криволинейного интеграла

J (у) — lim Sa — J dl — j ddt² + dx² ■


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

J (>(■))

ti
У у/1 + х²(t)dt to

Здесь через x(t) обозначена скорость (проггзводпая пути по времени) x'(t) — dxt)- Величина J представляет собой функцию от функции и называется функционалом. Из свойств интеграла вытекает, что функционал аддитивен. Это значит, что если кривая разбита па несколько участков, то значение функционала па всей кривой равно сумме значений функционала па отдельных участках. Формально это легко записывается, если снова обозначить кривую одной буквой, у — х(ф а разбиение кривой, предположим, на 3 участка 5, е, у понимать как конкатенацию у — 6 Л е Л у или, проще, как произведение у — 5еу. Тогда


J (т) — J ⁽⁵еП) — J ⁽⁵⁾ + J ⁽е⁾ + J (п)
   Другие свойства разбиения кривой будут рассмотрены в основном тексте.
   В общем случае функционал в вариационном исчислении записывается в виде

J (Y) —

J (xQ) — f to

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

где у — xQ - вектор-функция, L - функция Лагранжа. Для нахождения экстремума функционала составляется уравнение Эйлера — Лагранжа

13