Введение к работе
Актуальность темы. Приближенные и вычислительные методы — обширная и ставшая самостоятельной область исследований и разработок в теории оптимального управления, нацеленных на эффективное решение практических задач. Основные исследования и разработки приближенных методов группируются главным образом вокруг численной реализации известных теоретических результатов: принципа максимума Понтрягина, метода динамического программирования Беллмана, принципа оптимальности Кротова и общей теории экстремума Милютина-Дубовицкого, их обобщений и аналогов для различных постановок, учитывающих разнообразные практические ситуации. Основы этой теории широко освещены в литературе (Р. Беллман; А. М. Летов; Л. С. Понтрягин, В. Г. Болтянский, Р. В. Гамкрелидзе, Е. Ф. Мищенко; В. Ф. Кротов; А. Я. Дубовицкий, А. А. Милютин; Н. Н. Красовский, А. И. Субботин; А. Б. Куржанский; Р. Габасов, Ф. М. Кириллова и др.).
Несмотря на то, что теоретические результаты учитывали особенности современных задач управления, главным образом, наличие разнообразных ограничений в дополнение к основным - дифференциальным - связям в вариационном исчислении, их прямое практическое использование оказалось весьма ограниченным сложностями реализации теоретических соотношений, описывающих искомое решение получаемых уравнений. Как правило, аналитическое решение можно было найти лишь в редких случаях, если не считать специально подобранных примеров. Это послужило причиной для разработки приближенных методов, позволяющих решать сложные практические задачи. За прошедший с момента их появления полувековой период было предложено множество разнообразных приближенных, численных методов, позволяющих искать оптимальное решение напрямую, минуя условия оптимальности, посредством операций улучшения управления, повторяемых в итерационной процедуре. При этом косвенно использовались как сами ос-
новополагающие результаты, так и принципы, лежащие в их основе.
Исторически развитие методов улучшения началось с методов первого порядка, известных как градиентные методы, одновременно с созданием современной теории оптимального управления. В числе основоположников отметим Р. Куранта, Л. В. Канторовича, Д. Е. Охоцимского и Т. М. Энеева, Л. И. Шатровского, Дж. Келли. Более сложные схемы требуются при наличии ограничений на переменные управления и состояния. Здесь можно отметить, например, работы Р. П. Федоренко и В. Г. Гюрджиева. Наряду с этим реализовались и другие методы, родственные градиентным, основанные на принципе максимума Понтрягина (И. А. Крылов, Ф. Л. Черноусько; О. В. Васильев, А. И. Тятюшкин, А. В. Аргучинцев). Ряд интересных схем предложен Н. Н. Моисеевым. Для поиска управления в форме синтеза весьма эффективным оказался метод моментов (Н. Н. Красовский; Р. Габасов, Ф. М. Кириллова).
Методы первого порядка демонстрируют, как правило, высокую эффективность на первых итерациях и ее резкое снижение в окрестности оптимума. Это заставило обратиться к более сложным схемам построения алгоритмов и разработке методов второго порядка (Д. X. Джекобсон; В. Ф. Кротов, И. Н. Фельдман; Р. Анрион). Одно из направлений в этой области базируется на достаточных условиях оптимальности В. Ф. Кротова1'2 и его последователей: В. И. Гурмана3, М. М. Хрусталева, А. И. Москаленко. В работах
A. И. Москаленко были предложены теоремы о совместной оптимальности,
которые имеют отношение, с одной стороны, к теории достаточных условий
B. Ф. Кротова, а с другой — к методу вектор-функций Ляпунова, разрабаты-
вашемуся В. М. Матросовым и его учениками (Л. Ю. Анапольский, С. Н. Ва
сильев).
хКротов В. Ф., Гурман В. И. Методы и задачи оптимального управления. — М.: Наука, 1973.
2Krotov V. F. Global methods in optimal control. — N.Y.: Marcel Dekker, 1996.
3Гурман В. И. Принцип расширения в задачах управления. — М.: Физматлит, 1985, 1997.
Ряд конкретных методов как для непрерывных, так и для дискретных систем приведен в работах В. И. Гурмана, В. А. Батурина, И. В. Расиной, Е. В. Данилиной, В. Ф. Кротова, И. Н. Фельдмана. Их спецификой является априорно приближенный подход, возможность оценивания получаемых приближенных решений и использование характерного свойства вырожденности прикладных задач и соответствующих специальных методов для поиска начальных приближений, что, как известно, является критическим моментом при использовании итерационных улучшающих алгоритмов. Родственные методы улучшения, называемые нелокальными, описаны в книге В. А. Срочко. Эти методы развиваются в работах А. С. Булдаева.
Широкий спектр методов и их приложения для решения практических задач представлены в работах В. А. Батурина, В. И. Гурмана, В. В. Токарева, В. А. Дыхты, А. В. Лотова, В. В. Салмина.
В настоящее время появляется все больше европейских работ, предлагающих применять теорию оптимального управления (а именно, метод глобального улучшения управления Кротова) к задачам управления различными квантовыми системами (S. Е. Sklarz, D. J. Tannor, С. P. Koch, J. P. Palao, R. Kosloff, I. I. Maximov, J. Salomon, G. Turinici, N. C. Nielsen, M. Murphy, S. Montangero, V. Giovanetti, T. Calarco). Было отмечено, что метод Кротова не испытывает особых трудностей на больших размерностях и позволяет решать задачи управления квантовыми системами с высокой точностью.
Современные сложные многомерные прикладные задачи (например, задачи управления квантовыми системами, социо-эколого-экономических системами, и т. п.) диктуют основные требования к методам решения задач управления: упрощающие преобразования модели объекта, эффективные методы поиска приближенно-оптимальных управнений с учетом больших размерностей и распараллеливание вычислений.
В диссертационной работе разработаны новые итерационные методы оптимизации управления на основе достаточных условий оптимальности, ори-
ентированные на параллельные вычисления. Для предварительного анализа и поиска эффективных начальных приближений исходной задачи рассматриваются различные расширяющие, аппроксимирующие и сужающие преобразования модели объекта, направленные на упрощение исходной задачи.
Как показывают вычислительные эксперименты, выполненные на суперкомпьютерах семейства «СКИФ», разработанные методы обладают высокой эффективностью и временной производительностью.
Цель и задачи исследования. Целью диссертационной работы является разработка эффективных методов поиска приближенных решений задач оптимального управления, ориентированных на параллельные вычисления, на основе известных ранее и новых преобразований модели объекта управления, достаточных условий оптимальности и глобальных оценок.
Для достижения указанной цели в работе поставлены и решены следующие задачи:
-
Разработать теоретические основы и конструктивные методы упрощающих преобразований модели объекта, которые позволяют заменить исходную задачу семейством более простых задач (в смысле дальнейшего поиска приближенного решения) и тем самым составляют основу методики исследования.
-
Реализовать конструктивно минимаксный принцип Кротова улучшения управления как основу эффективных итерационных методов оптимизации управления.
-
Разработать на основе указанных подходов серию методов и алгоритмов приближенного поиска оптимального управления, ориентированных на параллельные вычисления с соответствующим программным обеспечением.
4. Применить разработанные методы для решения прикладных задач
управления из различных областей, в том числе с применением суперЭВМ.
Методы исследования. Исследования, выполненные в работе, базиру-
ются на достаточных условиях оптимальности и глобальных оценках, принципах расширения и локализации. При алгоритмической и программной реализации использовались различные численные методы аппроксимации функций многих переменных, решения дифференциальных уравнений, нелинейного программирования. При написании компьютерных программ использовался язык программирования C++, при написании параллельных версий программ использовалась Т-система с открытой архитектурой (OpenTS).
Научная новизна результатов. Все основные результаты диссертации являются новыми. Среди них ниболее важные:
конструктивные методы упрощающих преобразований множества управлений динамической системы как модели объекта посредством расширения, аппроксимации и сужения;
общая схема приближенного решения задач оптимального управления с использованием указанных и известных ранее преобразований в пространстве состояний, включающая глобальный поиск начального приближения, итерационные процедуры его улучшения и оценки;
-новые методы глобального улучшения управления в составе итерационных процедур на основе минимаксного принципа Кротова, ориентированные на параллельные вычисления.
Теоретическая и практическая ценность результатов, полученных в диссертации, заключается в разработке:
методики приближенного решения задач управления на базе преобразований модели объекта, позволяющей создать гибкое математическое и программное обеспечение, легко адаптируемое к решению конкретных практических задач;
итерационных процедур, использующих методы глобального улучшения управления, являющихся составной частью общей схемы поиска приближенного решения;
- алгоритмического и программного обеспечения для решения задач
управления, позволяющего реализовать предлагаемый подход к поиску приближенных решений в среде параллельных вычислений и тем самым повысить его эффективность при решении различных прикладных задач.
Результаты диссертационной работы используются в Исследовательском центре системного анализа Института программных систем имени А.К. Ай-ламазяна РАН и в лаборатории математических методов исследования оптимальных управляемых систем Института проблем управления имени В.А. Трапезникова РАН, а также нашли применение при выполнении ряда крупных программ и проектов РФФИ и РГНФ.
Положения, выносимые на защиту:
-
Исследование и конструктивное представление класса преобразований динамической системы как модели объекта управления на основе расширения множества управлений. Общая схема приближенного исследования задач оптимального управления с использованием этого класса, известных преобразований в пространстве состояний, достаточных условий оптимальности Кротова и глобальных оценок.
-
Реализация минимаксного принципа глобального улучшения управления посредством задачи Коши для линейного уравнения в частных производных относительно разрешающей функции Кротова и его дискретного аналога для построения эффективных итерационных процедур.
-
Серия новых методов и алгоритмов приближенного решения задач оптимального управления, как для систем общего вида, так и для важных частных случаев на основе предложенных общих подходов с применением принципа локализации.
-
Решения разработанными методами ряда прикладных задач, демонстрирующие эффективность предложенного инструментария.
Связь исследований с научными программами. Исследования проводились в рамках:
- научных грантов № 06-01-00330-а (Реализация обобщенных решений за
дач управления), 08-01-00274-а (Приближенные методы оптимизации управ
ления на основе аппроксимаций модели объекта), 09-01-170-а (Вырожден
ные задачи оптимального управления), 11-01-90717-моб-ст (Научная работа
Трушковой Е. А. из ИПС им. А.К. Айламазяна РАН в ИПУ им. В.А. Тра
пезникова РАН. «Глобальные алгоритмы улучшения для динамических си
стем с управлением»), 12-01-00256-а (Исследования импульсных и гибридных
управляемых систем на основе дискретно-непрерывных моделей) Российско
го фонда фундаментальных исследований;
научно-технической программы Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоемких компьютерных технологий на базе мультипроцессорных вычислительных систем» (шифр «ТРИАДА») по проекту ПР6: «Исследование проблемы эффективной синхронизации параллельных процессов при имитационном дискретном моделировании больших технических и социально-экономических систем, разработка основ создания параллельных интеллектуальных имитационных комплексов для работы в составе ситуационных центров поддержки принятия решений» , подпроект: «Разработка программного комплекса улучшения и оптимизации законов управления для приложений в различных областях» ;
в научно-технической программе Союзного государства «Разработка и использование программно-аппаратных средств Грид-технологий перспективных высокопроизводительных (суперкомпьютерных) вычислительных систем семейства СКИФ» (шифр «СКИФ-ГРИД») по проекту «Многовариантные расчеты стратегии устойчивого развития Байкальского региона с применением ПК ISCON на суперЭВМ СКИФ»;
в научной программе № 14 ОЭММПУ РАН «Анализ и оптимизация функционирования систем многоуровневого, интеллектуального и сетевого управления в условиях неопределенности» по проекту 1.6: «Методы опти-
мизации управления динамическими системами, описываемыми линейными уравнениями с управляемыми коэффициентами. Синтез управления в нелинейных системах. Приложения к моделям оптимального управления квантовыми системами».
Степень достоверности и апробация работы. Достоверность полученных результатов подтверждена доказательствами соответствующих теорем и содержательными примерами вычислений для различных прикладных задач.
Результаты диссертации неоднократно докладывались и обсуждались на научных семинарах ИПС им. А.К. Айламазяна РАН и ИПУ РАН, на семинаре «Квантовые компьютеры и квантовые вычисления» Физико-технологического института РАН, а также на различных научных симпозиумах и конференциях: XV Международной конференции по механике и современным прикладным программным системам (ВМСППС'2007), 25-31 мая 2007 г., Алушта; IV Международном симпозиуме «Обобщенные решения в задачах управления» (GSCP-08), Бурятия, г. Улан-Удэ, 23-28 июня 2008 г.; Третьей всероссийской научно-практической конференции «Имитационное моделирование. Теория и практика», 17-19.10.2007, Санкт-Петербург; IV международной конференции «Параллельные вычисления и задачи управления» (РАСО-2008), Москва, октябрь 2008 г.; Международной конференции «Программные системы: теория и приложения». ИПС РАН, Переславль-Залесский, 2009; XVI Международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС'2009), 25-31 мая 2009 г., Алушта; Первой традиционной всероссийской молодежной летней школе «Управление, информация и оптимизация», Переславль, 2009; Молодежном симпозиуме с международным участием: «Теория управления: новые методы и приложения», ИПС РАН, Переславль-Залесский, 22-26 сентября 2009 г.; Международной научной конференции «Параллельные вычис-
лительные технологии'2010», Уфа, 2010 г.; Третьей Международной научной конференции «Суперкомпьютерные системы и их применение» (SSA'2010), 25-27 мая 2010 года, Минск; Третьей международной конференции «Математическое моделирование социальной и экономической динамики» (MMSED-2010), 23-25 июня 2010 г., Москва; III международной конференции «Ин-фокоммуникационные и вычислительные технологии» (ИКВТС-2010), Улан-Удэ, 2010; V International Symposium «Generalized statements and solutions of control problems - 2010», Ulaanbaatar, Mongolia, 2010; Школе-семинаре «Приближенные методы оптимального управления в параллельных вычислениях», Переславль-Залесский, декабрь 2010; 16-ой Саратовской зимней школе «Современные проблемы теории функций и их приложения», Саратов, 27 февраля - 3 января 2012; VI Международном научном семинаре "Обобщенные постановки и решения задач управления"(С88СР-2012), Геленджик, сентябрь 2012; Sino-Russian International Workshop on Optimal Control and Computing, Shanghai, China, November, 2012.
Публикации. Результаты диссертационной работы отражены в 38 публикациях: 19 статей, в том числе 15 статей в изданиях из списка ВАК; 15 материалов международных и российских конференций; 1 свидетельство государственной регистрации программ для ЭВМ; 2 учебных пособия.
Структура и объем работы. Диссертационная работа состоит из введения, 6 глав основного материала, заключения, библиографического списка и содержит 229 страниц основного текста, 46 рисунков, 12 таблиц. Библиографический список включает 143 наименования литературы.
