Методы решения некоторых классов задач оптимального управления на основе соприкасающихся эллипсоидов тема диссертации и автореферата по ВАК РФ 01.01.02, кандидат физико-математических наук Хабаров, Николай Васильевич

• Хабаров, Николай Васильевич
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Хабаров, Николай Васильевич

Список обозначений

Введение

1 Алгоритм проектирования точки на множество на основе эллипсоидов

1.1 Постановка задачи.

1.2 Описание численного метода.

1.3 Скорость сходимости метода.

1.4 Модификация метода (промежуточная одномерная оптимизация).

1.5 Некоторые примеры расчетов.

1.5.1 Квадратичная скорость сходимости.

1.5.2 Случай зацикливания.

1.5.3 Пример использования метода с промежуточной одномерной оптимизацией

1.5.4 Сравнение с методом проектирования на основе потенциала.

1.5.5 Применение метода для решения задачи оптимального управления с терминальным функционалом.

2 Ньютоновский алгоритм проектирования с гарантированной сходимостью

2.1 Предварительные замечания.

2.2 Описание численного метода.

2.3 Сходимость метода.

2.4 Скорость сходимости метода.

3 Алгоритм решения задачи захвата точки семейством выпуклых множеств

3.1 Постановка задачи.

3.2 Описание численного метода.

3.3 Сходимость численного метода.

3.4 Скорость сходимости метода.

3.5 Некоторые примеры расчетов.

4 Алгоритм решения задачи быстродействия на основе проектирования начального состояния на соприкасающиеся эллипсоиды

4.1 Описание численного метода.

4.2 Скорость сходимости метода.:.

4.3 Некоторые примеры расчетов.

4.4 Решение задачи управления линейным динамическим объектом

4.5 Замечания об эффективности метода.

5 Ньютоновский алгоритм решения задачи быстродействия с гарантированной сходимостью

5.1 Описание численного метода.

5.2 Сходимость метода.

5.3 Скорость сходимости метода.

Введение диссертации (часть автореферата) на тему «Методы решения некоторых классов задач оптимального управления на основе соприкасающихся эллипсоидов»

Теория оптимального управления, развитая на рубеже пятидесятых и шестидесятых годов группой выдающихся советских ученых во главе с Л.С.Понтрягиным [1], получила всеобщее признание как фундаментальное теоретическое достижение и нашла широкое применение в приложениях.

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

Линейный характер поведения динамического объекта определяет "выпуклость" задачи и позволяет провести исследование в весьма удобном виде, что приводит к получению компактно формулируемых результатов. Рассмотрение гладких задач можно признать удачным выбором формулировки проблемы, позволяющей перейти к построению эффективных вычислительных алгоритмов. Математическая постановка гладких задач оптимального управления в терминах опорной функции области управления, а также обоснование целесообразности такой постановки предложены Ю.Н.Киселевым [4]. Исследование взаимосвязи гладких и негладких задач проведено Ю.Н.Киселевым и С.Н.Аввакумовым, а также предложены алгоритмы "сглаживания" задачи [5]. Большую практическую экспериментальную и исследовательскую работу в этом направлении выполнил М.В.Орлов [6], [7].

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

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

К числу отправных исследований нужно отнести результаты, полученные Ю.Н.Киселевым: конструкцию соприкасающегося эллипсоида, предложенную для аппроксимации гладких выпуклых компактов [8], идею и методы "одномерной оптимизации", также высказанные в других формах, в частности, Дж.Итоном и В.Г.Болтянским, теорему о квадратичной скорости сходимости метода проектирования начального состояния на изохрону, изложенную в [4], специальную параметризацию начального значения сопряженной переменной, предложенную в работе [9].

Основой для исследованных в работе методов решения задач оптимального управления служат эллипсоиды, построенные специальным образом. Эллипсоидальные конструкции применялись ранее для аппроксимации множеств достижимости управляемых систем. Этой проблематике посвящены работы Ф.Л.Черноусько [10], А.Б.Куржанского и П.Варайя [11, 12]. Предложенные эллипсоидальные аппроксимации ставят своей целью прежде всего оценку возможных фазовых состояний динамической системы; использованная в данной работе конструкция имеет иное предназначение. На основе квадратичного порядка аппроксимации границы множества достижимости (управляемости) соприкасающимся эллипсоидом строятся алгоритмы решения задач оптимального управления, обладающие квадратичной скоростью сходимости.

Геометрический смысл гладкости выпуклого компактного множества состоит в существовании в любой его граничной точке соприкасающегося невырожденного эллиптического параболоида. Соприкасающиеся параболоиды рассмотрены, например, в [13], [14]. В [4] излагается та же конструкция применительно к границе гладких выпуклых компактов. Соприкасающийся параболоид локально приближает исходный компакт, являясь неограниченным множеством. Для локальной аппроксимации гладких компактов Ю.Н.Киселевым предложена более совершенная конструкция - соприкасающийся эллипсоид [8]. Гладкий выпуклый компакт М € Г (К") с опорной функцией а (ф) = с(Л4,ф) имеет соприкасающийся эллипсоид £(р) = £(Л4,р) в любом направлении р € К?, р ф 0, который определяется опорной функцией с(£(р), Ф) = (а(р), ф) + у/ф*В(р)ф, где а(р) = 1[</(р)+</(-р) 1еГ,

В(р) = \{а{р) + а(-р)]<г"(р) + ИР) - «(р)Мр) - "(?)]* G R"™

Конструкция соприкасающегося эллипсоида применяется в данной работе для аппроксимации множеств достижимости X(to, t,xо) и управляемости Z(t, t\,x\) линейной динамической системы с гладкой областью управления Ы: x{t) = Ax(t) + u{t), x{t) G R", u(t) eUe r(Ru).

Эти множества, как показано в [4], являются гладкими выпуклыми компактами, их опорные функции имеют следующий вид: c(*(*0, t, х0), ф) = ф*еА^х0 + f c{U, еА'^ф№, c(Z(t, ti,xi), -ф) = -ф*еА«-ь^хх + f 1 c{U,eA'(t-*H)ds, где x(t0) = Xq и x(ti) = хг.

Рассматриваются задача быстродействия в начало координат x(t) = Ax(t) + u(t), х{0) = х0, х{Т) = 0, (!)

Т —> min и задача с терминальным функционалом типа "норма разности" ii(£) = Ax(t) + u(t), s(0) = х0, (2) x(T)-yf-+mm, целевая точка у и момент времени Т предполагаются здесь зафиксированными.

На основании уравнений принципа максимума Л.С.Понтрягина, оптимальное управление в задачах (1) и (2) записывается в форме и.(*)= Сф(и,е~А'%), где р, € К", р* ф 0 - оптимальное начальное значение сопряженной переменной, единственное с точностью до положительнбго множителя, которое для задачи (1) определяется условием c{Z(Q,U,xi),-p+) = (х0,-р*), (3) здесь £* - время быстродействия - есть момент первого захвата точки х0 семейством множеств Z(0, t, Xi), xi = О G R". В задаче (2) оптимальное начальное значение сопряженной переменной имеет вид еА'тр, где р = у- п{Х(О, Т,х0),у), (4) где 7г(Л,х) = argmin | а — х | - оператор проектирования точки х на выпуклый компакт аел

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

Квадратичный порядок локальной аппроксимации границы множества позволяет использовать соприкасающиеся эллипсоиды в качестве основы для построения алгоритмов с ньютоновской скоростью сходимости. Результатом, натолкнувшим па это предположение можно считать теорему о квадратичной скорости сходимости метода проектирования начального состояния на изохрону, изложенную в [4]. Вместе с тем, приведенный в работе результат получен другим путем и для несколько иного класса задач. Изначально в работе рассматривается постановка задачи, не ставящая во главу угла ее дифферепциальную специфику. Вместо этого используются геометрические соображения для рассматриваемых множеств и аналитические свойства их опорных функций, а уже потом полученные результаты применяются для решения задач оптимального управления. Такой взгляд на проблему можно признать родственным подходу, примененному С.П.Самсоновым в [15] и [16]. При доказательстве квадратичной скорости сходимости методов решения задачи быстродействия оказалась удобной параметризация начального значения сопряженной переменной, с небольшой особенностью отражающая суть подхода, предложенного в [9]. Использование идеи "одномерной оптимизации" привело к построению квадратично сходящегося метода, для которого не возникает проблемы выбора "достаточно" хорошего начального приближения. В качестве вспомогательного метода, а также в целях сравнительного анализа используется потенциал W(q), введенный в [17].

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

Сначала проводится исследование метода проектирования точки на множество в статическом случае; главным конструктивным элементом алгоритма решения этой задачи является соприкасающийся эллипсоид. Доказано, что при определенных предположениях можно гарантировать квадратичную скорость сходимости метода, [44]. Также проведено изучение вопроса о сходимости метода, теоретические и практические исследования для его модификаций, сравнение с имеющимися аналогами. Метод использован для решения задачи оптимального управления с терминальным функционалом. Построена его модификация, обладающая гарантированной сходимостью. Далее рассматривается задача быстродействия в геометрической интерпретации и алгоритм ее решения на основе проектирования точки на множество. Для этого метода сформулированы требования, гарантирующие сходимость, и получены условия, достаточные для ньютоновской скорости сходимости, [45], [46]. Следующая часть представляет собой конструктивный синтез результатов, полученных в работе ранее, - использование конструкции соприкасающегося эллипсоида для решения задачи быстродействия, [47]. Рассмотренный метод применяется для решения задачи оптимального управления, в качестве основы используется идея проектирования начального состояния на изохрону, подробно изложенная в [4], при этом дается ответ на вопрос о способе проектирования, который был оставлен открытым; дифференциальная интерпретация процесса проектирования (метод проектирования в непрерывной форме, изложенный, например, в [5]) при этом не используется. В заключительной части построена модификация метода, обладающая гарантированной сходимостью.

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

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

и включение G Не,- (5.41)

Из леммы 4.1, поскольку сейчас выполнены все ее условия, следует, что существуют положительные константы С2 и Сз и достаточно малое число £г3 > 0 такие, что для всех пар (t,p), удовлетворяющих условиям (t,p) G il£3 и р G £(t, 0), выполнено неравенство:

С2\Р - Р. |2 < 11 - U | < С3\р - р* |2. (5.42)

Положим число е4 = тт{е1,е2,ез}. На множестве Н£4 выполняется оценка (5.40) и включение (5.41), поэтому из (5.38), с учетом равенств (5.39), следует справедливость соотношений

9{t,q) =g(t*,p*) + g,t(k'(it)(t-t*) + 9'p(4><is) *(я~р*) = 0 + Ш, <fc)(£ - «*) + 6(1 q - р* I) = здесь момент времени = + (1 — и вектор = £q+ (1 + £)р,, для некоторого числа £ G [0,1]. Отсюда на основании оценки (5.42) и непрерывности функции $(•»•) в точке (£*,р*)> следует справедливость соотношений -Й(«{.9£) +о(1) = Р.) + «(!)•

Поэтому существует такое достаточно малое число ет, удовлетворяющее требованию 0 < е < £4, что для всех точек (i,p) 6 таких, что р е £(i,0), будет выполнятся неравенство 9 (U я) < 0. Лемма 5.4 доказана.

Замечание 5.7 Из леммы 5.4 следует, что при выполнении ее условий существует такое малое число 5 > 0, что в методе (4-1) для любых пар (tk,Pk), удовлетворяющих условию (tfc.Pfc) Е 11$, существует момент времени tk+\ € (£&,£*], определенный равенством <?(tfc+i,Pfc+i) = 0. Справедливость этого замечания следует из непрерывности функции д(',') по первому аргументу и следующих двух неравенств g{tk,Pk+i) < 0 м g(t*,Pk+i) > 0.

Список литературы диссертационного исследования кандидат физико-математических наук Хабаров, Николай Васильевич, 2003 год

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

2. Федоренко Р. П. Принцип максимума и приближенное решение вариационных задач // Международная конференция, посвященная девяностолетию со дня рождения Л.С.Понтрягина. 1998. Оптимальное управление и добавления. С. 270-278.

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

4. Киселев Ю.Н. Линейная теория быстродействия с возмущениями. I. М.: Издательство МГУ, 1986.

5. Аввакумов С.Н., Киселев Ю.Н., Орлов М.В. Методы решения задач оптимального управления на основе принципа максимума Понтрягина // Труды МИАН им. В.А. Стеклова. 1995. Т. 211. С. 3-31.

6. Орлов М.В. Численный метод решения линейной задачи быстродействия. -В сб.: Вопросы вычислительной математики и программного обеспечения ЭВМ. М.: Издательство МГУ, 1985.

7. Орлов М.В. Линейная задача быстродействия: численный алгоритм. Вестник Московского университета. Сер.15. Вычислительная математика и кибернетика, 1986.

8. Киселев Ю.Н. Приближение гладкого выпуклого компакта соприкасающимися эллипсоидами // Международная конференция по управлению "АВТОМАТИКА-2001". 2001. Т. 1. С. 31-32.

9. Киселев Ю.Н. Быстросходящиеся алгоритмы решения линейной задачи быстродействия // Кибернетика. 1990. N 6. С. 47-57.

10. Черноусъко Ф.П. Оценивание фазового состояния динамических систем. Метод эллипсоидов М.: Наука, 1988.

11. Kurzhanski А.В., Varaiya P. On ellipsoidal techniques for reachability analysis. Part I: External approximations // Optimization methods and software, v. 17, N 2, 2002.

12. Kurzhanski A.В., Varaiya P. On ellipsoidal techniques for reachability analysis. Part II: Internal approximations box valued constraints // Optimization methods and software, v. 17, N 2, 2002.

13. Погорелое А.В. Геометрия. M.: Наука, Главная редакция физ.-мат. литературы, 1983.

14. Погорелое А.В. Дифференциальная геометрия. 7-е издание. М.: Наука, 1979.

15. Самсонов С.П. Одна задача оптимального управления с различными функционалами качества // Труды МИАН им. В.А. Стеклова. 1988. Т. 185. С. 215-221.

16. Самсонов С. П. Численный метод решения линейной задачи оптимального управления с заданной точностью // Некоторые проблемы современной математики и их приложения к задачам математической физики. М.: МФТИ, 1985. С. 121-124.

17. Киселев Ю.Н., Шимохина О.Н. Алгоритмы минимизации квадратичного терминального функционала в дискретных линейных управляемых системах с гладкой областью управления // Техническая кибернетика (М.), 1993. N 4. С. 109-119.

18. Белолипецкий А.А. Численный метод решения линейной задачи оптимального быстродействия сведением ее к задаче Коши // ЖВММФ, 1977. N 6. С. 1380-1386.

19. Понтрягин JI.C. Избранные научные труды. Т. 2. М.: Наука, 1988.

20. Понтрягин JI.C. Обыкновенные дифференциальные уравнения М.: Наука, 1970.

21. Киселев Ю.Н. Оптимальное управление. М.: Издательство МГУ, 1988.

22. Аввакумов С.Н., Киселев Ю.Н. Решение систем нелинейных уравнений на основе ряда Чебыпгева // Сб. "Проблемы математической физики". Диалог-МГУ, Москва, 1998. С. 5-27.

23. Аввакумов С.Н. Гладкая аппроксимация выпуклых компактов // Труды Института Математики и Механики УрО РАН. Екатеринбург. 1996. Т.4. С. 184-200.

24. Киселев Ю.Н., Орлов М.В., Федотова E.JI. Проектирование точки на эллипсоид // Вест. Моск. ун-та. Сер. 15, ВМиК, 1993, N 1. С. 45-50.

25. Киселев Ю.Н. Проектирование точки на выпуклый компакт // Международная конференция по управлению "Автоматика-2001". 2001. Т. 1. С. 30-31.

26. Yu.N. Kiselev. Algorithms of projection of a point onto an ellipsoid // Lithuanian Math. Journal, Vol. 34, No 2. 1994, pp. 141-159.

27. Киселев Ю.Н., Орлов М.В. Методы решения нелинейной краевой задачи в линейной задаче быстродействия // Дифференциальные уравнения, 1995. N 11. С. 1843-1850.

28. Киселев Ю.Н., Орлов М.В. Метод потенциалов для линейной задачи быстродействия // Дифференциальные уравнения, 1996. N 11. С. 44-51.

29. Киселев Ю.Н., Орлов М.В. Численные методы линейных быстродействий // ЖВММФ, 1991. N 12. С. 1763-1771.

30. Киселев Ю.Н. Гладкие плоские выпуклые компакты. Лекция для студентов. 1999. МГУ, ВМиК (рук.)

31. Григоренко Н.Л., Киселев Ю.Н., Орлов М.В. Пакеты прикладных программ для решения прямых и обратных задач управления // Сб.: Компьютерные технологии в высшем образовании. М.: МГУ, 1994. С. 346-364.

32. Федоренко Р.П. Приближенные методы решения задач оптимального управления. -М.: Наука, 1978.

33. Благодатпских В.И. Линейная теория оптимального управления. М.: Издательство МГУ, 1978.

34. Благодатпских В.И. Введение в оптимальное управление (линейная теория). М.: Высшая школа, 2001.

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

36. Галеев Э.М., Тихомиров В.М. Оптимизация: теория, примеры, задачи. М.: Эдито-риал УРСС, 2000.

37. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. Начальный курс. М.: Изд-во МГУ, 1985.

38. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. Продолжение курса. М.: Изд-во МГУ, 1987.

39. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987.

40. Калиткин Н.Н. Численные методы. М.: Наука, 1978.

41. Федоров В.В. Численные методы максимина. М.: Наука, Гл. ред. физ.-мат. лит., 1979.

42. Хабаров Н.В. Алгоритмы проектирования точки на гладкий выпуклый компакт с квадратичной скоростью сходимости // Тезисы докладов ВЗМШ. 2001. С. 269-270.

43. Хабаров Н.В. Алгоритмы решения задач быстродействия с квадратичной скоростью сходимости // Тезисы докладов ВВМШ. 2001. С. 164-165.

44. Хабаров Н.В. Алгоритм решения задачи быстродействия па основе проектирования конечного состояния на множество достижимости J J Труды XXIV Конференции молодых ученых механико-математического факультета МГУ им. М.В.Ломоносова. 2002. С. 182-184.

45. Хабаров Н.В. Алгоритм решения задачи оптимального управления на основе соприкасающихся эллипсоидов // Материалы Воронежской весенней математической школы. 2002. С. 156-157.

46. Хабаров Н.В. Алгоритм проектирования точки на множество // Материалы Воронежской весенней математической школы. 2003. С. 145.

47. Киселев Ю.Н., Хабаров Н.В. Соприкасающиеся эллипсоиды в алгоритмах решения линейной задачи быстродействия // Материалы 10-й международной конференции по автоматическому управлению "Автоматика-2003". 2003. Т. 1. С. 49-50.

48. Хабаров Н.В. Метод решения линейной задачи оптимального управления с терминальным функционалом типа "норма разности" на основе соприкасающихся эллипсоидов // МГУ, М., 2003. - 67 с. - Рус. - Деп. в ВИНИТИ 20.10.2003, N 1832-В2003.

49. Хабаров Н.В. Метод решения линейной задачи быстродействия на основе соприкасающихся эллипсоидов // МГУ, М., 2003. - 66 с. - Рус. - Деп. в ВИНИТИ 20.10.2003, N 1834-В2003.