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

Введение к работе

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

Выбор исследуемого класса задач объясняется его практической значимостью и вместе с тем во многом мотивирован достижениями классической линейно-квадратичной теории оптимального управления. Специализация этой теории, основы которой были заложены Р.Калманом, Н.Н.Красовским и А.М.Летовым (а в части, касающейся стохастических объектов, А.Н.Колмогоровым, Н.Винером, Е.Хопфом), — задачи оптимального управления, сводящиеся к минимизации выпуклого квадратичного функционала на аффинном пространстве. Значительный вклад в ее развитие внесли Б.Андерсон, Я.К.Виллемс, В.И.Зубов, В.М.Кунцевич, А.Б.Куржанский, Ж.Л.Лионе, А.И.Лурье, А.А.Красов-ский, В.А.Якубович и многие другие ученые. В настоящее время эта теория охватывает широкий спектр разнообразных задач. Они связаны с системами, описываемыми уравнениями разных типов: обыкновенными дифференциальными, интегро-дифференциальными, в частных производных и др. Благодаря специфике линейно-квадратичного случая для многих линейно-квадратичных задач удалось построить исчерпывающую теорию и разработать эффективные методы решения.

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

х — Ах + Ви₇ 0 < t < со, л:(0) = а, (1.1)

|х(-)І + К)|ЄІ₂(0,+со), 01 < 0,...,0 < 0, <5o-*min. (1.2)

Здесь х = x(t) Є К" — состояние, и = v(t) Є R^m — управление, А к В — вещественные матрицы, 5, := f^Gi[x(t),u(t)]dt — 7і, Gi(x,u) — квадратичная форма от х,и, числа 7ь ,?* ^и вектор а Є К" заданы, 7о = 0. Допустимым считаем любое измеримое управление и(-) : [О.оо) —* R^m, удовлетворяющее включению и неравенствам из (1.2). (В (1.2) х(-) определено по «() из (1.1).) Задача состоит в том, чтобы найти допустимое

управление и(-) из условия 0о —* niin. Особенность этой задачи — присутствие (вообще говоря, невыпуклых) ограничений 01 < 0,..., 01 < 0; отбрасывая их, получаем одну из задач, всесторонне изученных в классической линейно-квадратичной теории оптимального управления.

Квадратичные ограничения дают возможность ставить задачу более естественно и часто отражают существо проблемы. Вместе с тем теория соответствующих задач, сравнимая по эффективности предлагаемых ею методов решения с классической линейно-квадратичной теорией, долгое время отсутствовала. Это не случайно, так как внесение в постановку задачи квадратичных ограничений принципиально усложняет ситуацию. Усложнение объясняется, в частности, тем, что в результате возникает, вообще говоря, невыпуклая задача глобальной оптимизации. В общем случае такие задачи, как правило, с трудом поддаются решению. Соответствующим проблемам в последнее время уделяется много внимания. Отметим вместе с тем, что известные методы невыпуклой глобальной оптимизации в основной массе являются численными, часто основаны на эвристических идеях и не всегда сопровождаются гарантией сходимости. Более того, известно, что проблема построения универсального сходящегося метода невыпуклой глобальной оптимизации в определенном смысле неразрешима в принципе [1].

Вместе с тем в 1990х годах появились работы В.А.Якубовича ([2,3] и др.), продемонстрировавшие, что для некоторых невыпуклых линейно-квадратичных задач оптимального управления с квадратичными ограничениями соответствующие проблемы просто и изящно преодолеваются. Более того, в этих работах был предложен общий подход, позволяющий строить эффективные алгоритмы решения упомянутых задач на базе методов классической линейно-квадратичной теории оптимального управления. Эти алгоритмы основаны на математической теории, являются в наиболее существенной части аналитическими и гарантированно приводят к нахождению глобального оптимума.

Предложенный в [2, 3] подход состоит в обосновании основных соотношений теории выпуклой двойственности для рассматриваемых невыпуклых задач оптимизации и в применении основанного на них правила решения задачи. Изложим его, следуя работе [17] и применительно к общей задаче оптимизации:

0 o(z) -+ inf в области z Є Z, 0 (г) < 0у. (1.3)

Здесь Z - аффинное подпространство вещественного линейного пространства X, функции 0о(-) : X ~* Ж, <&() : X —> Y заданы, Y = {у}

— конечномерное вещественное линейное пространство, унорядоченное непустым выпуклым (не обязательно телесным) конусом К₊, т.е. у\ < Ї/2 *й" 2/2 — Уі Є К+. Введем функцию Лагранжа S(t*,г) := 0o(z) + г*0 (г), где г* Є Y* - множитель Лагранжа. Далее т* > 0 4 т*у > 0 Vij > 0. Упомянутое правило состоит в выполнении следующих действий. (I) Для т* > 0 решаем задачу

5(т*, г) -+ inf в области z Z, (1.4)

ограничиваясь нахождением величины Sq(t*) :—ivd_z^zS(T*,z). (II) Находим какое-либо решение Тд двойственной задачи

Sq(t*) -+ max в области т* > 0, (1.5)

где максимум обязательно достигается.

1. Находим все решения г задачи (1.4) с т* — г и затем отбрасываем решения z , не удовлетворяющие хотя бы одному из следующих соотношений 0(z) < 0, Tq0(z) = 0. Множество оставшихся точек {г⁰} совпадает с множеством всех решений исходной задачи (1.3).

2. Пусть inf{0_o(z) : z Є D} > -со, где D := {z Є Z : 0(z) < 0}. Последовательность {z_n} С /? является минимизирующей в задаче (1.3), т.е. 0о(г_п) -* inf^_e,D 0о(г) »р« п -+ со и z„ Є Г> V», в том и только том случае, если она минимизирующая в задаче (1.4) с т* :== Гц, т.е. S{t^,z_u) —* inl_zzzS(tq,z) при п —> со, и при этом 0 (z_n) < 0 Vn, т₀* 0 (z_n) - 0 п -* со.

Изложенный метод сводит решение исходной, вообще говоря, невыпуклой задачи к решению задач (1.4) и (1.5). Вторая из них, как несложно убедиться, является задачей конечномерной выпуклой оптимизации и, как правило, легко решается методами выпуклого программирования. Поэтому общая дееспособность метода в основном определяется возможностью эффективного решения задачи (1.4). Она в отличие от (1.3) не содержит нелинейного ограничения 0 (г) < 0 и в этом смысле проще. Более того, для многих линейно-квадратичных задач оптимального управления с квадратичными ограничениями (1.4) — это некоторая задача, изученная в классической линейно-квадратичной теории оптимального управления и допускающая простое решение. Этим и объясняется привлекательность метода (I)-(IV) в обсуждаемой области.

Вместе с тем вопрос о самой применимости этого метода нетривиален: известно, что во многих случаях метод некорректен, т.е. дает неправильный ответ, а сформулированные в (I)-(IV) утверждения

неверны. В [2, 3] метод (I)-(IV) был обоснован для задачи (1.1),(1-2), для аналогичной задачи с дискретным временем, стохастической задачи и задачи с периодическими коэффициентами. Следует также отметить, что корректность метода равносильна справедливости соотношения лагранжевой двойственности: інах_т->оІпі_гЄ7S(t*,z) — iafjgp &q(z), где D определено в (IV). Проблеме двойственности в задачах оптимизации посвящены многочисленные исследования (K.J.Arrow, L.Hurwicz, D.G.Luenberger, I.Ekeland, R.Temam, Е.Г.Голынтейн, В.Н.Соловьев, В.М.Тихомиров и многие другие.) В них, в частности, были предложены общие критерии справедливости лагранжевой двойственности, проверка которых обычно составляет отдельную и часто нетривиальную задачу, а также явно выделены некоторые типы задач, для которых эта двойственность имеет место и, значит, метод (I)-(IV) корректен. Среди них — задача (1.3) с выпуклыми функциями 0о(^-) и 0(-)^ задачи, сводимые к выпуклым посредством определенного приема, именуемого "релаксацией", а также некоторые другие. Из соответствующих фактов выделим те, что нашли применения в теории невыпуклых линейно-квадратичных задач оптимального управления с квадратичными ограничениями. В общей форме такие задачи можно записать в виде (1.3), где функции во(-) и 0(-) квадратичны, т.е.

0о(*)= Во(*) + Ч* + 7о, «*(*) = »(*) +Аг+ 7. (1.6)

Здесь Во(0 — квадратичная форма, a 55(-) — векторная квадратичная форма (т.е. <8 (г) — B{z, г), где В(-, ): X х X -+Y — билинейное симметричное отображение), 1$:Х —> R а А: X —*Y — линейные операторы, То Є К,7 Є У. В случае (1.6) правило (l)-(IV) корректно, если: 1) в (1.3) dirnF = 1 и X — вещественное пространство; 2) в (1.3) У = IR² и X — комплексное пространство, а в (1.6) В (г) = [2$ 1(2), »2(2)], Я5«(-) — эрмитовы, формы и операторы Щ и А линейны, если X рассматривать как вещественное пространство. В [2, 3] корректность метода (I)-(IV) была обоснована для задачи (1.3) с функциями (1.6) в случае пространства Y произвольной размерности, упорядоченного телесным конусом int К+ (в приложениях телесность соответствует отсутствию ограничений в виде равенств) в предположениях, обобщающих свойства конкретных линейно-квадратичных задач оптимального управления на бесконечном интервале времени с интегральными квадратичными ограничениями и стационарными или периодическими коэффициентами.

Эффективность применения метода (I)-(IV) к актуальным задачам

^Здесь и далее считаем, что ограничения из (1.3) совместны в некотором усиленном смысле.

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

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

Вопрос о применимости метода (I)-(IV) к линейно-квадратичным задачам с квадратичными ограничениями связан с вопросом о выпуклости образа квадратичного отображения. Дело в том, что для задачи (1.3) этот метод корректен (при неограничительных дополнительных предположениях), если выпукло множество & (Z)⁺ :— {у — щ + у+ : щ Є 0(Z),y+ Є К+}. Здесь &(z) := [<8₀(z), <3(z)} и K+ := {(*,») Є R x Y : t > О, у > 0}. В свою очередь выпуклость этого множества следует из выпуклости образа &(Z), где в случае (1.6) функция &() квадратична.

Результаты о выпуклости образов квадратичных отображений нашли важные применения не только в теории оптимального управления, но и в других дисциплинах: теории операторов (в том числе, дифференциальных), теории устойчивости дифференциальных уравнений и теории неопределенных систем управления. Основополагающими среди этих результатов можно, по-видимому, считать следующие факты. Теорема 0.1 (Toeplitz-Hausdorff) Пусть 051(-) и 25г(-) -пепрерывные эрмитовы формы, заданные на комплексном гильбертовом пространстве X — {х}. Отображение х н+ [2Ji(a:), г(лО] Є К² преобразует единичную сферу {х X : |а:| = 1} в выпуклое множество.

Теорема 0.2 (Dines) Пусть X — вещественное линейное пространство и Si(-), 2(-) : X —+ Ш - квадратичные формы. Образ пространства X при отображении х н-+ [^v3i(x), 2(3")] Є R² — выпуклое множество.

'Точнее, задача (1.4) является выпуклой при г* Є Т := {г* : г* > 0,5о(г*) > — со}, тя« S₀(t*) определено із (I). Такими г* молодо ограничиться ввиду представимости задачи (1.5) в виде 5о(г") —* max, г* Є Т. Последняя задача, как уже отмечалось, выпукла всегда.

Отметим также следующий близкий по тематике результат. Теорема 0.3 (Фрадков-Якубович) Пусть X — комплексное линейное пространство и Ші(-), Ss('), $з(-) : X -+ Ш. - эрмитовы формы. Образ пространства X при отображении х н-> [2$j(a;), Ъ%(х), з(^ж)] Є М³ — выпуклое множество.

Простые примеры показывают, что ни в одной из приведенных теорем число форм в общем случае увеличить нельзя. Это можно сделать только при дополнительных предположениях. Например, Теорема 0.2 распространяется на случай трех форм, если dimX > 3 и хотя бы одна из форм строго знакоопределена (работы L.Brickman и Y.H.Au-Yeuug, где также показано, что Теорема 0.1 верна в случае вещественного пространства размерности dimX > 3, при атом 2їі(-)> 25г(-) — квадратичные формы). Имеются также разрозненные результаты разных авторов, констатирующие выпуклость образа всего пространства или единичной сферы в случае, когда число форм произвольно. Не вдаваясь в подробное описание этих результатов, отметим, что они носят локальный характер, относятся к узким классам специальных форм, не включают в себя Теоремы 0.1-0.3 и в большинстве случаев не охватывают друг друга. Знакомство с доказательствами усиливает впечатление фрагментарности общей картины, так как различные группы результатов устанавливают выпуклость, опираясь на аргументы разной природы. Потребность в более глубоком осмыслении причин выпуклости образов квадратичных отображений отмечал еще П.Халмош в связи с классической теоремой Тешгаца-Хаусдорфа. Он писал [4, с.114,115] "все известные доказательства основаны на вычислениях. Эти вычисления можно провести хорошо или плохо, но от этого они не перестают быть вычислениями Хотелось бы получить идейное доказательство, пусть даже (или особенно?) с использованием менее элементарных понятий, чем в вычислительном доказательстве."

Цель работы состояла в расширении сферы гарантированной применимости метода (I)-(IV) к невыпуклым задачам оптимального управления системами, описываемыми дифференциальными уравнениями, в том числе, в частных производных. В рамках принятой в работе методики указанная цель подразумевала получение различных обобщений классической теоремы Теплица-Хаусдорфа, а также Теорем 0.2 и 0.3 на случай произвольного конечного числа форм. Подобные обобщения могут представлять самостоятельный интерес. В цели работы входила также демонстрация возможностей полученных результатов об образах квадратичных отображений в общей теории необходимых условий оп-

тимальности.

Методы. Корректность метода (I)-(IV) выводилась как следствие полученных в работе результатов о выпуклости образов квадратичных (и более общих) отображений. Точнее, для обоснования его применимости достаточно установить выпуклость не образа (Z) отображения 6 () : X -> V, а надобраза &(Z)⁺ := {у = jft, + У+ Ш Є (%), У+ Є А'+} (где А"₊ — заданный выпуклый конус). Поэтому много внимания было уделено исследованию надобраза. Если К₊ = {0}, он совпадает с образом; при А'₊ -ф {0} его выпуклость — свойство более слабое, чем выпуклость образа, и в этом случае получены критерии выпуклости надобраза с требованиями, более слабыми, чем в случае образа.

При изучении квадратичных и более общих отображений ключевую роль играли результаты, касающиеся векторных квадратичных форм 9$ () : X —> У, в частности, результаты о выпуклости надобраза 93 (V)⁺ произвольной окрестности нуля V С X в заданной локально выпуклой топологии в X. Применялись два подхода к исследованию образа и надобраза векторной квадратичной формы. Один из них развивает метод, разработанный А.А.Милютиным для исследования анормальных экстремальных задач и связанный с понятием суперлежапдрова конуса квадратичного отображения [14]. Другой подход основан на изучении направления от произвольной точки пространства до ближайшей к ней точки надобраза. При этом привлекались методы теории экстремальных задач, а также метод возмущений квадратичного отображения, заложенный в работах А.А.Аграчева, а утверждения о выпуклости устанавливались предельным переходом из более общих результатов, констатирующих приближенную выпуклость надобраза в смысле метрической близости к некоторому выпуклому множеству. Эти результаты, в свою очередь, опираются на установленную в работе и верную для любой формы оценку надобраза: fc_ С 93(^Y)⁺ С Y \k₊ (второе включение выполнено при *8(Х)⁺ ф У). Здесь &_ и к₊ — выпуклые конусы, для которых получено явное (в известном смысле) описание. Точнее, результаты о выпуклости надобраза опираются на оценку Аг_ С 93 (Х)⁺. Оценка 53 [Х)⁺ cY\k₊ играет ключевую роль при исследовании необходимых условий оптимальности в гладкой экстремальной задаче.

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

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

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

Получены обобщения указанных ранее классических теорем Теплица-Хаусдорфа и Дайнса, а также теоремы Фрадкова-Якубовича на случай, когда число форм произвольно. Эти обобщения охватывают также утверждения из [5, 6] о выпуклости образа единичной сферы комплексного гильбертова пространства X — {х} при отображении х *-* [{Aix,x) ,..., {AkX,а;)] (где {,) — скалярное произведение в X и А, — эрмитово самосопряженные операторы) в случае классических или абстрактных теплицевых операторов А;, "нетривиальную" составляющую аналогичных результатов [5,7], касающихся случая, когда операторы Аі коммутируют или хотя бы почти коммутируют (т.е. A_tTAj = AjTA; Vi, j для некоторого симметричного положительно определенного оператора Т : X — Л"), результаты [8] о сюръективности векторной квадратичной формы S () : X —-» У, а также результаты [2, 3] о выпуклости замыкания S (X) для форм Ш () специального вида. Объединение этих утверждений произошло не эклектически, а как естественное следствие некоторой единой точки зрения на причины выпуклости образа.

Установлен ряд технических фактов, которые могут представлять и самостоятельный интерес. Именно, получены критерии выпуклости⁵* не только образа ?8(Х), но и надобраза 93(-^)+ := %$(Х) + К₊ векторной квадратичной формы QJ(-): X —> У в случае, когда пространство У упорядочено выпуклым конусом А"+. При этом к форме S () предъявлены более слабые требования, чем в случае, когда речь идет об образе S (X). Установлены критерии выпуклости^ надобраза множества, опи-

⁵Точнее, несколько более слабого свойства почти выпуклости, определение которого см. иа с.12.

сываемого конечной системой квадратных уравнении и неравенств, а также произвольной окрестности нуля в заданной локально выпуклой топологии. Для образа единичной сферы и надобраза всего пространства получены критерии их приближенной выпуклости в смысле близости к некоторому выпуклому множеству и установлены явные оценки степени близости. Найдены критерии выпуклости^ надобраза {Х)⁺ для отображений вида 0(-)= (-) + Ф(*)і ^гД^е (^-) — векторная квадратичная форма, а Ф(-) — функция со специальными свойствами, например, выпуклая. Для произвольной формы S(-) установлены "оценки"

надобраза: fc_ С Ш (Х)+, <В (Х)⁺ ф У ^ «8 (Х)+ cY\k₊. Здесь fc_, к+

выпуклые конусы, описанные в известном смысле явно в двойственных терминах и с привлечением индекса инерции скалярных квадратичных форм г*5$(-),т* Є Y*. Автору неизвестны прецеденты исследования вопросов выпуклости надобраза, & ТЙІКЖЄ приближенной выпуклости образа или надобраза векторной квадратичной формы, выпуклости образа произвольной окрестности нуля или выпуклости надобразов отображений вида 0(-) = 3(-) + Ф(-) с выпуклой функцией Ф(-). Результаты, охарактеризованные в данном и предыдущем абзацах, сформулированы на языке функционального анализа. Вместе с тем они относятся к ситуациям, которые возникают в связи с исследованиями, касающимися дифференциальных уравнений, и находят приложения, связанные прежде всего с такими уравнениями.

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

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

Апробация. Основные материалы, вошедшие в диссертацию, были представлены на American Control Conference (June 1995, Seattle, USA); на 3rd European Control Conference (September 1995, Rome, Italy); на 4th European Control Conference (July 1997, Brussels, Belgium); на 2nd Russian-

^Точнее, несколько более слабого свойства почти выпуклости, определение которого см. на с.12.

Swedish Control Conference (August 1995, Saint Petersburg, Russia); на 4th International Workshop Multiple criteria and game problems under uncertainty (September 1996, Orehovo-Zuevo, Russia); на международной конференции Дифференциальные уравнения и их приложения (декабрь 1996, Санкт-Петербург, Россия); на International Workshop Nonsmooth analysis and optimization (September 1995, Saint Petersburg, Russia); на International Workshop Nonlinear mechanics and partial differential equations (October 1996, Saint Petersburg, Russia). Результаты диссертации докладывались на Санкт-Петербургском городском семинаре по математической физике им. В.И.Смирнова (рук. акад. О.А.Ладыженская); на семинаре Нелинейный анализ и оптимизация в МГУ им. М.В.Ломоносова (рук. проф. М.И.Зеликин, А.В.Куржанский, Ю.С.Осипов, В.М.Тихомиров, А.В.Фурсиков); на семинаре на фак-те ВМК МГУ им. М.В.Ломоносова (рук. проф. А.А.Милютин); на семинаре кафедры дифференциальных уравнений СПбГУ (рук. проф. В.А.Плисе); на семинаре кафедры теоретической кибернетики СПбГУ (рук. проф. В.А.Якубович); на семинаре кафедры математического анализа СПбГПУ им. А.И.Герцена (рук. проф. В.П.Одинец); на семинаре Division of Optimization and System Theory, Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden (рук. проф. A.Lindquist); на семинарах в University of Western Australia, Perth, Australia.

Публикации. Основные результаты диссертации опубликованы в работах [17-32].

Объем и структура диссертации. Работа изложена на 406 страницах и состоит из введения, трех глав, разделенных на 14 параграфов, и списка литературы из 199 наименований.