Содержание к диссертации
Введение
1 Внутреннее оценивание пересечения эллипсоидов при помощи линейной свертки квадратичных форм 19
1.1 Формализация методов оценивания 19
1.2 Линейная свертка квадратичных форм и ее использование в оценивании пересечения 22
1.3 Связь методов оценивания пересечения и объединения 30
1.4 Численная реализация методов оценивания 38
1.5 Эллипсоидальное решение задачи синтеза управления при ограниченных координатах 44
2 Классификация пересечения эллипсоидов 51
2.1 Основные определения 51
2.2 Множество о 58
2.3 Множество і 69
2.4 Множество і 80
2.5 Множество J 85
2.6 Классификация 92
3 Недоминируемые внутренние оценки пересечения эллипсоидов 96
3.1 Достаточное условие недоминируемости 97
3.2 Внешнее оценивание объединения (концентрический случай) 100
3.3 Внешнее оценивание объединения (случай осевой симметрии) 108
3.4 Внутреннее оценивание пересечения 116
Заключение 119
Библиография 120
- Линейная свертка квадратичных форм и ее использование в оценивании пересечения
- Эллипсоидальное решение задачи синтеза управления при ограниченных координатах
- Внешнее оценивание объединения (концентрический случай)
- Внутреннее оценивание пересечения
Введение к работе
Исследование динамических систем с неопределенностью является одним из наиболее востребованных направлений современной математической теории. Особое внимание уделяется проблемам оценивания в задачах управления и наблюдения. Результаты, полученные в этом направлении, находят приложения в различных областях человеческой деятельности, таких как автоматизация, робототехника и телекоммуникация. Классические задачи оценивания основаны на предположении, что вероятностные возмущения параметров системы известны, или по крайней мере известны их статистические характеристики, такие как математические ожидания или ковариационные матрицы. Однако, во многих приложениях статистическое описание не является полным или адекватным в силу отсутствия достаточного количества экспериментальных данных или их статистической неустойчивости. По этой причине, начиная с 60-х годов прошлого столетия, в рамках теории гарантированного оценивания развивается альтернативный подход, связанный с предположением об ограниченности неопределенных параметров модели некоторыми известными множествами. Разработка основ теории связана с именами Н.Н. Красовского [11], А.Б. Куржанского [12], X. Витзенхаузена [52|, Ф. Швеппе [48], Д. Бертсекаса и И. Родэса [23J. Дальнейшее развитие данный метод получил в работах [18, 31, 38, 41] и многих других. В последнее время также проявляется интерес к моделям со смешанной неопределенностью [5J и почти произвольными помехами [4].
Отметим, что в рамках направления гарантированного оценивания, используя теорию множеств, выпуклый и многозначный анализ, зачастую удается получить точные аналитические описания множеств возможных состояний изучаемой системы. Однако, как правило, эти множества имеют очень сложную структуру. Поэтому не меньший интерес вызывает задача построения для них гарантированных, то есть внутренних или
внешних, аппроксимаций в некотором классе множеств канонической формы, описываемых конечным числом параметров. К наиболее используемым на практике классам множеств можно отнести многогранники [35, 42, 51], параллелотопы [7, 8, 9,26] и эллипсоиды [18, 38]. Особой популярностью пользуются эллипсоидальные множества в силу гладкости границы, наглядности и удобства численной реализации. Расширение использования эллипсоидального подхода в оценивании в немалой степени связано с развитием теории так называемого эллипсоидального исчисления. Данный термин был впервые введен в работе [38] для обозначения совокупностей методов построения гарантированных эллипсоидальных оценок для результатов различных операций над эллипсоидами. Существенный вклад в изучение эллипсоидальных методов для задач динамики принадлежит С. Бойду [25], А.Б. Куржанскому [38,40], Ф.Л. Черноусько [18] и их ученикам. В процессе развития в эллипсоидальном исчислении оформились два основных подхода к оцениванию. Первый (см. [18]) основан на построении единственной аппроксимации, по возможности обладающей теми или иными оптимальными свойствами, в качестве которых могут использоваться объем эллипсоида, сумма радиусов эллипсоида и многие другие. Второй (см. [38]) предполагает описание бесконечного семейства оценок, объединение или пересечение которых совпадает с оцениваемым множеством. Последнее требование мотивировано естественным стремлением наделить метод оценивания свойством неограниченного повышения точности аппроксимации за счет рассмотрения все большего и большего количества эллипсоидов. При этом, как правило, неоднозначность оценки компенсируется требованием недоминируемости, то есть максимальности или минимальности по включению, каждой оценки семейства. Важно отметить, что в рамках второго подхода также остается возможность выделения в семействе оценок конкретных представителей, удовлетворяющих перечисленным выше критериям оптимальности.
Конкретный набор оцениваемых операций над эллипсоидами преимущественно связан с потребностями, возникающими в процессе исследования задач управления и наблюдения для линейных динамических систем с эллипсоидальными ограничениями на неизвестные параметры. В связи с этим самыми востребованными (в плане оценивания) операциями в настоящее время являются алгебраическая сумма и геометрическая
разность эллипсоидов, активно используемые для построения гарантированных оценок множеств достижимости и разрешимости означенных динамических систем. Однако не меньший интерес вызывает проблема оценивания пересечения эллипсоидов, которая возникает в частности в задачах наблюдения в условиях неопределенности [10] или управления при наличии фазовых ограничений [38]. Отметим, что, в то время как первый класс задач обычно связан с построением внешних оценок, для второго класса практическое использование допускают преимущественно внутренние оценки. В качестве примера можно привести задачу синтеза управления, заключающуюся в построении многозначной позиционной стратегии, обеспечивающей попадание линейной динамической системы в конечный момент времени на заданное множество при одновременном соблюдении фазовых ограничений. Идею постановки данной задачи и подход к решению можно найти в работах [37] и [38]. В данном случае достижение терминального множества возможно не только при использовании максимально возможной стратегии, но и любой ее внутренней оценки. В то же время соответствующая внешняя аппроксимация находит весьма ограниченное применение.
В то время, как задачи внешнего и внутреннего оценивания суммы и геометрической разности эллипсоидов к настоящему моменту полностью решены и соответствующие методы оценивания [18, 38] давно и успешно используются в различных приложениях, в направлении, связанном с пересечением эллипсоидов, результаты не столь впечатляющие. Главная трудность заключается в том, что, в отличие от суммы или геометрической разности, пересечение эллипсоидов в общем случае не обладает ни центральной, ни какой либо другой симметрией. Помимо этого, наблюдаются качественные отличия в строении оцениваемого множества в разных случаях пересечения, а также существенная зависимость последнего от взаимного расположения эллипсоидов.
Исторически первым подходом к оцениванию пересечения эллипсоидов было использование различных алгоритмов построения двусторонних эллипсоидальных оценок выпуклого компактного множества М = {х Є Rn | /;(х) < 0, і = 1,т}, где /;{) — некоторые выпуклые функции, такие что intM ф 0. Результатом применения таких
методов, как правило, являются соотношения вида
х + г\Е С.М Сх + г2 ( х Є int М, J"2 > гі > 0 )
где является эллипсоидом с центром в начале координат. При этом обязательным свойством является независимость отношения viJt\ от оцениваемого множества. Впервые подобные оценки были получены в работах [29, 32], где в качестве х + Гг рассматривался минимальный по объему описанный эллипсоид, для которого были доказаны существование и единственность среди всех внешних эллипсоидальных оценок множества Л4. Там же было показано, что из такого эллипсоида, который в западной литературе получил название Lowner-John ellipsoid, можно получить и внутреннюю оценку, положив Гз/гі = п. Отметим, что для случая т > 1 непосредственное вычисление внешней минимальной по объему эллипсоидальной оценки является довольно сложной в вычислительном плане процедурой. Поэтому в ряде работ, таких как [46], предлагается использование более простого алгоритма, обеспечивающего отношение гг/гі — \/п[п + Ї). Альтернативой построению "наилучшей внешней оценки" является построение "наилучшей внутренней оценки". Так, если в качестве х + гіЄ взять максимальный по объему вписанный эллипсоид, то парная внешняя оценка будет удовлетворять условию Г2/Г1 = п. Данный подход применительно к пересечению эллипсоидов приводит к задаче выпуклой оптимизации с ограничениями в виде линейных матричных неравенств [25[, для которой разработано много эффективных численных методов. Еще одну довольно многочисленную группу составляют "методы аналитического центра", в основе которых лежит использование логарифмической штрафной
функции <р(х) = — 1п(—/Да;)). Данный подход был впервые предложен в работах
(=1 [6, 34, 49] для оценивания многогранников, и в дальнейшем был обобщен на случай
множеств более общего вида [24, 30, 43, 50]. Все методы, относящиеся к данной группе, тесно связаны с построением так называемого эллипсоида Дикина, который для каждой точки z Є intAl определяется как [z] = {х Є Rn | {х — z, H(z)(x — z)) < і}, где H{z) = V2
[z] С АЛ- При этом в качестве внутренней аппроксимации (х + Т\) обычно берут эллипсоид [ж*], где х* = argmin <р(х) является аналитическим центром рассматриваемой системы неравенств. Соответствующее этому эллипсоиду отношение гг/гь позволяющее строить внешние оценки, не зависит от размерности пространства тї и однозначно выражается через количество ограничений т. Конкретное значение отношения было неоднократно пересмотрено в сторону улучшения в целом ряде работ. Последний из известных автору результатов, полагающий Гі(г\ = m, представлен в работе [27J.
Помимо универсальных алгоритмов двухстороннего оценивания, существуют также специализированные методы для получения исключительно внешних или внутренних эллипсоидальных оценок пересечения. Более богатым в этом плане является внешнее оценивание. Например, в работе [25] приводятся (в терминах линейных матричных неравенств) достаточные условия для параметров эллипсоида, описанного вокруг пересечения заданных эллипсоидов. Последнее позволяет использовать эффективные численные методы оптимизации для получения единичных представителей, обладающих оптимальными свойствами. Однако наибольшее распространение получил подход,
при котором внешние оценки для pi і, где j = (х Rn | (х — <ц, Q,_1(x — fy)) < 1}
*=1
(i = 1,т), ищутся в виде множеств уровня линейной свертки квадратичных форм:
Є+ = іхЄКп ац(х-ъ,0;1(х-ад)<1\ щ > 0 (i = 1,
m)
Не трудно проверить, что при условии 2 щ = 1 выполняется включение П i С +.
Среди первых работ, в которых использовались подобные оценки, можно назвать [33] и [47]. К сожалению, данный подход в определенных случаях может порождать весьма неудовлетворительные аппроксимации, в связи с чем были разработаны альтернативные методы. Так, в [17] и [36] задача внешнего оценивания пересечения эллипсоидов сводится к внешнему оцениванию суммы эллипсоидов при помощи включения
Л С М& + + Mmm> Мі Є Rnxn, Т.Мі = E,
что в конечном итоге позволило в [38] построить бесконечное семейство внешних оценок пересечения (в том числе и достаточно приемлемых), допускающее представление оцениваемого множества в виде пересечения всех аппроксимаций. С другой стороны в
[18] для случая т = 2 было продемонстрировано использование алгоритмического подхода, допускающего последовательное итерационное улучшение внешней оценки. Суть идеи заключается в предварительном мажорировании эллипсоида большего объема полупространством или множеством вида {х Є R" j с\ < (x,b) < (} и последующем оптимальном внешнем эллипсоидальном оценивании эллиптического сегмента или слоя, применяя известные явные аналитические формулы.
Среди специализированных методов внутреннего оценивания пересечения, можно отметить один интересный подход, представленный в работе [38]. В его основе лежит сведение внутреннего оценивания пересечения эллипсоидов \ Л 2 С R71 к внутреннему оцениванию суммы эллипсоидов удвоеной размерности при помощи представления
5хП2 = [х ЄКП | ( * ) Є Єї+Є; С R2"},
где * С R2" является вырожденным эллипсоидом, опорная функция которого равна
Данный подход, в силу существования способа оценивания суммы, допускает построение семейства внутренних оценок пересечения, однако его серьезным недостатком является большая вероятность получения пустых множеств, что усложняет практическое использование.
В целом, внутреннее оценивание пересечения все еще остается недостаточно проработанным направлением теории эллипсоидального исчисления. При этом в прикладных задачах особенно остро ощущается недостаток метода, предлагающего в явном аналитическом виде формулы для описания достаточно представительного семейства удовлетворительных внутренних оценок пересечения произвольной пары эллипсоидов.
Цель данной диссертации состоит в разработке метода внутреннего эллипсоидального оценивания пересечения двух эллипсоидов, обеспечивающего получение преимущественно недоминируемых (в данном случае максимальных по включению) аппроксимаций и допускающего предельное представление оцениваемого множества в виде замыкания объединения всех порождаемых внутренних оценок.
Перейдем к описанию основных результатов диссертации.
Первая глава посвящена описанию методов внутреннего оценивания пересечения
эллипсоидов, основаных на использовании множеств уровня линейной свертки квадратичных форм.
В первом параграфе определяется класс невырожденных эллипсоидов (a, Q) и его традиционные обобщения. Вводится понятие гарантированной эллипсоидальной оценки множества и условие ее недоминируемости. В заключение дается формальное определение метода эллипсоидального оценивания как совокупности конкретных математических объектов, а также оговариваются условия "качественной и количественной удовлетворительности" метода, используемые в работе. Первое условие связано с требованием недоминируемости порождаемых аппроксимаций, а второе — с наличием достаточного количества оценок для получения предельного представления оцениваемого множества в виде их объединения или пересечения.
Во втором параграфе для каждой пары эллипсоидов {г, 2) определяется класс Z>{\, 2) множеств уровня всевозможных линейных сверток соответствующих квадратичных форм. После этого доказывается утверждение о существовании в Z{\, 2) единственной неулучшаемой (в своем классе) внутренней оценки пересечения і П 2. В результате производится построение универсального способа оценивания пересечения эллипсоидов, основанного на решении экстремальной задачи вида min{ACi(x) | /С3(х) = 1} для некоторых смещенных квадратичных форм 1(),^2(-)-
В третьем параграфе устанавливается связь методов внутреннего оценивания пересечения и внешнего оценивания объединения эллипсоидов. Описывается способ сведения первой обозначений задачи оценивания ко второй при помощи полярной двойственности. Для того, чтобы иметь возможность воспользоваться данной техникой, требуется предварительно научиться оценивать объединение эллипсоидов Є\ U 2 снаружи. Поставленная задача полностью решается в классе Я(і,2), при этом доказывется утверждение о существовании среди элементов 2(i,f2) единственной неулучшаемой (в своем классе) оценки, параметры которой выражаются через решение экстремальной задачи вида max{i(;r) | К,ч{х) = 1} для смещенных квадратичных форм /Ci (-),^0)-Использование полярной двойственности в конечном итоге позволяет получить из единственной внешней оценки объединения бесконечное семейство различных внутренних
оценок пересечения эллипсоидов за счет неоднозначности выбора точки, принимаемой за новое начало координат при осуществлении перехода к полярам. Кроме того, интересно отметить, что полученный метод оценивания пересечения является, в отличие от построенного ранее, "количественно удовлетворительным", то есть допускает представление оцениваемого множества в виде замыкания объединения всех оценок семейства.
Четвертый параграф полностью посвящен численной реализации предложенных методов оценивания. В центре внимания находится решение возникающих задач квадратичной оптимизации при квадратичных ограничениях. Изучению задач данного и более общего вида посвящено множество работ, среди которых [22, 27, 28, 44]. В основе построения большинства соответствующих численных методов лежит использование так называемой S-процедуры. Данный термин был впервые предложен в работе [21] для описания необходимых и достаточных условий неотрицательности одной квадратичной функции на множестве векторов, для которых неотрицательными являются одна или несколько других. Доказательство большинства основных результатов в этой области принадлежит В.А. Якубовичу и его ученикам (см. [15, 16, 19, 20]). Однако в данном разделе рассматривается альтернативный подход, в основе которого лежит использование специфических свойств однопараметрических семейств внешних оценок суммы и внутренних оценок геометрической разности эллипсоидов, представленных в работе [38]. В результате удается свести все поставленные многомерные экстремальные задачи к одномерным задачам отимизации на конечном отрезке, допускающим эффективное численное решение.
Пятый параграф демонстрирует применение внутренних оценок пересечения для практического нахождения (эллипсоидального) решения задачи синтеза управления для дискретной линейной динамической системы, обеспечивающего попадание в конечный момент времени на терминальное множесто и не нарушающего ограничений на фазовое состояние системы в процессе движения. При этом терминальное множество и фазовые ограничения задаются в виде невырожденных эллипсоидов. В заключение производятся численные расчеты с использованием универсального способа внутреннего оценивания пересечения эллипсоидов, представленного во втором параграфе, а также способа внутреннего оценивания суммы эллипсоидов, описанного в работе [38].
Во второй главе производится классификация пар эллипсоидов с непустой внутренностью пересечения. В основе классификации лежат условия, равносильные наличию или отсутствию возможности (за счет некоторого переноса начала координат) осуществления такого "полярного отражения" (то есть перехода к полярам), в результате которого взаимное расположение множеств обретет определенную симметрию. Рассматриваемые виды симметрии ограничены центральной симметрией, что равносильно условию концентричности эллипсоидов, и: осевой симметрией (последняя понимается с точностью до некоторого аффинного преобразования).
В первом параграфе второй главы обозначенный критерий классификации формализуется для фиксированной пары пересекающихся эллипсоидов (ї, 2) в терминах пустоты или непустоты множеств во, 1 Q int(5i П 2), состоящих из всех возможных векторов, полярное отражение относительно которых приводит рассматриваемые эллипсоиды к центральной или осевой симметрии соответственно. Кроме этого, определяются множества 0^ С ! и 0j С 0\, аналогичным образом связанные с дополнительными (помимо осевой симметрии) условиями, накладываемыми на взаимное расположение эллипсоидов, полученных в результате полярного отражения. Для упрощения конкретных формулировок воспользуемся условным термином "строгая сравнимость по включению" для обозначения соотношения между двумя абстрактными множествами, при котором одно из них принадлежит относительной внутренности другого. Тогда, можно сказать, что <Э\ добавляет требование, интерпретируемое как отсутствие "строгой сравнимости по включению" проекций эллипсоидов на ось симметрии. В свою очередь 62 дополняет упомянутое требование условием, которое можно аналогично проинтерпретировать как отсутствие "строгой сравнимости по включению" проекций эллипсоидов на гиперплоскость, перпендикулярную оси симметрии (оба представленных условия сформулированы для эллипсоидов, полученных в результате применения некоторого аффинного преобразования, приводящего исходные множества к общей осевой симметрии). После введения всех обозначений ставится задача определения условий непустоты и получения аналитического описания множеств во, ві, в^, в".
Во втором параграфе рассматривается множество в0 и показывается, что критерием его непустоты для пары ± = {щ, Qi) (і = 1,2) является условие отсутствия
кратных и комплексных корней у некоторой функции /(), такой что
| z4{Q\ - kQ2)-1z + іг1 - 1, если det(Qi - ttQ2) ф О
urn }{а), иначе,
где z = cli — аъ. Отметим, что областью определения функции /() является множество всех комплексных чисел 7г ф 0, таких что z Є Ini(Qj — ttQ2). Помимо этого устанавливается однозначное соответствие векторов множества во определенным собственным векторам матрицы И^И2 Є R.("+l)x(+i)j где
соответствующим собственному значению 7Г, такому что /(тг) = 0, /'(тг) < 0.
В третьем параграфе изучается множество і. Основным результатом является утверждение о непустоте данного множества для всех пересекающихся эллипсоидов і ф 2, кроме случая, когда функция /() имеет корень кратности 3. Кроме этого показывается связь элементов рассматриваемого множества с некоторыми двумерными несобственными инвариантными подпространствами матрицы fl^1^, что в конечном итоге позволяет получить полное аналитическое описание j.
В четвертом параграфе доказывается утверждение о том, что Q'x Ф если и только если /() имеет комплексные корни или корень кратности 2, и при ЭТОМ J = 01-
В пятом параграфе выясняется, что критерием непустоты ^' является непустота і и отсутствие свойства вложенности эллипсоидов друг в друга. При этом дается описание множества і' в терминах корней уравнений /(тг) = 0 и dettQj1 — \Qll) = 0.
В шестом параграфе все полученные во второй главе результаты объединяются вместе с целью получения полной картины. Основным результатом параграфа (и всей главы) является утверждение о том, что для "почти любой" пары пересекающихся и не вложенных друг в друга эллипсоидов одно (и только одно) из множеств о либо " не пусто. При этом единственным случаем пересекающихся эллипсоидов, не допускающим приведения ни к одному из рассматриваемых видов симметрии является случай наличия у функции /() корня кратности 3, что в геометрическом смысле соответствует особой разновидности касания поверхностей исходных эллипсоидов.
Целью третьей главы диссертации является разработка метода построения недоминируемых эллипсоидальных аппроксимаций пересечения эллипсоидов, основанного на классификации пересечения, представленной во второй главе. Используя обозначенную в первой главе двойственность задач оценивания пересечения и объединения эллипсоидов, исходная задача построения внутренних аппроксимаций пересечения не вложенных друг в друга эллипсоидов в большинстве случаев (кроме оговоренного исключения) сводится к задаче внешнего оценивания объединения эллипсоидов, удовлетворяющих либо требованию концентричности (если Go ф 0), либо расширенному требованию наличия осевой симметрии (если Q'[ Ф 0). Следовательно, для достижения поставленной в данной главе цели достаточно научиться оценивать снаружи (недоминируемым образом) только обозначеные случаи объединения эллипсоидов.
В первом параграфе формулируется и доказывается достаточное условие недоми-нируемости гарантированной эллипсоидальной аппроксимации, которое в дальнейшем используется для обоснования "качественной удовлетворительности" разрабатываемых методов.
Во втором параграфе описывается алгоритм построения недоминируемых внешних аппроксимаций объединения концентрических эллипсоидов. При этом в начале рассматриваются диагональные матрицы, а затем построенный способ оценивания переносится на произвольный случай. Отметим, что представленный в параграфе метод оценивания является не только "качественно", но и "количественно удовлетворительным".
Третий параграф посвящен внешнему оцениванию объединения неконцентрических эллипсоидов, обладающих тем не менее осевой симметрией "в широком смысле" и некоторыми дополнительными свойствами, перечисленными в определении множества
е;'.
В качестве основного инструмента используется уже построенный метод внешнего оценивания концентрических эллипсоидов, который в данном случае применяется к определенным парам концентрических эллипсоидов, мажорирующих исходные множества так, чтобы все внешние оценки объединения мажорант удовлетворяли достаточному условию недоминируемости для объединения исходных множеств. Следует отметить,
что полученный в результате описанных манипуляций метод в случае пространства R2 существенно упрощается и становится "количественно удовлетворительным", не смотря на то, что в общем случае это свойство отсутствует.
В четвертом параграфе оба метода внешнего оценивания объединения используются вместе для построения алгоритма внутреннего оценивания пересечения, применимого в большинстве практических случаев. Для пространства R.2 описывается упрощенный вариант метода, который ко всему прочему полностью решает поставленную задачу в "количественном" плане (в отличие от общего случая).
Результаты диссертации отражены в публикациях [1, 2, 3], а также представлены в виде докладов на следующих конференциях:
международная конференция студентов и аспирантов по фундаментальным наукам "Ломоносов-2000" (Москва, МГУ, апрель 2000 г.)
школа-семинар молодых ученых факультета ВМиК МГУ им. М.В. Ломоносова (Дубна, октябрь 2001 г.)
Автор выражает признательность своему научному руководителю Александру Борисовичу Куржанскому за постановку задачи и полезные критические замечания.
Линейная свертка квадратичных форм и ее использование в оценивании пересечения
В первом параграфе определяется класс невырожденных эллипсоидов (a, Q) и его традиционные обобщения. Вводится понятие гарантированной эллипсоидальной оценки множества и условие ее недоминируемости. В заключение дается формальное определение метода эллипсоидального оценивания как совокупности конкретных математических объектов, а также оговариваются условия "качественной и количественной удовлетворительности" метода, используемые в работе. Первое условие связано с требованием недоминируемости порождаемых аппроксимаций, а второе — с наличием достаточного количества оценок для получения предельного представления оцениваемого множества в виде их объединения или пересечения.
Во втором параграфе для каждой пары эллипсоидов {г, 2) определяется класс Z {\, 2) множеств уровня всевозможных линейных сверток соответствующих квадратичных форм. После этого доказывается утверждение о существовании в Z{\, 2) единственной неулучшаемой (в своем классе) внутренней оценки пересечения і П 2. В результате производится построение универсального способа оценивания пересечения эллипсоидов, основанного на решении экстремальной задачи вида min{ACi(x) /С3(х) = 1} для некоторых смещенных квадратичных форм 1(), 2(-) В третьем параграфе устанавливается связь методов внутреннего оценивания пересечения и внешнего оценивания объединения эллипсоидов. Описывается способ сведения первой обозначений задачи оценивания ко второй при помощи полярной двойственности. Для того, чтобы иметь возможность воспользоваться данной техникой, требуется предварительно научиться оценивать объединение эллипсоидов Є\ U 2 снаружи. Поставленная задача полностью решается в классе Я(і,2), при этом доказывется утверждение о существовании среди элементов 2(i,f2) единственной неулучшаемой (в своем классе) оценки, параметры которой выражаются через решение экстремальной задачи вида max{i(;r) К,ч{х) = 1} для смещенных квадратичных форм /Ci (-), 0)-Использование полярной двойственности в конечном итоге позволяет получить из единственной внешней оценки объединения бесконечное семейство различных внутренних оценок пересечения эллипсоидов за счет неоднозначности выбора точки, принимаемой за новое начало координат при осуществлении перехода к полярам. Кроме того, интересно отметить, что полученный метод оценивания пересечения является, в отличие от построенного ранее, "количественно удовлетворительным", то есть допускает представление оцениваемого множества в виде замыкания объединения всех оценок семейства.
Четвертый параграф полностью посвящен численной реализации предложенных методов оценивания. В центре внимания находится решение возникающих задач квадратичной оптимизации при квадратичных ограничениях. Изучению задач данного и более общего вида посвящено множество работ, среди которых [22, 27, 28, 44]. В основе построения большинства соответствующих численных методов лежит использование так называемой S-процедуры. Данный термин был впервые предложен в работе [21] для описания необходимых и достаточных условий неотрицательности одной квадратичной функции на множестве векторов, для которых неотрицательными являются одна или несколько других. Доказательство большинства основных результатов в этой области принадлежит В.А. Якубовичу и его ученикам (см. [15, 16, 19, 20]). Однако в данном разделе рассматривается альтернативный подход, в основе которого лежит использование специфических свойств однопараметрических семейств внешних оценок суммы и внутренних оценок геометрической разности эллипсоидов, представленных в работе [38]. В результате удается свести все поставленные многомерные экстремальные задачи к одномерным задачам отимизации на конечном отрезке, допускающим эффективное численное решение.
Пятый параграф демонстрирует применение внутренних оценок пересечения для практического нахождения (эллипсоидального) решения задачи синтеза управления для дискретной линейной динамической системы, обеспечивающего попадание в конечный момент времени на терминальное множесто и не нарушающего ограничений на фазовое состояние системы в процессе движения. При этом терминальное множество и фазовые ограничения задаются в виде невырожденных эллипсоидов. В заключение производятся численные расчеты с использованием универсального способа внутреннего оценивания пересечения эллипсоидов, представленного во втором параграфе, а также способа внутреннего оценивания суммы эллипсоидов, описанного в работе [38]. Во второй главе производится классификация пар эллипсоидов с непустой внутренностью пересечения. В основе классификации лежат условия, равносильные наличию или отсутствию возможности (за счет некоторого переноса начала координат) осуществления такого "полярного отражения" (то есть перехода к полярам), в результате которого взаимное расположение множеств обретет определенную симметрию. Рассматриваемые виды симметрии ограничены центральной симметрией, что равносильно условию концентричности эллипсоидов, и: осевой симметрией (последняя понимается с точностью до некоторого аффинного преобразования).
В первом параграфе второй главы обозначенный критерий классификации формализуется для фиксированной пары пересекающихся эллипсоидов (ї, 2) в терминах пустоты или непустоты множеств во, 1 Q int(5i П 2), состоящих из всех возможных векторов, полярное отражение относительно которых приводит рассматриваемые эллипсоиды к центральной или осевой симметрии соответственно. Кроме этого, определяются множества 0 С ! и 0j С 0\, аналогичным образом связанные с дополнительными (помимо осевой симметрии) условиями, накладываемыми на взаимное расположение эллипсоидов, полученных в результате полярного отражения. Для упрощения конкретных формулировок воспользуемся условным термином "строгая сравнимость по включению" для обозначения соотношения между двумя абстрактными множествами, при котором одно из них принадлежит относительной внутренности другого. Тогда, можно сказать, что Э\ добавляет требование, интерпретируемое как отсутствие "строгой сравнимости по включению" проекций эллипсоидов на ось симметрии. В свою очередь 62 дополняет упомянутое требование условием, которое можно аналогично проинтерпретировать как отсутствие "строгой сравнимости по включению" проекций эллипсоидов на гиперплоскость, перпендикулярную оси симметрии (оба представленных условия сформулированы для эллипсоидов, полученных в результате применения некоторого аффинного преобразования, приводящего исходные множества к общей осевой симметрии). После введения всех обозначений ставится задача определения условий непустоты и получения аналитического описания множеств во, ві, в , в".
Эллипсоидальное решение задачи синтеза управления при ограниченных координатах
Если det Q ф 0, то эллипсоид называется невырожденным, иначе — вырожденным. Каждый невырожденный эллипсоид {а, Q) является множеством уровня некоторой положительно определенной квадратичной формы, а именно (а, Q) = lev/C(-), где () = (" I а) Q l) Є Кп. В связи с этим, множество уровня неотрицательно определенной квадратичной формы можно рассматривать как обобщение понятия эллипсоида. Поэтому множества вида lev/Co( ), где /Со(-) Є К, будем называть "обобщенными эллипсоидами". Итого, можно выделить следующие классы эллипсоидальных множеств:
Классы эллипсоидов Е И обобщенных эллипсоидов Е являются различными расширениями класса невырожденных эллипсоидов Еп в том смысле, что Еп = Е П Е. Одним из основных свойств каждого из представленных классов является инвариантность относительно любого невырожденного аффинного преобразования: Утверждение 1.1. Для любого Т(-) = Т{ \Ь7А) Є Т„ выполняется Доказательство. Представленные равенства обосновываются следующим образом: Введем обозначения для декартовых произведений классов Е„ и Е : jn :— cjn х лп J» := Е« х Е Элементами каждого из введенных пространств являются всевозможные пары соответствующих эллипсоидальных множеств. Элементы, состоящие из пересекающихся эллипсоидов, можно условно назвать "связными" (coherent). Среди последних отдельно можно выделить элементы, представляющие собой вложенные (nested) или равные (equal) множества. Для упрощения использования данной терминологии, удобно ввести следующие обозначения. Для любого пространства М Є { J„, J } определим Определение 1.2. Эллипсоид Є Є Вп будем позывать гарантированной внешней (внутренней) эллипсоидальной аппроксимацией или оценкой множества Лі Є 2R", если MQ (Є С М). Среди всех эллипсоидальных оценок особый интерес представляет класс неулучшаемых или недоминируемых оценок. Определение 1.3. Внешняя (внутренняя) эллипсоидальная аппроксимация Є Є Е„ множества Лі Є 2R" называется недоминируемой, если для любой оценки Q Є En, такой что Лі Cf0Cf { С So С Лі), выполняется равенство Q = Є. Недоминируемость является основной качественной характеристикой любой эллипсоидальной оценки, однако проверка наличия данного свойства требует, как правило индивидуального подхода в каждом отдельном случае. Данная работа имеет дело с методами эллипсоидального оценивания различных операций над эллипсоидами, то есть отображений из М С Jn в convRT1. Примерами подобных операций могут служить алгебраическая сумма, геометрическая разность, объединение и пересечение эллипсоидов. Определение 1.4. Методом внешнего (внутреннего) эллипсоидального оценивания отображения :Ми convR", определенного на множестве М С J„, будем называть совокупность объектов {ft, , ЛГШ}, состоящую из семейства аппроксимирующих отображений {Хш : М - Еп и) ї}, множества параметризации ї произвольной природы и правила выбора области допустимых значений параметра Е ; Мн 2п, таких что для любых J Є М й и (,7") ф 0 выполняется ( AJ) С Т(3) ) При этом метод оценивания будем называть "качественно удовлетворительным", если A jr) является недоминируемой оценкой для F(S) при всех ш Є 2(ёГ), и "количественно удовлетворительным", если имеет место предельное представление ( нj) = сіиі-ияі єад} ) Замечание 1,1. Отметим, что для корректного задания метода каждое аппроксимирующее отображение Хи достаточно определить на множестве элементов (J Є М, таких что и Є (.7). Представленная формализация применима для описания всех используемых и разрабатываемых в последующих разделах методов эллипсоидального оценивания. В качестве примера рассмотрим метод внешнего оценивания суммы эллипсоидов, описаний в работе 38]. В формализованом виде обозначеный метод записывается как {n5+,S5+, SJ"}, где Qs+ = (0, оо), а отображения 5+ : Jn »-» 2R и 5J" : J„ н-» Е„ определяются для любых (i, 2} Є Jn, где Si = (щ, Q{) Є En (г = 1,2), по правилу Доказательство. Наличие свойства недоминируемости у представленных оценок и воз можность представления суммы эллипсоидов в виде пересечения всех оценок данного семейства доказываются в [38].
Внешнее оценивание объединения (концентрический случай)
В данном разделе демонстрируется использование методов внутреннего эллипсоидального оценивания для решения задачи синтеза упровления на терминальное множество. Рассмотрим динамическую систему с дискретным временем, фазовое состояние х(к) которой подчиняется линейному рекуррентному уравнению:где и(А:) — управление, удовлетворяющее ограничениям
Будем предполагать, что на траектории системы (1.27) наложены фазовые ограниченияОпределение 1.6. Задача синтеза управления на терминальное множество ЛЛ 2Rn состоит в построении множества начальных состояний \У[к\ = W(&o, к\,ЛІ) и определении для каждого х Є Rrt многозначной стратегии U(k,x) С V(k), таких что любая последовательность {х{к) Є R"} , удовлетворяющая включениям не нарушает фазовых ограничений (1.29) и достигает, в конечный момент времени ki терминального множества ЛА, то есть х{к\) Є ЛЛ.
В данном разделе будет предложен алгоритм построения частного решения задачи синтеза управления, основанный на использовании методов внутреннего эллипсоидального оценивания, при следующих предположениях
Отметим, что только в случае У(к) = R, то есть когда фазовые ограничения отсутствуют, можно гарантировать существование решения задачи синтеза управления на любом временном интервале. В общем случае, поставленная задача может и не иметь решения или иметь бесконечное множество решений. В связи с этим нашей целью будет нахождение любого из возможных решения. Для избежания работы с пустыми множествами, далее будем предполагать, что решение поставленной задачи существует. А для начала найдем одно конкретное решение, у которого множества W[Aio] и U(k,x) максимальные до включению. Заметим, что в рекуррентных формулах, которые будут получены далее, не учитывается конкретный вид множеств Т{к),У(к) и Л4, что позволяет использовать их и в общем случае. Определение 1.7. Множеством разрешимости линейного рекуррентного уравнения (1.27) при условиях (1.28) и (1.29) будем называть совокупность всех векторов х у Є R 1, для которых существуют множества Ы{к7х) С (&) такие, что любая последовательность {x(k),k Є [fco i]}i удовлетворяющая включениям и начальному условию x(ko) = XQ, не нарушает фазовых ограничений (1.29) и достигает в момент времени кх терминального множества М, то есть х(к ) є Л4. Через W [A;] = W (k, кі,М) обозначим множество разрешимости рассматриваемой задачи. Нетрудно убедиться в справедливости следующего утверждения Лемма 1.11. Множество W [A] состоит из всех векторов XQ R", для которых существует последовательность управляющих векторов и(к) Є "Р(к), к Є [ко, к\ — 1], такая что решение рекуррентного уравнения (1.27) с начальным условием х(кц) — Ха не нарушает фазовых ограничений (1.29) и удовлетворяет включению x(ki) Лі. Замечание 1.3. Фактически, лемма 1.11 дает альтернативное определение множества разрешимости W \k\. Отметим, что эквивалентность двух данных определений является следствием отсутствия неопределенности, то есть отсутствия в уравнении (1.27) неконтролируемых, заранее неизвестных параметров (помех). Из последнего утверждения следует, что множество W [A;] состоит из всех векторов х(к) У (к), для которых существует вектор и(к) є V(k) такой, что Отсюда вытекает рекуррентная формула для W [&]: Искомая максимальная стратегия Ы {к, х) должна обеспечивать включение чтобы гарантировать выполнение х(кі) Є W [fci] = М. Пусть дан некоторый х W [fc]. Тогда множество U (k,x) состоит из таких векторов и(к) Є V(k), для которых справедливо включение А(к)х + и(к) Є W [k + 1]. Отсюда Формулы (1.31) и (1.32) полностью решают задачу синтеза управления, однако ими трудно пользоваться на практике. Далее займемся построением эллипсоидального решения задачи синтеза управления, то есть решения, для которого W[fco],W(A,a;) Е„. Фиксируем некоторые, вообще говоря произвольные, методы внутреннего эллипсоидального оценивания для суммы и пересечения эллипсоидов:
Внутреннее оценивание пересечения
Доказательство. Так как любые две положительно определенные квадратичные формы приводимы одновременно к главным осям при помощи некоторого невырожденного линейного преобразования, то справедливо утверждать, что для произвольного элемента ()) Є J„ существует аффинное преобразование То(-) Тп, такое что %{Єі) = {а, Q), %{&) = {0, Е), где
Если A; \j{i ф j) для всех itj = 1,пг, то 7о(-) является искомым преобразованием. В противном случае, для некоторых 1 її 12 тп выполнено Ajj = АІ2 . Рассмотрим Т(-) = Т(7о(-) 0, Л) Є Т„, где матрица А = {aij}j=i определяется по правилу Положим p = arctan —-. Тогда e = 0. После выполнения соответствующей перестанов ки координат, получим представление, аналогичное (2.2), но с меньшим количеством ненулевых компонент у вектора а. Последовательное применение подобной процедуры в конечном итоге позволит построить требуемое преобразование. П Представление (2.1) будем называть каноническим для элемента J Є J„. Лемма 2.2. Число к [0,п] в каноническом представлении (2.1) не зависит от конкретного выбора преобразования Т(-) Є Тп, приводящего З Є Jn к этому виду. Доказательство. Предположим противное. Пусть для некоторого элемента (Su 2) Jn существуют преобразования %п{-) Тп (т = 1,2), такие, что Тт(Е{) = (а,п т), Xn{S2) = (0,Е) (т = 1,2), где %{) — ЗгС Ч1)) Є Тп выполняется %{{auQi)) = (oa,Q2), ((0, )) = (0,5), откуда следует, что 7о(-) = Т(-\ 0,А), где А = {ау},_! — ортогональная матрица, удовлетворяющая следующим равенствам Поскольку матрицы Qi 11 — подобны (а значит обладают одним и тем же набором собственных значений), то, без ограничения общности, можно считать, что Aj2 ф Ajj (г ф j), для всех г, j = 1, ki (выполнения этого требования можно добиться, добавив к 72(-) некоторую перестановку координат &2 + 1,...,«). Отсюда следует, что для каждого і = / + 1, п среди элементов {ац,..., a t,} найдется не более одного ненулевого. С другой стороны, наличие ровно одного такого элемента будет противоречить равенству fci J2 kjCji = О, так как все сд ф О (j = 1,ki). Следовательно, a = 0 для всех і = к2+ 1,п j=i и j 1, fci. Нетрудно убедиться, что в этом случае матрица А будет вырожденной, что не совместимо с ее ортогональностью. Пришли к противоречию. D Инварианту к канонического представления (2.1) для элемента J Є Jn далее будем обозначать как asymj" := к, где asym : Ju і— [0, ті]. Лемма 2.3. asym(i,2) = asym(2,i), V (і,г) Jrt. Доказательство. Пусть (fi, з) Є Jrt посредством некоторого преобразования %() Є Т„ приводятся к виду (2.1). Тогда (гіі) Є Jn можно привести к аналогичному виду при помощи преобразования Т(%(-) \ Ь, А) Є ТП) где n-fc Л АГ1 2} , Ь= (-АГ1/ЭС1,...,-Л Ч,бГ?Э) . Отображение asym задает отношение эквивалентности на множестве J„. При этом J„ = (J {Jn, k = 0, п}, где J fc — классы эквивалентности, определяемые как Jn,fc := { 7Є Jn I asymj" = A} k = Q,n Замечание 2.1. В практическом плане полезно иметь в виду, что Зп п плотно в Зп. Наиболее простой структурой обладают классы Jn o и Jn,i. Лемма 2.4. Пусть J = (і,з) Є J„, где 6І ( ц,Qi) Є Еп (і = 1,2), и при этом Qi(ai — 02) = {ІІ{Щ — а2) ф 0 (г = 1,2). Тогда asym ,7 = 1. Доказательство. Без ограничения общности положим а2 = 0. Фиксируем произвольную U К"4", такую что UU = Е а 1/аг = (а, 0,..., 0) . Не сложно проверить, что UQiV = W Pi Далее, обозначим через D Ri" 1)x(n_1) такую невырожденную матрицу, для которой DPiD = diag{Ai}?-l1, DPaD = Е. Тогда преобразование Т(-1AU, 0) Є Т„, где приводит эллипсоиды \, f2 к требуемому каноническому виду. Лемма 2.5. Пусть J = (і,2) Є Jn, где І = ( ii,Qi) Є En (г = 1,2). Тогда Доказательство. Первый пункт утверждения очевиден. Остановимся на втором пунк те. Прежде всего отметим, что представленное свойство коллинеарности инвариантно относительно невырожденного афинного преобразования и тривиально проверяется для канонического вида любого элемента J Є Jn, такого что asym J = 1. Таким образом, необходимость (=-) доказана. Для доказательства обратного утверждения ( =) доста точно убедиться, что Qi \ и Q [ 2 удовлетворяют условиям леммы 2.4. D Таким образом, класс ЛП]о состоит из всех пар концентрических эллипсоидов, а класс J„,i объединяет все пары неконцентрических эллипсоидов І = {щ, Qi) Є Е„ (і = 1,2), таких что для некоторого Т() Є Т„ множества Т{і),Т{2) одновременно обладают осевой симметрией относительно прямой afF{T(oi), Т(аг)}. Последнее свойство можно рассматривать как осевую симметрию "в широком смысле" (то есть с точностью до некоторого невырожденного аффинного преобразования).
