Эллипсоидальные аппроксимации трубок достижимости управляемых систем при неопределённости тема диссертации и автореферата по ВАК РФ 01.01.02, кандидат физико-математических наук Гагаринов, Петр Владимирович

• Гагаринов, Петр Владимирович
• кандидат физико-математических наук
• 2013

Введение диссертации (часть автореферата) на тему «Эллипсоидальные аппроксимации трубок достижимости управляемых систем при неопределённости»

Решение задачи управления по принципу обратной связи является центральной в математической теории управления, особенно для систем, функционирующих в условиях неопределённости, конфликта и недостатка информации [30,31,60,86]. Основным стимулом для возникновения соответствующей математической теории явились прикладные задачи управления движением, автоматики, робототехники и.т.д. В настоящее время подобные задачи возникают в моделях управления транспортными потоками, при изучении квантовых процессов, управления энергосистемами, а также в других моделях высоких технологий. Важную роль в решении подобных задач является сведение их к проблеме достижимости для линейных и нелинейных систем.

Настоящая диссертация посвящена задаче оценивания областей достижимости и попя тных областей разрешимости для линейных систем при неопределённости с управлением II форме обратной связи. Построение трубок решений, описывающих эволюцию областей достижимости управляемых систем в прямом и попятном времени, является одним из основных подходов к решению задач синтеза управления и гарантированного оценивания для таких систем. Использование метода динамического программирования, развитого Р. Беллманом [23| и Р. Айзексом [22], в том числе, для систем с неопределённостью, позволяет находить области достижимости как множества уровня функции цены для соответствующей задачи оптимизации. Такая функция цепы является решением уравнения в частных производных типа Гамильтона-Якоби-Беллмана-Айзекса (ШВ1). Но в общем случае эта функция цены нередко оказываются не всюду гладкой. Понятия обобщённых решений, таких как вязкостные решения П.Л.Лпонса и М.Г. Крендалла [77], а также минимаксные решения А.И. Субботина [65) позволили существенно расширить область применимости данного подхода, однако нахождение таких решений трсбуюч значительно вычислительной нагрузки. В тоже время, для линейных систем с выпуклыми ограничениями, обобщённые решения не обязательны, так как функции цены выпуклы и следовательно всюду дифференцируемы по любому направлению. Их можно точно описать при помощи теории двойственности выпуклого анализа. Использование множеств уровня функций цены, их подробное описание и возможность их вычисления позволили разработать эффективные методы описания их сечений в виде трубок достижимости как многозначных функций. Далее последовала теория аппроксимаций выпуклозначных функций при помощи эллипосидальных трубок (см. А.Б. Куржанский -[4,8-10,12,13,15,41,80]).

В данной диссертации рассматривается теория аппроксимаций для трубок достижимости при неопределённости. Такие точные трубки в прямом времени имеют самостоятельное значение. В обратном же времени они совпадают по своим основным свойствам с понятиями альтернированного интеграла Л.С. Поптрягина и моста Н.Н.Красовского. Упомянутый альтернированный интеграл был введён в работах [3,59] при геометрических ограничениях на управление и неопределённость. Дальнейший вклад в изучение свойств данного интеграла внесли М.С. Никольский, Е.Ф. Мищенко, А.П. Пономарев, Е.С. Половинкин, Н.Х. Розов [53] . (Следует заметить, что предложенные методы вычисления этого интеграла приводят к значительным вычислительным трудностям, связанным с необходимостью искать выпуклые оболочки надграфиков разностей опорных функций в многомерном пространстве. Последнее особенно касается систем высокой размерности.). Описание мостов Н.Н.Красовского дано в работах |30,31,69-72,79].

Аппарат эллипсоидального исчисления, разработанный в работах A.B. Куржанского и его соавторов, позволяет искать трубки достижимости при неопределённости в задаче с непрерывной коррекцией в виде "тугих" внешних и внутренних эллипсоидов ("касающихся" изнутри вдоль "хороших" кривых, определяемых фундаментальной .матрицей линейной системы). Подход к вычислениям более трудных внутренних эллипсоидальных оценок трубок с параметрами, являющимися решением обыкновенных дифференциальных уравнений описан в работах [4,8,9,12,13,15,41,80,87]. Этот поход рассматривался при некоторых условиях невырожденности. Заметим, однако, что поскольку в конструкцию таких тугих эллипсоидальных оценок заложено предположение о равенстве разности опорных функции вдоль направлений касания внутренних оценок и альтернированного множества достижимости, они склонны вырождаться в те моменты, когда данное предположение перестаёт выполняться. Последнее особенно актуально для систем большой размерности при малой размерности управления. Метод регуляризации эллипсоидальных аппроксимаций путем перемешивания нескольких эллипсоидальных оценок, предложенный в работе [82], позволяет преодолеть указанные сложности, в частности и для систем высоких размерностей (п ^ 500). Диссертация же посвящена альтернативному метод}' регуляризации, основанному па видоизменении структуры самого альтернированного интеграла, для которого получаются невырождающиеся тугие эллипсоидальные аппроксимации.

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

Основные результаты работы.

1. Введены операции квадратичного суммирования и вычитания центрально-симметричных компактов. Исследованы свойства этих операции и получены оценки, связывающие операции квадратичного суммирования и вычитания с алгебраической суммой и геометрической разностью. В частности получены асимптотические оценки квадратичной суммы через алгебраическую сумму для центрально-симметричного компакта и эллипсоида.

2. С использованием новых операции введено понятие квадратично-регуляризованного альтернированного множества достижимости, доказана теорема о его существовании и единственности. Построены схемы внутренних и внешних тугих эллипсоидальных оценок с адаптивной регуляризацией для квадратпчно-регуляризированных альтернирован!патрубок достижимости. Построены оценки квадратичного альтернированного множества через "обычные" альтернированные множества. Предложена схема комбинирования оценок для разных направлении.

3. Построены алгоритмы проецирования на статические и динамические (обусловленные фундаментальной матрицей системы) подпространства. Построены эллипсоидальные оценки квадратично-регуляризировапного альтернированного множества достижимости к моменту и его границы.

4. Введены операции ^-суммирования и р-вычитания центрально-симметричных компактов как обобщённые варианты квадратичной суммы и разности. Исследованы свойства обобщённых операций и получены оценки, связывающенпе результаты применения данных операций для разных значений степени р.

Научная новизна работы. Полученные результаты являются новыми. В работе рассмотрено не изучавшееся ранее квадратичио-регулярпзированное альтернированное множество достижимости, а также операции операции квадратичного суммирования и вычитания множеств и их обобщения на случай произвольного р > 1. Для регуляризироваиного множества достижимости получены оценки, связывающие его с исходным классическим множеством. Эллипсоидальные оценки с адаптивным выбором регуляризирующих параметров решают проблему вырождения оценок, представленных в [9] и являются их обобщением.

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

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

Апробация работы. Результаты работы были представлены в виде докладов на научно-исследовательских семинарах кафедры системного анализа факультета ВМиК МГУ (рук. Кур-жаиский A.B.), отдела динамических систем ИММ УрО РАН (рук. Ушаков В.Н.), а также на международной конференции студентов и аспирантов по фундаментальным паукам "Ломопосов-2013" (Москва, МГУ, апрель 2013 г.)

Публикации. По теме диссертации опубликовано 2 работы.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и библиографии. Общий объем диссертации 104 страниц. Библиография включает 87 наименований.

Заключение диссертации по теме «Дифференциальные уравнения», Гагаринов, Петр Владимирович

Основные результаты работы состоят в следующем:

1. Введены операции квадратичного суммирования и вычитания центрально-симметричных компактов. Исследованы свойства этих операций и получены оценки, связывающие операции квадратичного суммирования и вычитания с алгебраической суммой и геометрической разностью. В частности получены асимптотические оценки квадратичной суммы через алгебраическую сумму для центрально-симметричного компакта и эллипсоида.

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

3. Построены алгоритмы проецирования на статические и динамические (обусловленные фундаментальной матрицей системы) подпространства. Построены эллипсоидальные оценки квадратично-регуляризнрованного альтернированного множества достижимости к моменту и его границы.

4. Введены операции /^суммирования и р-вычитания центрально-симметричных компактов как обобщённые варианты квадратичной суммы и разности. Исследованы свойства обобщённых операций и получены оценки, связывающение результаты применения данных операций для разных значений степени р.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Гагаринов, Петр Владимирович, 2013 год

1. Гагаринов П.В. Вычисление проекций трубок достижимости линейных управляемых систем на основе методов эллипсоидального исчисления. Вести. Моск. ун-та., (1):14—24. 2007.2| Ф.Р.Гантмахер. Теория .матриц. Наука, 1988.

2. Поптрягин JI.C. Линейные дифферент;! 1альные игры преследования. Математический сборник, 112(154)(3(7)):307-330, 1980.

3. Куржанский А.Б., Мельников Н.В. О задаче синтеза управлений: альтернированный интеграл Поптрягипа и уравнение Гамильтопа-Якоби. Мат. сборник, 191 (в):69—100, 2000.

4. Boyd S.P., Vandenberghe L. Convex Optimization. Cambridge University Press, 1988.

5. Dormand J.R., Prince P.J. A family of embedded runge-knt,ta formulae. J. Сотр. Appl. Math., (6): 19—26, 1980.

6. Гагаринов П.В. Вычисление альтернированных трубок достижимости линейных управляемых систем при неопределённости. Вестн. Моск. ун-та(4): 17-24, 2012.

7. Kurzhanski А.В., Varaiya P. On reachability under uncertainty. SI AM J. Control Optim., 41(1): 181—216, 2002.

8. Kurzhanski А.В., Varaiya P. On ellipsoidal techniques for reachability analysis, part i. external approximations. Optimization Methods and Software, 17:177-206, 2001.

9. Vazlientsev A.Y. External ellipsoidal estimation of the union of two concentric ellipsoids and its applications. Computational Mathematics and Modeling, 15(2), 2004.17| P. Хорн, Ч. Джонсон. Матричный анализ. Мир, 1989.

10. Р.Рокафеллар. Выпуклый анализ. Мир, 1989.

11. Куржанский А.Б. Альтернированный интеграл понтрягина в теории синтеза управлений. Труды математического института им,. В.А. Стеклова, 224:234-248, 1999.

12. В.А.Ильин, Г.Д.Ким. Линейная алгебра и аналитическая геометрия. Изд-во МГУ, 1998.

13. Азамов А. О. О втором методе Понтрягина в линейных дифференциальных играх преследования. Математический сборник, И8(160)(3 (7)):422-430, 1982.

14. Айзеке Р. Дифференциальные игры. Мир, 1967.

15. Беллман Р. Динамическое программирование. ИЛ, 1960.

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

17. Иванов Г. Е., Половинкин Е. С. О сильно выпуклых линейных дифференциальных играх. Дифференциальные уравнения, 31(10):1 G41—1648, 1995.

18. Колмогоров А. П., Фомин С. В. Элементы теории (функций и функционального анализа. Наука, 5 edition, 1981.29| Красовский Н. Н. К задаче об успокоении линейной системы при минимальной интенсивности управления. ПММ, 29(2):218-225, 1965.

19. Красовский П. Н. Теория управления движением. Наука, 1968.

20. Красовский 11. Н. Игровые задачи о встрече двиэюений. Наука, 1970.

21. Красовскпй Н. Н. Минимаксное поглощение в игре сближения. ПММ, 35(6):945-951, 1971.

22. Красовский II. Н. Дифференциальная игра сближения-уклонения ь Известь я АН СССР. Техническая кибернетика, (2):3-18, 1973.

23. Красовский Н. II. Дифференциальная игра сближения-уклонения п. Известия АН СССР. Техническая кибернетика, (3):22—41, 1973.

24. Красовский Н. II. Дифференциальные игры. Аппроксимациоиные и формальные модели. Математический сборник 107(149)(4(12)):541-571, 1978.

25. Красовский Н. II. Управление динамической системой. Наука, 1985.

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

27. Красовский II. Н., Субботин А. И.„ Ушаков В. Н. Минимаксная дифференциальная игра. Доклады АН СССР, 20б(2):277-280, 1972.

28. Куржанский А. Б. Уггравление и наблюде-ние в условиях неопределенности. Наука, 1977.

29. Куржанский А. Б. Дифференциальные игры сближения при ограниченных фазовых координатах. Доклады АН СССР, 192(3):491-494, 1970.

30. Куржанский А. Б. Альтернированный интеграл Понтрягина в теории синтеза управлений. Труды МИ АН, 224:234-248, 1999.

31. Куржанский А. Б., Никонов О. И. К задаче синтеза стратегий управления. Эволюционные уравнения и многозначное интегрирование. Доклады АН СССР, 311(4):788-793, 1990.

32. Ледясв Ю. С. Регулярные дифференциальные игры со смешанными ограничениями па управления. Труды МИ А Я, 167:207-215, 1985.

33. Мищенко Е. Ф. Задачи преследования и уклонения от встречи в теории дифференциальных игр. Известия АН СССР. Техническая кибернетика, 5:3-9, 1971.

34. Мищенко Е. Ф., Понтрягин Л. С. Линейные дифференциальные игры. Доклады АН СССР, 174(1):27—29, 1967.

35. Никайдо X. Выпуклые структуры и математическая экономика. Мир, 1972.

36. Никольский М. С. Нестационарные линейные дифференциальные игры. Вестник МГУ, (3):65-73, 1969.

37. Никольский М. С. Об альтернированном интеграле Л. С. Понтрягина. Математический сборник, 126(158) (1(9)): 136-144, 1981.

38. Половникин Е. С., Иванов Г. Е., Балашов В., Константинов Р. В.,. Хорев А. В. Об одном алгоритме численного решения линейных дифференциальных игр. Математический сборник, 192(10):95—122, 2001.

39. Пономарев А. П. Оценка погрешности численного метода построения альтернированного интеграла Понтрягина. Вестник МГУ, 4:37-43. 1978.

40. Пономарев А. П., Розов Н. X. Устойчивость и сходимость альтернированных сумм Понтрягина. Вестник МГУ, 1:82-90, 1978.

41. Пономарев А. П., Розов Н. X. О дифференцируемое™ опорной функции альтернированного интеграла. Математические заметки, 30(6):865-870, 1981.

42. Поптрягин Л. С. Обыкновенные дифференциальные уравнения. Наука, 5 edition, 1982.

43. Поптрягин Л. С. О линейных дифференциальных играх i. Доклады АН СССР, 174(6):1278-1280, 1967.

44. Поптрягин Л. С. О линейных дифференциальных играх ii. Доклады АН СССР. 175(4):910 -912, 1967.

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

46. Сансоне Д. Обыкновенные дифференциальные уравнения. ИЛ, 1953.

47. Субботин А. И. К задаче об игровой встрече движений. ПММ, 31:834-840. 1967.

48. Субботин А. И. Экстремальные стратегии в дифференциальных играх с полной памятью. Доклады АН СССР, 206(3):552-555, 1972.

49. Субботин А. И. Минимаксные неравенства и уравнения Гамильтона-Якоба. Наука, 1991.

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

51. Субботин А. И., Ченцов А. Г. Оптимизация гарантии в задачах управления. Наука, 1981.

52. G7| Субботина H. Н. Метод динамического программирования для класса локально-лпшпицевых систем. Доклады РАН, 389(2):1-4, 2003.

53. G8| Тихонов А. Н., Васильева А. Б.„ Свешников А. Г. Дифферетщальные уравнения. Наука, 1980.

54. Ушаков В. Н. К вопросу стабильности в дифференциальных играх. Позицио иное управление с гарантировантлм результатом, pages 101-109, 1988.

55. Ушаков В. Н. Процедуры построения стабильных мостов в дифференциальных играх: Дис. д-ра физ.-мат. наук: 01.01.02. Ин-т математики и механики УрО АН СССР, 1991.

56. Ушаков В. Н. Успенский А.А.„ Токманцев Т.Б. К вопросу стабильности в дифференциальных играх. Труды Института математики и механики УрО РАН, pages 155-177. 2004.

57. Ушаков В. Н. К задаче построения стабильных мостов в дифференциальной игре сближения-уклонения. Известия АН СССР. Техническая кибернетика, (4):29-3G, 1980.

58. Черноусько Ф. Л., Меликян А. А. Игровые задачи управления и поиска. Наука, 1978.

59. Aubin Л .Р., Frankowska H. Set-valued Analysis. Birkhauser, 1990.

60. Crandall M. G., Lions P.L. Viscosity solutions of hamilton-jacobi equations. Transactions of American Mathematical Society, 277:1-41, 1983.78| Krasovski N. N., Subbotin A. I. Positional Differential Games. Springer Verlag, 1988.

61. Krasovski N. N., Subbotin A. I. Game-theoretical control problems. Springer Verlag, 1987.

62. Kurzhanski А. В., Varaiya P. Dynamic optimization for reachability problems. Journal of Optimization Theory and Applications, 108(2):227-251, 2001.

63. Ky F. Minimax theorems. Proc. Nat. Acad, of S ci., 39(l):42-47, 1953.

64. Пшеничный Б.Н. Необходимые условия экстремума. Наука, 2 edition, 1982.

65. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. Наука, 1980.

66. М.М. Lee, L. Markus. Foundations of Optimal Control Theory. Whiley, 1967.