Методы поиска и улучшения экстремальных процессов в невыпуклых задачах оптимального управления тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Розинова, Надежда Сергеевна

• Розинова, Надежда Сергеевна
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Розинова, Надежда Сергеевна

Введение

ГЛАВА 1. Основная задача. Методы линейно-квадратичной аппроксимации

1.1 Основная задача. Фазовая аппроксимация.

1.2 Метод фазовой линеаризации.

1.3 Метод квадратичной аппроксимации

1.3.1 Задача улучшения. Нелокальные методы.

1.3.2 Обоснование свойств улучшения.

1.3.3 Задача без ограничений на управление.

1.3.4 Численная реализация.

ГЛАВА 2. Задача на максимум нормы конечного состояния.

Условия оптимальности и методы улучшения

2.1 Постановка задачи. Экстремальные точки.

2.2 Условия оптимальности.

2.3 Улучшение экстремальных точек

2.4 Численная реализация.

2.5 Квадратичная вспомогательная задача.

ГЛАВА 3. Избранные задачи невыпуклой оптимизации.

Специализированные методы

3.1 Задача (І-оптимизации и овия глобального эремума

3.1.1 Необходимое условие оптимальности.

3.1.2 Достаточное условие оптимальности.

3.2 Задача на максимум евклидовой нормы.

3.2.1 Метод скорейшего подъема

3.2.2 Максимизация нормы на параллелепипеде.

3.2.3 Задача максимизации полунормы.

3.3 Билинейная система специального вида.

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

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

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

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

1) итерационные процедуры принципа максимума (ПМ) - локальные и нелокальные аппроксимации функционалов, вспомогательные задачи на максимум функции Понтрягина, разнообразные схемы игольчатого варьирования управлений, методы игольчатой и фазовой линеаризации, процедуры нелокального улучшения [25]-[28], [32], [41], [46], [53], [75], [89],[94],[95] ;

2) градиентные методы оптимального управления - классические и неклассические вариации функционалов, вспомогательные задачи на минимум вариаций, слабое варьирование управлений, квазиградиентные методы [29], [39], [75], [76], [90], [91], [114] ;

3) методы улучшения на основе достаточных условий оптимальности

- линейно-квадратичная реализация разрешающей функции, работа с дифференцируемой функцией Гамильтона и уравнением Риккати, варьирование управлений с помощью регуляризации основного функционала с целью обеспечения сильного и слабого улучшения [17], [38], [47], [113];

4) методы оптимального управления в режиме реального времени - опорные процедуры поиска программных решений, неклассическая технология решения проблемы оптимального синтеза [35], [36];

5) методы математического программирования в задачах оптимального управления - дискретные аппроксимации моделей оптимального управления, расчетные формулы для производных сложных функций по компонентам дискретного управления, адаптация методов конечномерной оптимизации к специфике дискретных задач, вопросы сходимости аппроксимаций [30], [42], [43], [54].

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

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

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

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

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

В первую очередь здесь закономерно выделяются методы и алгоритмы, связанные с необходимыми условиями оптимальности. Наиболее эффективным средством для построения вычислительных процедур служит принцип максимума Понтрягина [3], [11]-[15], [34], [45], [51]-[53], [55], [59], [60]. Первоисточником соответствующего класса методов являются, конечно, схемы последовательных приближений из [48], [49], которые наряду с результатом [112] заложили добротную основу конструктивного использования ПМ и стимулировали развитие методов игольчатого варьирования в задачах оптимального управления. Дальнейшие исследования в этом направлении привели к своеобразной технике варьирования управлений (в некоторой окрестности точки максимума по приращению функции Понтрягина, в области "максимальных"(выше среднего) значений определяющей функции, на специальных семействах множества варьирования и др.). В полуэвристическом плане указанные способы конструирования управлений были, по-видимому, впервые сформулированы в работах [25], [31], [32], [46], [87] и послужили активным стимулом совершенствования теории варьирования. В результате сформировался представительный цикл работ с доказательством сходимости последовательных приближений по определенным невязкам и со свойством монотонности по функционалу.

Основополагающий вклад в развитие методов ПМ внесли исследования Ф.Л. Черноусько и его учеников [48]-[50], [94], [95]. Например, можно подчеркнуть, что в известной монографии [95] приведено семь модификаций метода последовательных приближений для задачи оптимального управления со свободным правым концом, каждая из которых характеризуется тем или иным своеобразием.

Необходимо также выделить популярный вариант игольчатого варьирования, который был предложен О.В. Васильевым и связан с так называемым определяющим неравенством интегрального типа [24], [26], [118].

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

Наметим вычислительную схему метода для основной задачи оптимального управления

Ф(и) - (p(x(t\)) —» min, x = f(x,u,t), x(t0)=x°, u(t) eU, t eT =[tQ,ti];

• исходные данные u(t). x(t), ip(t), t ET;

• максимизирующее управление t) — arg max H(ip(t) ,x(t),v,t), vZÜ функция переключения g(t) = Н(ф(£), x{t),ü{t)A) - ЯОА(г), x(t), u(t), t) с крайними значениями

Ащіп = іпї{д(і), і є Т], А і тах 8ир{д(і): і є т};

• процедура варьирования и\(і) = и{і), ^(0 < А, Ці), д{і) > А;

• итерационный поиск параметра Л с ориентировкой на решение за

Следующую представительную группу методов численного решения составляют градиентные процедуры оптимального управления, имеющие в своей основе следствия ПМ (классические вариации функционалов, дифференциальный ПМ, условие стационарности гамильтониана) и использующие разноплановые варианты слабого варьирования управлений. Спектр задач, методов и технологий реализации в этой области необыкновенно широк, что образует богатую картину градиентного многообразия. На этом фоне выделим в качестве классических уже указанные монографии Р.П. Федоренко [91] и Ф.П. Васильева [30].

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

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

Цих) —> тіп, Л Є [Атіп, Атах].

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

- нестандартным элементом процедур варьирования является конструктивное использование специальных функций (вместо параметров), которые расширяют потенциал и повышают эффективность варьирования;

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

В качестве характерной иллюстрации отметим, например, процедуру смешанного варьирования, которая сочетает в себе участки слабого и игольчатого варьирования [77].

Образуется функция переключения с максимизирующим управлением й(£). Схема варьирования для Л > О представляется в виде и х)= I + д{1)< Л,

Ч' } \ Щ, д{1)> А;

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

Очередная группа методов численного решения классических задач в той или иной мере связана с конструкциями и соотношениями условий оптимальности в формате В.Ф. Кротова и В.И. Гурмана. В этой области методы строятся по принципу сильного и слабого улучшения в первом и втором порядке. При этом порядок метода определяется характером аппроксимации разрешающей функции (линейная аппроксимация определяет первый порядок, квадратичная аппроксимация - второй порядок). Существенным фактором для обеспечения свойства улучшения основного функционала является систематическое использование стандартной выпуклой комбинации основного и вспомогательного функционалов. Для решения краевой задачи ПМ такого сорта комбинации использованы, например, в [19]. Если в качестве вспомогательного функционала выбрать среднеквадратичное отклонение по управлению, то речь пойдет о слабом улучшении. В противном случае, если использовать среднеквадратичную невязку по фазовым траекториям, то приходим к процедурам сильного улучшения.

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

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

В первой главе диссертации для задач, линейных по управлению, этот подход реализуется по следующей схеме: классическая вариация функционала => фазовая линеаризация задачи => квадратичная аппроксимация.

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

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

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

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

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

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

Для d.с.-задач математического программирования необходимые и достаточные условия оптимальности и некоторые их реализации в форме стратегий глобального поиска разработаны и суммарно представлены в монографии A.C. Стрекаловского [81]. В терминологии соответствующих задач оптимального управления линейными системами эти результаты были сформулированы в [82], [83] и получили дальнейшее развитие в [84], [85].

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

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

Следующий существенный шаг на пути исследования задач выпуклой максимизации связан с получением достаточных условий оптимальности в форме неравенства для производной по направлению на пересечении поверхности уровня целевой функции и множества достижимости управляемой системы [80], [100], [108]. Эти результаты послужили основой для построения стратегий и алгоритмов глобального поиска ([81], [98], [99], [102], [103]), существенным элементом которых являются различные процедуры дискретизации экстремальной поверхности уровня с последующим перебором значений функции максимума с целью проверки условия оптимальности. В [9] рассмотрена аналогичная задача с невырожденной системой управления, порождающей строго выпуклое (полной размерности) множество достижимости.

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

Наконец, уместно отметить, что рассматриваемая задача выпуклой максимизации не является экзотичной и имеет свою историю и результаты, в первую очередь в рамках математического программирования (обзорное изложение см. в [81], [97], [102], [110]). По линии оптимального управления ее частный, но популярный вариант (на максимум евклидовой нормы) в аналитическом и вычислительном аспектах изучался, например, в [1], [2], [22], [33], [82], [88]. Задача имеет прикладное значение (отметим задачу о максимальном отклонении от программного движения вследствие возмущений [2]) и представляет теоретический интерес как характерный пример невыпуклой постановки, в которой принцип максимума Понтрягина не является достаточным условием оптимальности.

В третьей главе диссертации исследуются специальные задачи невыпуклой оптимизации, среди которых выделим задачу с с!.с.-целевой функцией квадратичного типа и задачу оптимального управления для одного класса билинейных систем. Задачи с1.с.-оптимизации имеют достаточно высокий уровень общности и образуют своеобразный класс невыпуклых структур [81], [107], [117]. Первая ступень исследования таких задач связана с выводом условий оптимальности, учитывающих специфику постановки и выделяющих множество экстремальных точек. Интересно отметить, что полученные в этой области результаты являются не только необходимыми, но и достаточными условиями глобальной оптимальности, что ранее было характерно только для выпуклых задач.

В разделе 3.1 рассматривается задача максимизации квадратичной с!.с.-функции на выпуклом компакте. Показывается, что стандартное условие оптимальности (полная линеаризация целевой функции) эквивалентно условию с частичной линеаризацией по первой из составляющих функций. Представлены две процедуры поиска экстремальных точек задачи. Расширение локального условия на все точки глобального максимума приводит к достаточному условию оптимальности, которое доказывается через редукцию к эквивалентной задаче выпуклой максимизации. В отличие от результата из [81] полученное условие не содержит параметра и формулируется в виде неравенства для производной целевой функции по направлениям в допустимых точках поверхности уровня.

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

В заключительной части третьей главы проведено решение задачи минимизации линейного терминального функционала на траекториях специальной билинейной системы х = Ах + иЪ(с,х). (0.1)

Билинейные системы вида (0.1) имеют немаловажное прикладное значение. Они описывают математические модели целого ряда процессов в биологии, экономике, медицине, энергетике, являются объектом исследования в теории автоматического управления (библиографию см. в [92], [93]). В частности, такие системы моделируют процесс лечения злокачественных опухолей (химиотерапия) путем задержки развития раковых клеток в определенной стадии [115], [116]. Ряд результатов качественного характера применительно к системе (0.1) (условия неотрицательности решений, свойства множества достижимости, оценка числа переключений экстремальных управлений) получен в [92], [93]. В разделе 3.3 выясняются условия, при которых принцип максимума становится достаточным условием оптимальности. Получены дополнительные условия типа линейной независимости определенной системы векторов, при которых оптимальное управление не содержит особых участков. В результате решение задачи проводится вполне элементарно, ценой однократного интегрирования фазовой системы (0.1) на релейном управлении сигнатурного типа.

Основные результаты диссертации опубликованы в работах [5]-[7], [61]-[74] и докладывались на следующих научных собраниях:

- III международной конференции по проблемам управления (Москва, 2006);

- III межвузовской зональной конференции «Математика и проблемы ее преподавания в вузе», посвященной памяти профессора Б.А. Бельтюко-ва (Иркутск, 2007);

- V Всесибирском конгрессе женщин-математиков (Красноярск, 2008);

- XIV Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (Иркутск-Северобайкальск, 2008);

- Международной конференции «Дифференциальные уравнения и топология», посвященная 100-летию со дня рождения Л.С. Понтрягина (Москва, 2008);

- Всероссийской конференции «Устойчивость и процессы управления», посвященной 80-летию со дня рождения В.И. Зубова (Санкт-Петербург, 2010);

- V Международном симпозиуме «Обобщенные постановки и решения задач управления» (Улан-Батор, 2010)

- XV Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (Иркутск, 2011).

Материалы диссертации неоднократно обсуждались на семинарах кафедры вычислительной математики и механики ИГУ и отделения методов управления ИДСТУ СО РАН.

Некоторые результаты диссертации получены в рамках научной работы по грантам РФФИ и включены в соответствующие отчеты (проекты 05-01-00187 и 08-01-00709).

В диссертации используется стандартная система обозначений и ссылок. Формулы имеют двойную нумерацию: номер главы и порядковый номер формулы в главе. Ссылки на литературу оформляются квадратными скобками. Список литературы приведен в алфавитном порядке.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Розинова, Надежда Сергеевна

Заключение

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

Основу исследования составляют два фактора:

• билинейные аппроксимации целевого функционала, порождающие вспомогательные задачи локального типа;

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

Сформулируем основные результаты диссертации, представляемые к защите.

1. Основная задача оптимального управления

• метод фазовой линеаризации с билинейной системой и со свойством улучшения управлений, не удовлетворяющих принципу максимума;

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

2. Задача на максимум нормы конечного состояния

• метод скорейшего подъема для функции максимума на эллипсоиде со сходимостью по невязке экстремальности;

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

3. Специальные задачи невыпуклой оптимизации

• критерий оптимальности в задаче на максимум квадратичной с1.с.-функции конечного состояния;

• метод решения задачи оптимизации для билинейной управляемой системы.

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

Список литературы диссертационного исследования кандидат физико-математических наук Розинова, Надежда Сергеевна, 2011 год

1. Александров В. В. О накоплении возмущений в линейных системах по двум координатам / В.В. Александров // Вестник МГУ. Сер Мат., мех. 1968. - № 3. - С. 67-76.

2. Александров В. В. Оптимальное управление движением / В.В. Александров, В.Г. Болтянский, С.С. Лемак и др. М.:Физматлит, 2005. - 376 с.

3. Алексеев В.М. Оптимальное управление / В.М. Алексеев, В.М. Тихомиров, C.B. Фомин. М.: Наука, 1979. - 429 с.

4. Антоник В. Г. Процедуры нелокального улучшения в невыпуклых задачах оптимального управления / В.Г. Антоник, А.Л. Ветрова // Оптимизация, управление, интеллект. 2002. - № 6. - С. 36-42.

5. Антоник В.Г. Методы билинейных аппроксимаций для решения задач оптимального управления / В.Г. Антоник, Н.С. Розинова, В.А. Срочко // Известия Иркутского государственного университета. Серия «Математика». 2011. - Т.4., №3. - С. 146-157.

6. Антоник В.Г. Вычислительное сравнение методов градиентного типа в задачах оптимального -управления / В.Г. Антоник, Н.В. Мамонова, В.А. Срочко // Известия Иркутского государственного университета. Серия «Математика». 2007. - Т.1, №1. - С.275-290.

7. Антоник В.Г. Метод нелокального улучшения экстремальных управлений в задаче на максимум нормы конечного состояния / В.Г. Антоник, В.А. Срочко // Журн. вычисл. матем. и матем. физ. 2009. -Т.49, № 5. - С.791-804.

8. Аргучинцев A.B. Оптимальное управление: нелокальные условия, вычислительные методы и вариационный принцип максимума / A.B. Аргучинцев, В.А. Дыхта, В.А. Срочко // Изв. вузов. Матем. 2009. -№1.-С. 3-43.

9. Арутюнов A.B. Условия экстремума. Анормальные и вырожденные задачи / A.B. Арутюнов. М.: Факториал, 1997. -256 с.

10. Арутюнов A.B. Принцип максимума Поптрягина. Доказательство и приложения / A.B. Арутюнов, Г.Г. Магарил-Ильяев, В.М. Тихомиров. М.: Факториал, 2006. - 144 с.

11. Арутюнов A.B. Необходимые условия оптимальности для дискретных задач оптимального управления / A.B. Арутюнов, Б. Марин-кович // Вестник МГУ, сер. ВМК. 2005. - № 1. - С. 43-48.

12. Афанасьев А.П. Необходимое условие в оптимальном управлении / А.П. Афанасьев, В.В. Дикусар, A.A. Милютин, С.А. Чуканов. -М.: Наука, 1990. 319 с.

13. Ащепков JI.T. Лекции по оптимальному управлению: Учеб. пособие / JI.T. Ащепков. Владивосток: Изд-во Дальневосточного у-н-та, 1996. - 208 с.

14. Балашевич Н. В. Численные методы программной и позиционной оптимизации линейных систем управления / Н. В. Балашевич, Р. Габасов, Ф. М. Кириллова // Журн. вычисл. матем. и матем. фйз. -2000. Т. 40, Л* 6. - С. 838-859.

15. Батурин В. А. Приближенные методы оптимального управления, основанные на принципе расширения / В. А. Батурин, Д. Е. Урба-нович. Новосибирск: Наука, 1997. - 175 с.

16. Батурин В.А. Приближенные методы решения задач оптимального управления на основе достаточных условий оптимальности В. Ф.

17. Кротова / В.А. Батурин // Тр. XI межд. Четаевской конф. «Аналитическая механ., устойчивость и управление движением» посвященной 105-летию Н.Г. Четаева. Т.З. Управление и оптимизация. Иркутск, 2007. -С. 30-47.

18. Болдырев В.И. Численное решение задачи оптимального управления / В.И. Болдырев // Изв. РАН. Теория и системы управления. -2000. № 3. - С. 85-92.

19. Брусникина Н.Б. Расчет опорной функции множества достижимости линейной управляемой системы с гарантированной оценкой погрешности / Н.Б. Брусникина // Вестн. МГУ. Сер. Вычисл. матем. и кибернетика. 2006. - № 1. - С. 42-48.

20. Брусникина Н.Б. Аппроксимация с гарантированной точностью множеств достижимости для линейной динамической системы, подверженной импульсным воздействиям / Н.Б. Брусникина, A.B. Лотов // Ж. вычисл. матем. и матем. физ. 2007. - Т.47, № 11. ^ С. 1855-1864.

21. Булатов В. П. Методы погружения в задачах оптимизации /

22. B.П. Булатов. Новосибирск: Наука. - 1977. - 160 с.

23. Булдаев A.C. Методы возмущений в задачах улучшения и оптимизации управляемых систем / A.C. Булдаев. — Улан-Удэ: Изд-во Бурятского государственного университета. 2008. — 260 с.

24. Васильев О.В. Одно замечание к алгоритму последовательных приближений, основанному на принципе максимума / О.В. Васильев // Дифференц. и интегральные уравнения. Иркутск, 1980. - С. 167-178.

25. Васильев О.В. Об одном методе решения задач оптимального уравнения, основанном на принципе максимума / О.В. Васильев, А.И. Тятюшкин // Жури, вычисл. матем. и матем. физ. 1981. - Т.21, №6.1. C.1376-1384.

26. Васильев О. В. Лекции по методам оптимизации / О.В. Васильев. Иркутск: Изд-во ИГУ, 1994. - 344 с.

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

28. Васильев Ф.П. Методы оптимизации / Ф.П. Васильев. М.: Факториал Пресс, 2002. - 824с.

29. Величенко В.В. Численный метод решения задач оптимального управления / В.В. Величенко // Журн. вычисл. матем. и матем. физ. -1966. Т.6, т. - С.635-647.

30. Габасов Р. Качественная теория оптимальных процессов / Р. Габасов, Ф.М. Кириллова. М.: Наука, 1971. - 508 с.

31. Габасов Р. Оптимизация линейных систем / Р. Габасов, Ф.М. Кириллова. Минск: Изд-во Белорус, ун-та, 1973. - 146 с.

32. Габасов Р. Принцип максимума в теории оптимального управления / Р. Габасов, Ф.М. Кириллова. Минск: Наука и техника, 1974. -272 с.

33. Габасов Р. Конструктивные методы оптимизации. 4.2. Задачи управления / Р. Габасов, Ф.М. Кириллова. Минск: Изд-во "Университетское", 1984. - 207 с.

34. Габасов Р. Оптимальное управление в режиме реального времени / Р. Габасов, Ф.М. Кириллова // Вторая межд. конф. по проблемам управления: Пленарн. докл. М.: Институт проблем управления, 2003. - С.20-47.

35. Груздева T.B. Локальный поиск в задачах с невыпуклыми ограничениями / Т.В. Груздева, A.C. Стрекаловский // Ж. вычисл. матем. и матем. физ. - 2007. - Т. 47, № 3. - С. 397-413.

36. Гурман В.И. Принцип расширения в задачах управления / В.И. Гурман М.: Наука, 1997. - 288 с.

37. Демьянов В.Ф. Приблиэюенные методы решения экстремальных задач / В.Ф. Демьянов, A.M. Рубинов. JL: Изд-во ЛГУ, 1968. -180 с.

38. Демьянов В. Ф. Введение в минимакс / В. Ф. Демьянов, В. Н. Малоземов. М.: Наука, 1972. - 368 с.

39. Дикусар В.В. Качественные и численные методы в принципе максимума / В.В. Дикусар, А. А. Милютин. М.: Наука, 1989. - 144 с.

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

41. Ермольев Ю.М. Конечно-разностный метод в задачах оптимального управления / Ю.М. Ермольев, В.П. Гуленко, Т.Н. Царенко. Киев: Наук, думка, 1978. - 164 с.

42. Измаилов А.Ф. Численные методы оптимизации / А.Ф. Измаилов, М.В. Солодов. М.:Физматлит, 2005. - 304 с.

43. Иоффе А.Д. Теория экстремальных задач / А.Д. Иоффе, В.М. Тихомиров. М.: Наука, 1974. - 480 с.

44. Кирин Н.Е. Вычислительные методы теории оптимального управления / Н.Е. Кирин. Л.: Изд-во ЛГУ, 1968. - 144 с.

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

46. Крылов И. А. О методе последовательных приближений для решения задач оптимального управления / И. А. Крылов, Ф. Л. Черно-усько // Журн. вычисл. матем. и матем. физ. 1962. - Т.2, № 6. - С. 1132-1139.

47. Крылов И. А. Алгоритм метода последовательных приближений для задач оптимального управления / И. А. Крылов, Ф. Л. Чер-ноусько // Журн. вычисл. матем. и матем. физ. 1972. - Т. 12, № 1. -С.14-34.

48. Любушин A.A. Метод последовательных приближений для расчета оптимального управления / A.A. Любушин, Ф.Л. Черноусько // Изв. АН СССР. Техн. кибернетика. 1983. - №2. - С.147-159.

49. Матвеев A.C. Оптимальные системы управления: Обыкновенные дифференциальные уравнения. Специальные задачи: Учеб. пособие / A.C. Матвеев, В.А. Якубович. СПб.: Изд-во С.-Петербург, ун-та, 2003. - 540 с.

50. Милютин A.A. Принцип максимума в общей задаче оптимального управления / A.A. Милютин. М.: Физматлит, 2001. - 304 с.

51. Милютин A.A. Оптимальное управление в линейных системах / A.A. Милютин, А.Е. Илютович, Н.П. Осмоловский, C.B. Чуканов. -М.: Наука, 1993. 268 с.

52. Моисеев H.H. Элементы теории оптимальных систем / H.H. Моисеев М.: Наука, 1975. - 528 с.

53. Никольский М.С. О достаточности принципа максимума Понтрягина в некоторых оптимизационных задачах / М.С. Никольский // Вестник Моск. Ун-та. сер.15. Вычисл.матем. и киберн. 2005. -№ 1. - С. 35-43.

54. Овсеевич A.M. Явные формулы для эллипсоидов, аппроксимирующих области достижимости / A.M. Овсеевич, Ю.В. Тарабанько // Изв. РАН. Теория и системы управления. 2007. - № 2. - С. 33-44.

55. Овсянников Д.А. Моделирование и оптимизация динамики пучков заряженных частиц / Д.А. Овсянников. — Л.: Изд-во ЛГУ, 1990. — 312 с.

56. Овсянников Д.А. Моделирование интенсивных пучков заряженных частиц / Д.А. Овсянников, О.И. Дривотин. СПб.: Изд-во СПбГУ, 2003.- 174 с.

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

58. Понтрягин Л.С. Принцип максимума / Л.С. Понтрягин. М.: Фонд матем. образования и просвещения, 1998. - 70 с.

59. Розинова (Ахмеджанова) Н.С. Исследование специального класса задач оптимального управления / Н.С. Розинова (Ахмеджанова) // Вестник Иркутского университета. Специальный выпуск. Иркутск: Ир-кут. ун-т, 2005. - С. 96-97.

60. Розинова (Ахмеджанова) Н.С. Решение задач оптимального управления на основе билинейной аппроксимации / Н.С. Розинова (Ахмеджанова) // Вестник Иркутского университета. Специальный выпуск. Иркутск: Иркут. ун-т, 2006. - С. 88-89.

61. Розинова (Ахмеджанова) Н.С. Применение локальных аппроксимаций для решения задач оптимального управления / Н.С. Розинова

62. Ахмеджанова) // V Всесибирский конгресс женщин-математиков. Материалы конференции. Красноярск, 2008. - с.31-35.

63. Розинова (Ахмеджанова) Н.С. К решению задачи па максимум нормы терминального состояния линейной управляемой системы / Н.С. Розинова (Ахмеджанова), С.Н. Ушакова // Известия вузов. Математика. 2009. - № 10. - С.63-67.

64. Розинова Н.С. Условия оптимальности в задаче максимизации разности двух выпуклых функций / Н.С. Розинова // Известия вузов. Математика. 2010. - № 10. - С.87-91.

65. Розинова Н.С. Условие оптимальности и метод поиска экстремальных точек в задаче на максимум эллипсоидальной нормы / Н.С. Розинова, В.А. Срочко // Известия Иркутского государственного университета. Серия "Математика". 2010. - Т.З - №3. - С. 93-104.

66. Розинова Н.С. Некоторые вопросы поиска экстремальных процессов в невыпуклых задачах оптимального управления / Н.С. Розинова, В.А. Срочко // Автоматика и телемеханика. 2011. - № 6. - С. 140-150.

67. Срочко В. А. Итерационные методы решения задач оптимального управления j В.А. Срочко. М.: Физматлит, 2000. - 160 с.

68. Срочко В. А. Квазиградиентпые методы решения задач оптимального управления / В.А. Срочко // Труды Института математики HAH Беларуси. Минск, 2001. - Т.7. - С. 132-141.

69. Срочко В. А. Модернизаг^ия методов градиентного типа в задачах оптимального управления / В.А. Срочко // Изв. вузов. Математика. 2002. - №12. - С.66-78.

70. Срочко В.А. Метод полной квадратичной аппроксимации в задачах оптимального управления / В.А. Срочко, С.Н. Ушакова // Известия вузов. Математика. 2004. - № 1. - С. 87-93.

71. Срочко В.А. Метод билинеаризации для решения задач оптимизации программных управлений / В.А. Срочко, С.Н. Ушакова // Изв. вузов. Математика. 2005. - № 12. - С. 63-69.

72. Стрекаловский А. С. О невыпуклых задачах оптимального управления / A.C. Стрекаловский // Вестн. МГУ. Сер. 15. Вычисл. ма-тем. и кибернетика. 1993. - № 1. - С. 9-13.

73. Стрекаловский А. С. Элементы невыпуклой оптимизации / A.C. Стрекаловский. Новосибирск: Наука, 2003. - 356 с.

74. Стрекаловский А. С. Глобальный поиск в невыпуклой задаче оптимального управления / A.C. Стрекаловский, Е. В. Шаранхаева // Журн. вычисл. матем. и матем. физ. 2005. - Т. 45, № 10. - С. 17851800.

75. Стрекаловский А. С. Задачи оптимального управления с терминальными функционалами, представленными в виде разности двух выпуклых функций / A.C. Стрекаловский // Журн. вычисл. матем. и матем. физ. 2007. - Т. 47, № 11. - С. 1865-1879.

76. Стрекаловский A.C. К решению невыпуклых задач оптимального управления с терминальным целевым функционалом / A.C. Стрекаловский, М.В. Янулевич // Вычислительные методы и программирование. 2010. - Т.Н. - С. 269-280.

77. Сухарев А.Г. Курс методов оптимизации / А.Г. Сухарев, A.B. Тимохов, В.В. Федоров. М.: Наука, 1986.

78. Тарасенко Н.В. Один метод решения задачи оптимального управления на основе интегрального принципа максимума / Н.В. Тарасенко // Дискретные и распределенные системы. Иркутск. - 1981. -С.142-150.

79. Ткачев А. М. Геометрический метод решения задачи максимизации нормы вектора состояния системы на конечном интервале управления / А. М. Ткачев // Прикладная математика и механика -1990. Т. 54, вып. 6. - С. 1036-1039.

80. Тятюшкин А.И. Численные методы и программные средства оптимизации управляемых систем / А.И. Тятюшкин. Новосибирск: Наука, 1992. - 193 с.

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

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

83. Хайлов E.H. О решении задачи оптимального управления с терминальным функционалом для однородной билинейной системы / E.H. Хайлов // Вестник МГУ, сер. 15. 1998. - №1. - С. 26-30.

84. Хайлов Е.Н. Об экстремальных управлениях однородной билинейной системы, управляемой в полоэ/сителъиом ортанте / Е.Н. Хайлов // Труды математического института РАН. 1998. - Т.220. - С. 217-235.

85. Черноусько Ф. JI. Вариационные задачи механики и управления (Численные методы) / Ф.Л. Черноусько, Н. В. Баничук. М.: Наука, 1973. - 238 с.

86. Черноусько Ф.Л. Оценивание фазового состояния динамических систем. Метод эллипсоидов / Ф.Л. Черноусько. М.: Наука, 1988. - 320 с.

87. Aganovich Z. The successive approximation procedure for finite-time optimal control of bilinear systems / Z. Aganovich, Z. Gajic // IEEE Transactions on Automatic Control. 1994. - Vol. 39. - № 9. - P. 1932-1935.

88. Benson H.P. Concave minimization: theory, applications and algorithms / H.P. Benson. // Horst, R. and Pardalos, P.M. (eds.), Handbook of Global Optimization, Kluwer, Dordrecht, 1995. P. 43-148.

89. Chinchuluun A. Global minimization algorithms for concave quadratic programming problems / A. Chinchuluun, R. Enkhbat, P.M. Pardalos // Optimization. 2005. - Vol. 54. - N6. - P.627-639.

90. Chinchuluun A. A novel approach for nonconvex optimal control problems / A. Chinchuluun, R. Enkhbat, P.M. Pardalos // Optimization. - 2009. - Vol. 58. - N7. - P.781-789.

91. Clarke F.H. On Global Optimality Conditions for Nonlinear Optimal Control Problems / F.H. Clarke, J.B. Hiriart-Urruty, Yu.S. Ledyaev // J. of Global Optimization. 1998. - V. 13. - Issue 2. - P. 109-122.

92. Dorroh J.R. A multistate, multicontrol problem with unbounded controls / J.R. Dorroh, G. Ferreyra // SIAM J.Contr. and Optim. 1999. -Vol. 32. - № 5. - P. 1322-1331.

93. Enkhbat R. On Some Theory, Methods and Algorithms for Concave Programming / R. Enkhbat // Optimization and Optimal Control. World Scientific Publishing Co. 2003. - P. 79-102.

94. Enkhbat R. A Numerical Approach for Solving Some Convex Maximization Problems / R. Enkhbat, B. Barsbold, M. Kamada // J. of Global Optimization. 2006. - Vol. 35. - R85-101.

95. Fortin D. Piece adding technique for convex maximization problems / D. Fortin, I. Tseveendorj // Journal of Global Optimization, 2010. Vol. 48. - № 4. - P. 583-593.

96. Fortin D. Piecewise Convex Maximization Problems: Piece Adding Technique / D. Fortin, I. Tseveendorj // J. Optimization Theory and Applications., 2011. Vol. 148. - № 3. - P. 471-487.

97. Fukushima M. A Second-Order Algorithm for Continuous-Time Nonlinear Optimal Control Problems / M. Fukushima, Y. Yamamoto // IEEE. Trans. Automat. Contr. 1986. - Vol.31. - №7. - P.673-676.

98. Hiriart-Urruty J.B. Conditions for global optimality / J.B. Hiriart-Urruty // Handbook of global optimization. Edited by Horst R., Pandalos P.M. Kluwer Academic Publishers, 1995. Vol.2. - P. 1-26.

99. Hiriart-Urruty J.B. A note on the characterization of the global maxima of a (tangentially) convex function over a convex set / J.B. Hiriart-Urruty, Y.S. Ledyaev // J. Convex Anal., 1996. Vol.3. - № 1. - P. 55-61.

100. Hofer E.P. An iterative method for the finite-time bilinear-quadratic control problem / E.P. Hofer, B. Tibken // Journ. Optimiz. Theory and Applications. 1988. - Vol. 57. - № 3. - P. 411-426.

101. Horst, R. Introduction to Global Optimization. Vol. 3 of Nonconvex Optimization and its Applications / R. Horst, P.M. Pardalos, N.V. Thoai. -Kluwer Academic, Dordrecht. 1995. - 318 p.

102. Jones D.I. Comparison of optimization algorithms / D.I. Jones, J.W. Finch // Intern. Journal of Control. 1984. - Vol. 40. - № 4. - P. 747-761.

103. Kelly H.J. Successive approximation techniques for trajectory optimization j H.J. Kelly, R.E. Kopp, H.G. Moyer // Proc. Symp. on vehicle system optimization. New York. - 1961. - P.360-391.

104. Krotov V.F. Global methods in optimal control theory / V.F. Krotov. New York: Marrcel Dekker, 1996. - 408 p.

105. Pytlak R. Numerical methods for optimal control problems with state constraints / R. Pytlak // Lecture Notes in Mathematics. Springer-Verlag. 1999. - № 1707.

106. Swierniak A. Cell Cycle as an Object of Control / A. Swierniak // Journal of Biological Systems, 1995. Vol.3. - №1. - P. 41-54.

107. Swierniak A. Some Control Problems for Simplest Differential Models of Proliferation Cycle / A. Swierniak // Applied Math, and Computer Science, 1994. Vol. 4. - №2. - P. 223-232.

108. Tuy H. D.C. optimization: theory, methods and algorithms / H. Tuy // Handbook of global optimization. Edited by Horst R., Pardalos P.M. Kluwer Academic Publishers, 1995. Vol.2. - P. 149-216.

109. Vasiliev O.V. Optimization methods / O.V. Vasiliev. Atlanta: World Federation Publishers Company Inc., 1996. - 276 p.