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

Актуальность работы. Работа посвящена исследованию свойств задачи оптимального управления с фиксированным моментом окончания и роли характеристик уравнения Гамильтона-Якоби-Беллмана в численном решении этой задачи. Предлагается конструкция сеточного оптимального синтеза и исследуется ее эффективность. Разработаны и протестированы на ряде модельных задач оптимального управления программные реализации предложенных алгоритмов. Рассмотрено приложение конструкции сеточного оптимального синтеза к исследованию макроэкономической модели.

Истоки теории оптимального управления восходят к работам JI.C. Понт-рягина [Ij, R. Bellman [2], H.H. Красовского [3], R. Isaacs, W.H. Fleming,.

A. Fridman.

Фундаментальный вклад в развитие теории оптимального управления внесли В. Г. Болтянский, Р. В. Гамкрелидзе, Е. Ф. Мищенко, Б. Н. Пшеничный, H.H. Моисеев, Ф. Л. Черноусько, В. А. Якубович, Ю. Г. Евтушенко, L.D. Berkovitz, А.Е. Bryson, F.H. Clarke, G. Leitmann, Y.-C. Ho, R. Olsder, E.O. Roxin, J. Warga, R.J. Elliott, N.J. Kalton.

Существенное развитие теория получила в работах В. И. Зубова, Ф. М. Кирилловой, Р. Ф. Габасова, В. Ф. Кротова, A.A. Меликяна, A.A. Чи-крия, С. М. Асеева, A.A. Аграчева, Л. Д. Акуленко, A.B. Арутюнова, В.И. Бла-годатских, Н. Л. Григорепко, А. Я. Дубовицкого, A.B. Дмитрука, В. А. Дыхты,.

B.И. Жуковского, М. И. Зеликина, А. Д. Иоффе, Ю. С. Ледяева, A.A. Милютина, М. С. Никольского, Г. К. Пожарицкого, Е. С. Половинкина, H.H. Петрова, Л. А. Петросяна, В. М. Тихомирова, Е. Л. Тонкова, В. И. Ухоботова, C.B. Чистякова.

Настоящая работа лежит в рамках концепции оптимального позиционного управления, предложенной и развитой в работах H.H. Красовского [4].

Фундаментальный вклад в развитие теории позиционного управления, наблюдения, оценивания и динамической реконструкции внесли работы Ю. С. Осипова, А. Б. Куржанского, А. И. Субботина, A.B. Кряжимского, А. Г. Ченцова, В. Н. Ушакова, В. Е. Третьякова.

Большую роль в развитии теории оптимального позиционного управления сыграли работы Э. Г. Альбрехта, М. И. Гусева, С. Т. Завалшцина, А. Ф. Клейменова, А. И. Короткого, Е. К. Костоусовой, А. Н. Красовского, Н. Ю. Лукояпова, В. И. Максимова, О. И. Никонова, B.C. Пацко, В.Г. Пиме-нова, А. Н. Сесекина, H.H. Субботиной, A.M. Тарасьева, Т. Ф. Филипповой, А. Ф. Шорикова, В. Я. Джафарова, Х. Г. Гусейнова и их учеников.

Ключевым понятием в теории оптимального позиционного управления является функция цены, которая начальному состоянию управляемой системы ставит в соответствие оптимальный гарантированный результат. Эта функция лежит в основе конструкции оптимального синтеза — оптимального управления по принципу обратной связи.

Как правило, функция цены в рассматриваемых задачах оптимального управления является негладкой. Хорошо известно, что в точках дифферен-цирусмости она удовлетворяет уравнению в частных производных первого порядка (уравнению Гамильтона-Якоби-Беллмана), связанному с изучаемой задачей управления. В современной теории обобщенных решений уравнений Гамильтона-Якоби доказано, что функция цены для задачи управления совпадает с единственным минимаксным/вязкостным [5, 6] решением соответствующей краевой задачи Коши для уравнения Гамильтона-Якоби-Беллмана.

В случае, когда существует классическое (гладкое) решение задачи Коши для уравнения Гамильтона-Якоби-Беллмана, оно может быть построено с помощью классического метода характеристик Коши (см., например, [7, 8]). Этот метод сводит интегрирование уравнения в частных производных первого порядка к интегрированию системы обыкновенных дифференциальных уравнений, решения которой называются характеристиками. Как доказано в работах F.H. Clarke [9], N. Barron [10], S. Mirica [11], H.H. Субботиной [12], использование классических характеристик уравнения Гамильтона—Якоби-Беллмана обеспечивает исследователя необходимыми и достаточными условиями оптимальности в классе программных управлений.

В современной теории обобщенных решений уравнений Гамильтона-Яко-би и соответствующих задач динамической оптимизации рассматриваются различные обобщения понятия характеристики. Новые подходы к определению обобщенных характеристик предложены в работах А. И. Субботина [5], A.B. Куржанского [13], Ю. С. Ледяева [14], A.A. Меликяна [15], В.И. Благо-датских и А. Ф. Филиппова [16], A.A. Толстоногова [17], А. И. Булгакова [18], А. Cellina [19], J.P. Aubin и H. Frankowska [20], G. Haddad [21].

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

К настоящему времени разработано большое количество численных методов решения задач оптимального управления (см., например, [22—36] и библиографию к этим работам). Среди них можно выделить две группы методов. К первой относятся методы, нацеленные на построение оптимального программного управления: методы, основывающиеся на решении двухточечной краевой задачи, сле, лующей из принципа максимума Л. С. Понтрягинаметоды последовательных приближенийградиентные методы в пространстве управлений, методы, опирающиеся на конструирование областей достижимости. Разработке этих методов посвящены работы Ф. П. Васильева, В.Л. Гаси-лова, В. Б. Костоусова, Ю. И. Бердышева, Ю. Н. Киселева, H.H. Болотника, И. М. Апаньевского, Б. Н. Соколова, Н. В. Баничука, Д. В. Камзолкина и многих других известных математиков.

Упомянем метод, предложенный И. А. Крыловым и Ф. Л. Черноусько [25] для задачи оптимального управления с терминальным функционалом. Метод основан на необходимом условии оптимальности — принципе максимума Понт-рягина. Рассматривается двухточечная краевая задача для управляемой и сопряженной систем. Для вычисления экстремальной траектории и управления применяется метод последовательных приближений.

Вторую группу составляют методы, нацеленные на построение оптимального синтеза, основанные на методе динамического программирования и связанные с решением уравнения Гамильтона-Якоби. Существенный вклад в развитие этого направления внесли работы В. Н. Ушакова, B.C. Пацко, A.M. Тарасьева, А. Г. Пашкова, С. И. Кумкова, A.A. Успенского, P. Souganidis, М. Falcone. Численные алгоритмы конструкций позиционного оптимального управления успешно разрабатывались в работах В. А. Вахрушева, В.Л. Туро-вой, С. С. Кумкова, Д. А. Серкова, Л. Г. Шагаловой, А. П. Хрипунова.

Классический численный метод построения функции цены и оптимального синтеза — метод динамического программирования Р. Беллмана [2, 22]. Он состоит в замене непрерывной задачи ее конечно-разностной аппроксимацией и применении попятной процедуры последовательного решения вспомогательных задач конечномерной минимизации.

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

В работах P. Souganidis[24], A.M. Тарасьева, A.A. Успенского, В. Н. Ушакова [37] предложены численные алгоритмы построения функции цены дифференциальной игры. Рассматривая фиктивного второго игрока, можно использовать алгоритм для построения функции цены задачи оптимального управления. Оптимальное позиционное управление строится с помощью метода экстремального прицеливания на множества уровня функции цены. Основой алгоритмов аппроксимации функции цены служат разностные операторы, базирующиеся на построении локальных выпуклых и вогнутых оболочек. Аппроксимация функции цены строится с помощью попятной процедуры на последовательности регулярных, но пространству сеток. Получена оценка погрешности метода, имеющая порядок корня квадратного из шага интегрирования.

В работе Д. В. Камзолкина [38] задача оптимального управления с интегрально-терминальным функционалом решается в прямоугольной области [О, Т] х X С Ж. х Мп. Область разбивается на прямоугольные ячейки, каждой из которых ставится в соответствие постоянная величина — значение аппроксимации функции цены, которая подсчитывается согласно репрезентативной формуле функции цены, использующей характеристики уравнения Гамиль-тона-Якоби, приходящие в данную ячейку из заданной области К в конечный момент времени. Погрешность аппроксимации функции цены обратно пропорциональна числу ячеек.

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

Цели диссертационной работы. Исследование свойств функции цены задачи оптимального управления с непрерывными по времени и дифференцируемыми по фазовой переменной входными даннымиразработка и обоснование численных методов аппроксимации функции цены и построения сеточного оптимального синтеза в рассматриваемой задаче оптимального управления на базе классических характеристик уравнения Гамильтона-Якоби-Беллма-напрограммная реализация численных методов и решение модельных задач теории оптимального управленияприложение конструкций сеточного оптимального синтеза к анализу модели макроэкономической системы.

Методы исследования. Основным методом исследования является метод характеристик, который является обобщением классического метода Ко-ши для уравнения Гамильтона—Якоби. Для анализа минимаксных решений уравнений Гамильтона-Якоби применяются методы и аппарат негладкого анализа.

Для доказательства оптимальности полученных конструкций применяется необходимое условие — принцип максимума Понтрягипа в форме системы гамильтоновых включений, обоснованное Ф. Кларком [39].

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

При доказательстве утверждений о порядке сходимости численной процедуры построения аппроксимации решения задачи Коши для уравнения Гамильтона-Якоби была получена рекуррентная система оценок. Для ее решения была применена линеаризация и метод теории рекурсии, аналогичный методу решения системы обыкновенных линейных дифференциальных уравнений [40].

Для получения констант в оценке точности данного метода аппроксимации применялся пакет символьных вычислений из системы Matlab.

При программной реализации численных методов использованы методы вычислительной геометрии (триангуляция Делоне, диаграммы Вороного) [41].

Численные методы были реализованы автором в виде программы на языке С++ в среде Microsoft Visual С++ 2008 Express Edition. В программе использовались следующие библиотеки: для общих целей — библиотека BOOST (сайт проекта http://www.boost.org/) — для геометрических вычислений в двумерном пространстве — библиотека алгоритмов вычислительной геометрии CGAL (сайт проекта http://www.cgal.org/) — для численного интегрирования характеристической системы и использования метода наименьших квадратов — научная библиотека GNU (сайт проекта http://www.gnu.org/software/gsl/) — для визуализации результатов — система OpenGL (сайт проекта http://www.opengl.org/) — для создания иллюстраций — система преобразования из OpenGL в eps-файлы GL2PS (сайт проекта http://geuz.org/gl2ps/).

Научная новизна. Предложен новый метод решения задачи оптимального управления с фиксированным моментом окончания, при котором для нахождения оптимальных траекторий решается краевая задача Коши, где краевые условия для фазовой и сопряженной переменных заданы в один и тот же конечный момент времени (в отличие от стандартной двухточечной краевой задачи в принципе максимума JT.C. Понтрягина). Предложены новые конструкции численной аппроксимации функции цены и сеточного оптимального синтеза, определенные в узлах адаптивных сеток, лежащих на численных решениях характеристической системы.

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

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

Новым приложением конструкций сеточного оптимального синтеза является использование их для анализа динамики макроэкономической модели на основе накопленной дискретной статистики.

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

Структура, объем и краткое содержание диссертации.

Диссертация состоит из введения, 5 глав и библиографии. Общий объем диссертации 110 страниц, включая 28 рисунков. Библиография включает 56 наименований.

1. Понтрягин J1. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. Москва: Наука, 1961.

2. Bellman R. Dynamic Programming. Princeton: Univ. Press, 1957.

3. Красовский H. H. Теория управления движением. Москва: Наука, 1968.

4. Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. Москва: Наука, 1974.

5. Субботин А. И. Обобщенные решения уравнений в частных производных первого порядка. Перспективы динамической оптимизации. МоскваИжевск: Институт компьютерных исследований, 2003.

6. Crandall М. G., Lions P. L. Viscosity solutions of Hamiltion-Jacobi equations // Trans. Amer. Math. Soc. 1983. Vol. 277. Pp. 1−42.

7. Петровский И. Г. Лекции по теории обыкновенных дифференциальных уравнений. Москва: Изд-во МГУ, 1984.

8. Курант Р. Уравнения с частными производными. Москва: Мир, 1964.

9. Clarke F. Н., Vinter R. The relationship between the maximum principle and dynamic programming // S.I.A.M. J. Contr. Optimiz. 1987. Vol. 5. Pp. 1291−1311.

10. Barron E. N., Jensen R. The Pontryagin maximum principle from dynamic programming and viscosity solutions to first-order partial differential equations // Trans. Amer. Math. Soc. 1986. Vol. 298, no. 2. Pp. 635−641.

11. Mirica S. Extending Cauchy’s method of characteristics for Hamilton-Jacobi equations // Stud. Cere. Mat. 1985. Vol. 37, no. 6. Pp. 555−565.

12. Subbotina N. N. The method of characteristics for Hamilton-Jacobi equations and applications to dynamical optimization. NY: Springer, 2006.

13. Куржанский А. Б. Избранные труды. Москва: Издательство МГУ, 2009.

14. Bessis D. N., Ledyaev Y. S., Vinter R. B. Dualization of the Euler and Hamil-tonian inclusions // Nonlinear Anal. 2001. Vol. 43. P. 861−882.

15. Меликян А. А. Сингулярные характеристики уравнений в частных производных первого порядка // Доклады РАН. 1996. Т. 382, № 2. С. 203−217.

16. Благодатских В. И., Филиппов А. Ф. Дифференциальные включения и оптимальное управление // Тр. МИАН. 1985. Т. 169. С. 194−252.

17. Толстоногов А. А. Дифференциальные включения в банаховом пространстве. Москва: Наука, 1986.

18. Булгаков А. И. Интегральные включения с невыпуклыми образами и их приложения к краевым задачам дифференциальных включений // Матем. сб. 1992. Vol. 183, по. 10. Pp. 63−86.

19. Aubin J.-P., Celina A. Differential Inclusions. Berlin: Springer-Verlag, 1984.

20. Aubin J.-P., Frankowska H. Set Valued Analysis. Boston: Birkhauser, 1990.

21. Haddad G. Monotone trajectories of differential inclusions and functional-differential inclusions with memory // Israel J. Math. 1981. Vol. 39. Pp. 83−100.

22. Васильев Ф. П. Численные методы решения экстремальных задач. Москва: Наука, 1988.

23. Моисеев Н. Н. Избранные труды. Гидродинамика и механика. Оптимизация, исследование операций и теория управления. Москва: Тайдекс Ко, 2003.

24. Souganidis P. Е. Approximation schemes for viscosity solutions of Hamilton-Jacobi equations //J. Diff. Eqns. 1985. Vol. 59. Pp. 1−43.

25. Черноусько Ф. JI., Баничук H. В. Вариационные задачи мехиники и управления. Москва: Наука, 1973.

26. Кротов В. Ф., Гурман В. И. Методы и задачи оптимального управления. Москва: Наука, 1973.

27. Первозванский А. А., Гайцгори В. Г. Декомпозиция, агрегирование и приближенная оптимизация. Москва: Наука, 1979.

28. Поляк Б. Т.

Введение

в оптимизацию. Москва: Наука, 1983.

29. Уткин В. И. Скользящие режимы и их применения в системах с переменной структурой. Москва: Наука, 1974.

30. Фрадков А. Л. Кибернетическая физика: принципы и примеры. С.-Петербург: Наука, 2003.

31. Тятюшкин А. И. Многометодная технология оптимизации управляемых систем. Новосибирск: Наука, 2006.

32. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. Москва: Наука, 1982.

33. Полак Э. Численные методы оптимизации. Единый подход. Москва: Мир, 1974.

34. Нурминский Е. А. Численные методы выпуклой оптимизации. Москва: Наука, 1991.

35. Фурасов В. Д. Задачи гарантированной идентификации. Москва: Бином. Лаборатория знаний, 2005.

36. Марчук Г. И. Методы вычислительной математики. Москва: Наука, 1977.

37. Тарасьев А. М., Успенский А. А., Ушаков В. Н. Аппроксимационные схемы и конечно-разностные операторы для построения обобщенных решений уравнений Гамильтона-Якоби // Изв. РАН. Техн. кибернетика. 1994. Т. 3. С. 173−185.

38. Камзолкин Д. В. Методы решения некоторых классов задач оптимального управления и дифференциальных игр: Кандидатская диссертация / ВМК МГУ им. Ломоносова. 2005.

39. Кларк Ф. Оптимизация и негладкий анализ. Москва: Наука, 1988.

40. Грин Д., Кнут Д. Математические методы анализа алгоритмов. Москва: Мир, 1987.

41. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Москва: Мир, 1989.

42. Crandall M. G., Lions P.-L. Viscosity Solutions of Hamilton-Jacobi Equations // Trans. Am. Math. Soc. 1983. Vol. 277:1. Pp. 1−42.

43. Филиппов А. Ф. О некоторых вопросах теории оптимального регулирова-' ния // Вестник Моск. Ун.-та. 1959. № 2. С. 25−32.

44. Болтянский В. Г. Математические методы оптимального управления. Москва: Наука, 1969.

45. Пацко В. С. Поверхности переключения в линейных дифференциальных играх. Екатеринбург: ИММ УрО РАН, 2004.

46. Субботина H. Н. Обобщенный метод характеристик в задаче оптимального управления с липшицевыми входными данными // Изв. УрГУ: Математика и механика. 2006. Т. 4. С. 171−176.

47. Экланд И., Темам Р. Выпуклый анализ и вариационные проблемы. Москва: Мир, 1979.

48. Варга Д. Оптимальное управление дифференциальными и функциональными уравнениями. Москва: Наука, 1977.

49. Шолохович Ф. А. Лекции по дифференциальным уравнениям. Екатеринбург: Уральское изд-во, 2005.

50. Понтрягин JI. С. Обыкновенные дифференциальные уравнения. Москва: Наука, 1974.

51. Clarke F. Н., Ledyaev Y. S., Stern R. J., Wolensky P. R. Nonsmooth Analysis and Control Theory. NY: Springer, 1998.

52. Субботина H. Н., Колпакова Е. А. Численное решение оптимизационных задач вибрационной механики с помощью метода характеристик // Прикладная математика и механика. 2010. Т. 74(5). С. 832−839.

53. Филиппов А. Ф. Дифференциальные уравнения с разрывной правой частью. Москва: Наука, 1985.

54. Rockafellar R. Т., Wets R. J.-B. Variational Analysis. NY: Springer, 1997.

55. Джафаров В. Я., Субботина Н. Н. Достаточные условия для непрерывных е-оптимальных обратных связей в задачах управления с терминальной платой // Прикладная математика и механика. 2011. Т. 75(3). С. (в печати).

56. Альбрехт Э. Г. Методика построения и идентификации математических моделей макроэкономических процессов // Электронный журнал «Исследовано в России». 2002. Т. 5. С. 54−86.