Внутренние эллипсоидальные оценки в задачах динамики и управления тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Важенцев, Андрей Юрьевич

• Важенцев, Андрей Юрьевич
• кандидат физико-математических наук
• 2004

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

Содержание и

Введение

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

1 Внутреннее оценивание пересечения эллипсоидов при помощи линейной свертки квадратичных форм

1.1 Формализация методов оценивания.

1.2 Линейная свертка квадратичных форм и ее использование в оценивании пересечения.

1.3 Связь методов оценивания пересечения и объединения.

1.4 Численная реализация методов оценивания.

1.5 Эллипсоидальное решение задачи синтеза управления при ограниченных координатах

2 Классификация пересечения эллипсоидов

2.1 Основные определения.

2.2 Множество ©о.

2.3 Множество ©х.

2.4 Множество ©^.

2.5 Множество 0".

2.6 Классификация.

3 Недоминируемые внутренние оценки пересечения эллипсоидов

3.1 Достаточное условие недоминируемости.

3.2 Внешнее оценивание объединения (концентрический случай).

3.3 Внешнее оценивание объединения (случай осевой симметрии).

3.4 Внутреннее оценивание пересечения.

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

Исследование динамических систем с неопределенностью является одним из наиболее востребованных направлений современной математической теории. Особое внимание уделяется проблемам оценивания в задачах управления и наблюдения. Результаты, полученные в этом направлении, находят приложения в различных областях человеческой деятельности, таких как автоматизация, робототехника и телекоммуникация. Классические задачи оценивания основаны на предположении, что вероятностные возмущения параметров системы известны, или по крайней мере известны их статистические характеристики, такие как математические ожидания или ковариационные матрицы. Однако, во многих приложениях статистическое описание не является полным или адекватным в силу отсутствия достаточного количества экспериментальных данных или их статистической неустойчивости. По этой причине, начиная с 60-х годов прошлого столетия, в рамках теории гарантированного оценивания развивается альтернативный подход, связанный с предположением об ограниченности неопределенных параметров модели некоторыми известными множествами. Разработка основ теории связана с именами H.H. Красовского [11], А.Б. Куржанского [12], X. Витзенхаузена [52], Ф. Швеппе [48], Д. Бертсекаса и И. Родэса [23]. Дальнейшее развитие данный метод получил в работах [18, 31, 38, 41] и многих других. В последнее время также проявляется интерес к моделям со смешанной неопределенностью [5] и почти произвольными помехами [4].

Отметим, что в рамках направления гарантированного оценивания, используя теорию множеств, выпуклый и многозначный анализ, зачастую удается получить точные аналитические описания множеств возможных состояний изучаемой системы. Однако, как правило, эти множества имеют очень сложную структуру. Поэтому не меньший интерес вызывает задача построения для них гарантированных, то есть внутренних или внешних, аппроксимаций в некотором классе множеств канонической формы, описываемых конечным числом параметров. К наиболее используемым на практике классам множеств можно отнести многогранники [35, 42, 51], параллелотопы [7, 8, 9, 26] и эллипсоиды [18, 38]. Особой популярностью пользуются эллипсоидальные множества в силу гладкости границы, наглядности и удобства численной реализации. Расширение использования эллипсоидального подхода в оценивании в немалой степени связано с развитием теории так называемого эллипсоидального исчисления. Данный термин был впервые введен в работе [38] для обозначения совокупностей методов построения гарантированных эллипсоидальных оценок для результатов различных операций над эллипсоидами. Существенный вклад в изучение эллипсоидальных методов для задач динамики принадлежит С. Бойду [25], А.Б. Куржанскому [38,40], Ф.Л. Черноусько [18] и их ученикам. В процессе развития в эллипсоидальном исчислении оформились два основных подхода к оцениванию. Первый (см. [18]) основан на построении единственной аппроксимации, по возможности обладающей теми или иными оптимальными свойствами, в качестве которых могут использоваться объем эллипсоида, сумма радиусов эллипсоида и многие другие. Второй (см. [38]) предполагает описание бесконечного семейства оценок, объединение или пересечение которых совпадает с оцениваемым множеством. Последнее требование мотивировано естественным стремлением наделить метод оценивания свойством неограниченного повышения точности аппроксимации за счет рассмотрения все большего и большего количества эллипсоидов. При этом, как правило, неоднозначность оценки компенсируется требованием недоминируемости, то есть максимальности или минимальности по включению, каждой оценки семейства. Важно отметить, что в рамках второго подхода также остается возможность выделения в семействе оценок конкретных представителей, удовлетворяющих перечисленным выше критериям оптимальности.

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

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

Исторически первым подходом к оцениванию пересечения эллипсоидов было использование различных алгоритмов построения двусторонних эллипсоидальных оценок выпуклого компактного множества М = {х € | /Дя) < 0, г = 1,т}, где /¿(-) — некоторые выпуклые функции, такие что хт&М. ф 0. Результатом применения таких х + т\Е С М С х + r2£ (х е intМ, г2 > гх > 0 ) где £ является эллипсоидом с центром в начале координат. При этом обязательным свойством является независимость отношения гг/гх от оцениваемого множества. Впервые подобные оценки были получены в работах [29, 32], где в качестве х + рассматривался минимальный по объему описанный эллипсоид, для которого были доказаны существование и единственность среди всех внешних эллипсоидальных оценок множества Л4. Там же было показано, что из такого эллипсоида, который в западной литературе получил название Lowner-John ellipsoid, можно получить и внутреннюю оценку, положив гг/п = п. Отметим, что для случая m > 1 непосредственное вычисление внешней минимальной по объему эллипсоидальной оценки является довольно сложной в вычислительном плане процедурой. Поэтому в ряде работ, таких как [46], предлагается использование более простого алгоритма, обеспечивающего отношение гг/гх = у/п{п + 1). Альтернативой построению "наилучшей внешней оценки" является построение "наилучшей внутренней оценки". Так, если в качестве х+г\£ взять максимальный по объему вписанный эллипсоид, то парная внешняя оценка будет удовлетворять условию гг/^х = п. Данный подход применительно к пересечению эллипсоидов приводит к задаче выпуклой оптимизации с ограничениями в виде линейных матричных неравенств [25], для которой разработано много эффективных численных методов. Еще одну довольно многочисленную группу составляют "методы аналитического центра", в основе которых лежит использование логарифмической штрафной тп функции <р(х) = — 1п(—fi(x)). Данный подход был впервые предложен в работах 1 б, 34, 49] для оценивания многогранников, и в дальнейшем был обобщен на случай множеств более общего вида [24, 30, 43, 50]. Все методы, относящиеся к данной группе, тесно связаны с построением так называемого эллипсоида Дикина, который для каждой точки z £ intМ определяется как £\z] = {х € Rn | (х — z, H(z)(x — z)) < l}, где H{z) = V2<p(z). В работе [43] доказывается, что в случае, когда все /Д-) являются выпуклыми квадратичными функциями, для любого z G intM. выполняется включение z] С М- При этом в качестве внутренней аппроксимации (х + г\£) обычно берут эллипсоид £ [ж*], где х* = arg min у? (ж) является аналитическим центром рассматриваемой x€int М системы неравенств. Соответствующее этому эллипсоиду отношение гг/п, позволяющее строить внешние оценки, не зависит от размерности пространства п и однозначно выражается через количество ограничений т. Конкретное значение отношения было неоднократно пересмотрено в сторону улучшения в целом ряде работ. Последний из известных автору результатов, полагающий Г2/Г1 = т, представлен в работе [27].

Помимо универсальных алгоритмов двухстороннего оценивания, существуют также специализированные методы для получения исключительно внешних или внутренних эллипсоидальных оценок пересечения. Более богатым в этом плане является внешнее оценивание. Например, в работе [25] приводятся (в терминах линейных матричных неравенств) достаточные условия для параметров эллипсоида, описанного вокруг пересечения заданных эллипсоидов. Последнее позволяет использовать эффективные численные методы оптимизации для получения единичных представителей, обладающих оптимальными свойствами. Однако наибольшее распространение получил подход, т при котором внешние оценки для П где Ei = {х € Rn | (х — a^QTl{x — а<)) < 1} >=1 г = 1 ,т), ищутся в виде множеств уровня линейной свертки квадратичных форм: = {х £ Rn | f>f(x - Oi, Qr1(x - ъ)) < l}, cti > 0 (г = 1~m) m m

Не трудно проверить, что при условии = 1 выполняется включение f) £{ С £+. i <=i Среди первых работ, в которых использовались подобные оценки, можно назвать [33] и [47]. К сожалению, данный подход в определенных случаях может порождать весьма неудовлетворительные аппроксимации, в связи с чем были разработаны альтернативные методы. Так, в [17] и [36] задача внешнего оценивания пересечения эллипсоидов сводится к внешнему оцениванию суммы эллипсоидов при помощи включения т т

Г) ¿ч С М\£\ Н-----1- Мт£т, Mi е Rnxn, =

1=1 i= 1 что в конечном итоге позволило в [38] построить бесконечное семейство внешних оценок пересечения (в том числе и достаточно приемлемых), допускающее представление оцениваемого множества в виде пересечения всех аппроксимаций. С другой стороны в

18] для случая гп = 2 было продемонстрировано использование алгоритмического подхода, допускающего последовательное итерационное улучшение внешней оценки. Суть идеи заключается в предварительном мажорировании эллипсоида большего объема полупространством или множеством вида {ж € Кп | с\ < (х, Ь) < С2} и последующем оптимальном внешнем эллипсоидальном оценивании эллиптического сегмента или слоя, применяя известные явные аналитические формулы.

Среди специализированных методов внутреннего оценивания пересечения, можно отметить один интересный подход, представленный в работе [38]. В его основе лежит сведение внутреннего оценивания пересечения эллипсоидов £\ П £2 С К™ к внутреннему оцениванию суммы эллипсоидов удвоеной размерности при помощи представления

1п£2 = {хе11п\(*) е^ + ^ся2"}, где £* С К2л является вырожденным эллипсоидом, опорная функция которого равна (¿ = 1,2),

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

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

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

Перейдем к описанию основных результатов диссертации.

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

В первом параграфе определяется класс невырожденных эллипсоидов £(а, и его традиционные обобщения. Вводится понятие гарантированной эллипсоидальной оценки множества и условие ее недоминируемости. В заключение дается формальное определение метода эллипсоидального оценивания как совокупности конкретных математических объектов, а также оговариваются условия "качественной и количественной удовлетворительности" метода, используемые в работе. Первое условие связано с требованием недоминируемости порождаемых аппроксимаций, а второе — с наличием достаточного количества оценок для получения предельного представления оцениваемого множества в виде их объединения или пересечения.

Во втором параграфе для каждой пары эллипсоидов (<?1, £2) определяется класс £2) множеств уровня всевозможных линейных сверток соответствующих квадратичных форм. После этого доказывается утверждение о существовании в 2>{£\, £2) единственной неулучшаемой (в своем классе) внутренней оценки пересечения £\ П £2- В результате производится построение универсального способа оценивания пересечения эллипсоидов, основанного на решении экстремальной задачи вида тт{/С:(л;) | К^х) = 1} для некоторых смещенных квадратичных форм ¡С^-), К.2(-)■

В третьем параграфе устанавливается связь методов внутреннего оценивания пересечения и внешнего оценивания объединения эллипсоидов. Описывается способ сведения первой обозначеной задачи оценивания ко второй при помощи полярной двойственности. Для того, чтобы иметь возможность воспользоваться данной техникой, требуется предварительно научиться оценивать объединение эллипсоидов £\ и £2 снаружи. Поставленная задача полностью решается в классе 2(£1,£2), при этом доказывется утверждение о существовании среди элементов £2) единственной неулучшаемой (в своем классе) оценки, параметры которой выражаются через решение экстремальной задачи вида шах{/С1(х) | /Сг(ж) = 1} для смещенных квадратичных форм /С^-), /Сг^)-Использование полярной двойственности в конечном итоге позволяет получить из единственной внешней оценки объединения бесконечное семейство различных внутренних оценок пересечения эллипсоидов за счет неоднозначности выбора точки, принимаемой за новое начало координат при осуществлении перехода к полярам. Кроме того, интересно отметить, что полученный метод оценивания пересечения является, в отличие от построенного ранее, "количественно удовлетворительным", то есть допускает представление оцениваемого множества в виде замыкания объединения всех оценок семейства.

Четвертый параграф полностью посвящен численной реализации предложенных методов оценивания. В центре внимания находится решение возникающих задач квадратичной оптимизации при квадратичных ограничениях. Изучению задач данного и более общего вида посвящено множество работ, среди которых [22, 27, 28, 44]. В основе построения большинства соответствующих численных методов лежит использование так называемой Б-процедуры. Данный термин был впервые предложен в работе [21] для описания необходимых и достаточных условий неотрицательности одной квадратичной функции на множестве векторов, для которых неотрицательными являются одна или несколько других. Доказательство большинства основных результатов в этой области принадлежит В.А. Якубовичу и его ученикам (см. [15, 16, 19, 20]). Однако в данном разделе рассматривается альтернативный подход, в основе которого лежит использование специфических свойств однопараметрических семейств внешних оценок суммы и внутренних оценок геометрической разности эллипсоидов, представленных в работе [38]. В результате удается свести все поставленные многомерные экстремальные задачи к одномерным задачам отимизации на конечном отрезке, допускающим эффективное численное решение.

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

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

В первом параграфе второй главы обозначенный критерий классификации формализуется для фиксированной пары пересекающихся эллипсоидов (£1,£г) в терминах пустоты или непустоты множеств 0о, ©1 С П £2), состоящих из всех возможных векторов, полярное отражение относительно которых приводит рассматриваемые эллипсоиды к центральной или осевой симметрии соответственно. Кроме этого, определяются множества ©^ С 61 и ©" С аналогичным образом связанные с дополнительными (помимо осевой симметрии) условиями, накладываемыми на взаимное расположение эллипсоидов, полученных в результате полярного отражения. Для упрощения конкретных формулировок воспользуемся условным термином "строгая сравнимость по включению" для обозначения соотношения между двумя абстрактными множествами, при котором одно из них принадлежит относительной внутренности другого. Тогда, можно сказать, что 0'х добавляет требование, интерпретируемое как отсутствие "строгой сравнимости по включению" проекций эллипсоидов на ось симметрии. В свою очередь 0" дополняет упомянутое требование условием, которое можно аналогично проинтерпретировать как отсутствие "строгой сравнимости по включению" проекций эллипсоидов на гиперплоскость, перпендикулярную оси симметрии (оба представленных условия сформулированы для эллипсоидов, полученных в результате применения некоторого аффинного преобразования, приводящего исходные множества к общей осевой симметрии). После введения всех обозначений ставится задача определения условий непустоты и получения аналитического описания множеств 00,01,0^, ©".

Во втором параграфе рассматривается множество ©о и показывается, что критерием его непустоты для пары £ = (д^) (г = 1,2) является условие отсутствия =

- тгФг)-1* + 7Г"1 - 1, если ае^фх - 7гф2) ф 0

1ш1 /(сг), иначе, где г = ах — а2. Отметим, что областью определения функции /(•) является множество всех комплексных чисел 7Г ф 0, таких что г £ 1т(<2х — 7гф2). Помимо этого устанавливается однозначное соответствие векторов множества ©о определенным собственным векторам матрицы Г^1^ £ к(п+1)х(п+1)) где соответствующим собственному значению я-, такому что /(7г) = 0, /'(я-) < 0.

В третьем параграфе изучается множество ©х- Основным результатом является утверждение о непустоте данного множества для всех пересекающихся эллипсоидов £х ф £2, кроме случая, когда функция /(•) имеет корень кратности 3. Кроме этого показывается связь элементов рассматриваемого множества с некоторыми двумерными несобственными инвариантными подпространствами матрицы что в конечном итоге позволяет получить полное аналитическое описание ©х

В четвертом параграфе доказывается утверждение о том, что ©'х Ф 0 если и только если /(•) имеет комплексные корни или корень кратности 2, и при этом ©'х = ©х-В пятом параграфе выясняется, что критерием непустоты ©'/ является непустота ©х и отсутствие свойства вложенности эллипсоидов друг в друга. При этом дается описание множества ©'х' в терминах корней уравнений /(7г) = 0 и с^(ф^1 — Аф^1) = 0.

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

Целью третьей главы диссертации является разработка метода построения недоминируемых эллипсоидальных аппроксимаций пересечения эллипсоидов, основанного на классификации пересечения, представленной во второй главе. Используя обозначенную в первой главе двойственность задач оценивания пересечения и объединения эллипсоидов, исходная задача построения внутренних аппроксимаций пересечения не вложенных друг в друга эллипсоидов в большинстве случаев (кроме оговоренного исключения) сводится к задаче внешнего оценивания объединения эллипсоидов, удовлетворяющих либо требованию концентричности (если ©о ф 0), либо расширенному требованию наличия осевой симметрии (если 0'/ ф 0). Следовательно, для достижения поставленной в данной главе цели достаточно научиться оценивать снаружи (недоминируемым образом) только обозначеные случаи объединения эллипсоидов.

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

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

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

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

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

Результаты диссертации отражены в публикациях [1, 2, 3], а также представлены в виде докладов на следующих конференциях:

• международная конференция студентов и аспирантов по фундаментальным наукам "Ломоносов-2000" (Москва, МГУ, апрель 2000 г.)

• школа-семинар молодых ученых факультета ВМиК МГУ им. М.В. Ломоносова (Дубна, октябрь 2001 г.)

Автор выражает признательность своему научному руководителю Александру Борисовичу Куржанскому за постановку задачи и полезные критические замечания.

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

• R — поле вещественных чисел.

• С — поле комплексных чисел.

• 2м — семейство всех подмножеств множества Л4.

• äff .М — аффинная оболочка множества М. £ 2Rn.

• со Л4 — выпуклая оболочка множества М. G 2R".

• с\М. — замыкание множества М. G 2R".

• intAI — внутренность множества М. G 2Rn.

• ri М = {х € М | 3 В £ 2Rn : х 6 int В, В П äff М С М} — относительная внутренность множества М. G 2R".

• дМ — граница множества М. € 2Rn.

• conv Rn — пространство непустых выпуклых компактов в R". . R2+ = {(аьа2) € R2 | а1)£*2 > 0}\{(0,0)}.

• Q' € Спхт — матрица, транспонированная по отношению к матрице Q € СтХп.

• = {Q е Rnxn | Q — Q'} — симметричные матрицы.

• Sn = (Q G S°n | det Q ^ 0} — симметричные невырожденные матрицы.

• posS° = {Q € S° | Q > 0} - неотрицательно определенные матрицы. altS° = {S G S° | S £ pos —S & posS°} — знакопеременные матрицы.

E = diag{l,., 1} — матрица тождественного преобразования.

WV(Q) = ker(Q — ттЕ) — собственное подпространство матрицы Q G Rnxn, соответствующее значению 7г G R.

Ilxlls = (xi Sx) — значение квадратичной формы с матрицей S € в точке х G R71.

К{х | с, S) = \\х — с\\2а — значение смещенной квадратичной формы с центром с G R™ и матрицей S G в точке х 6 R".

К° = {£(•1 с, S) | се Rn, S G pos S° } — пространство смещенных неотрицательно определенных квадратичных форм.

Кn = {/С(-1 с, S) | с G Rn, S G posSn} — пространство смещенных положительно определенных квадратичных форм.

Т(х | Ь,А) = Ах + Ъ — аффинное преобразование вектора х G Rn, задаваемое матрицей A G Rnxn и вектором Ь G R".

Т„ = {Т(-1 Ь,А) | be Rn, A G Rnxn, det А Ф 0} — пространство невырожденных аффинных преобразований в R™. lev /(•) = {х G Rn | f(x) < 1} — множество уровня функции / : R™ •—► R. р{£ | М) = sup{{^, в) | в G М} — значение опорной функции множества М G 2R" в направлении £ G R".

Q* G Cnxm — матрица, псевдообратная к матрице Q G СшХп. Псевдообратная матрица однозначно определяется требованиями a) (QiQ)'=:QiQ, (QQ1)' = QQ* b) QQiQ = Q, QtQgt = Qt

1'±{Я) € [0, п] — число положительных(+) или отрицательных(—) собственных значений матрицы <3 € 8° (с учетом кратности)

•^тт(Ф) — минимальное собственное значение матрицы ф € Б®. тах(<5) — максимальное собственное значение матрицы ф € Б®.

Агтп(С?1|Ф2) — минимальный корень уравнения ёе^фх — Афг) = 0, где <2ъ <3г £ 8П.

АтахС^Фг) — максимальный корень уравнения А<52) = 0, где <5г С

М.\—Мг = {а; 6 Нп | х + М.г С М.\\ — геометрическая разность множеств М1,М2е2в-п. а>\1| а,2 — вектора ах, а2 € И" коллинеарны. £»-> £ — линейный оператор, полученный из оператора, соответствующего матрице А € 11"Хт\ путем индуцирования (то есть сужения области определения) на линейное подпространство С С И", инвариантное относительно А. а]4 £ К — значение г-ой компоненты вектора а С И". m стр. обозначения параметры

19 £{a,Q) o € Rn, Q € pos

19 Е„, Е°, Е~

20 т т°°

20 cohj, cohM, coh0M Je Me{J„, J~}

20 nestM, eqM M6{J„, J~}

22 ZS+(J), S+{J) J e J„, w e R

22 L„

23 ZA(J), Z{J) <7 e A e R\

24 J € coh weR

24 /^min( J")

28 1Z~(J) J" € cohJ~

30 M° Л1 € convR"

32 Je J„

34 JeJn

36 П*-, Jf-(J) J € coh Jn, 0€Rn

46 J G coh J„, w G

46 íí5", «SJ(^) стр. обозначения параметры

53 asym J7" J еЗп

53 J п,к к G [0, n]

55 A p{i,j) J G Jn, t G Rn

55 nil njH tij, tij JeJn

55 T v T" "i" Jn.o, Jti,l» Jn,l> Jn,l

55 V V" Je Jn

56 J-в, J° J" G Jn, 0 € Rn

57 pol J, pol-1 M J e coh Jn, M с J„

57 6fcl ©i, ©i' J" G coh Jn, A; G [0, п.]

57 Co

57 Ki{e) 0G Cn, ie {1,2}

57 am. Qm ÍGRn, ¿€{1,2}

58 V, Ai, Л2

58 G. 7Г € С

58 Ш 7Г G С

60 Поо

60 7Г G С

61 ©0) ©0) тт G R

67

67 Ah A, WO, Hi

68 fir TT G R

69 По, Пх

69 0GR", i,je{i.2}

70 ©X

71 Q, cl©x|Q

73 £*(тг) 7Г G R

85 <S0(Q), 5o(Q)

89

90

92 coh(fe>Jn fc G {1,2,3,4}

94 coh* Jn Ш стр. обозначения параметры

100 UZ>P, UT TeRmxp, m,p«E N, m + p<n,

103 W (Q)

104 Q0+, S0+(J), U${J) j e Jn>0, w € s°

108 Z(у\у'% Zk{y\y") Л €{1,2,3}

108 ЫУ') y' e R2, * €{0,1,2,3}

109 G{sus2,sz)t Gíip) «1,S2,S3 € R, г G {1,2}

109 ш°(р), ^(рьрг) P,Pl,í>2 € R

109 P, P¡, Pi ¿€{1,2}

109 Z2, 4 к €{1,2,3}

109 vi vt A €{1,2,3}

111 Í21+, E^ÍJ), U\+w{3) J e J'h, С € R3, T^eS»

111 ЭД, Qi[C], %] CeR3, »€{1,2}

113 S^U), wp1+(,7) J € J«!, p € R

116 J e coh* J„, 9 G Rn, С € R3, W e

116 ,7 e coh*J2, We s®, pe R

Заключение диссертации по теме «Вычислительная математика», Важенцев, Андрей Юрьевич

Основные результаты данной диссертации следующие:

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

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

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

Заключение

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

1. Важенцев А.Ю. О внутренних эллипсоидальных аппроксимациях для задач синтеза управления при ограниченных координатах // Известия РАН: Теория и системы управления. 2000. №3. С.70-77

2. Важенцев А.Ю. Проблема внешнего эллипсоидального оценивания объединения двух концентрических эллипсоидов и ее приложения // Прикладная математика и информатика: Труды фак. ВМиК МГУ им. Ломоносова. 2003. №14. С.18-34

3. Важенцев А.Ю. О внутреннем эллипсоидальном оценивании состояния динамической системы на основе наблюдения с помехой. // Вестник МГУ, серия 15: "Вычислительная математика и кибернетика". 2004. №2. С.26-32

4. Граничин О.Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах, М.: Наука, 2003

5. Дигайлова И.А. Задача фильтрации со смешанной неопределенностью // Изв. РАН: Теория и системы управления. 2001. №5. С. 16-24

6. Дикин И. И. Итеративное решение задач линейного и квадратичного программирования // Доклады АН СССР. 1967. т.174. №4. С.747-748

7. Костоусова E.K. О полиэдральном оценивании областей достижимости линейных многошаговых систем // АиТ. 1997. №3. С.57-68

8. Костоусова Е.К. Внешнее и внутреннее оценивание областей достижимости при помощи параллелотопов // Вычисл. технологии. 1998. т.З. №2. С.11-20

9. Костоусова Е.К., Куржанский А.Б. Гарантированные оценки точности вычислений в задачах управления и оценивания // Вычисл. технологии. 1997. т.2. №1. С. 19-27

10. Кощеев A.C., Куржанский А.Б. Адаптивное оценивание эволюции многошаговых систем в условиях неопределенности // Известия АН СССР: Техническая кибернетика. 1983. т. С.72-93

11. Красовский H.H. Игровые задачи о встрече движений. М.: Наука, 1970.

12. Куржанский А.Б. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977

13. Ланкастер П. Теория матриц. М.: Наука, 1978.

14. Рокафеллар Р. Выпуклый анализ. М., Мир, 1973.

15. Фрадков А.Л. Теоремы двойственности в некоторых невыпуклых экстремальных задачах // Сибирский математический журнал. 1973. т. 14. №2. С.357-383

16. Фрадков А.Л., Якубович В.А. S-процедура и соотношение двойственности в невыпуклых задачах квадратичного программирования // Вестник ЛГУ, серия "Математика". 1973. №1. С.81-87

17. Хонин В.А. Гарантированные оценки состояния линейных систем с помощью эллипсоидов // Эволюционные системы в задачах управления Свердловск: Уральский научный центр АН СССР, 1985. С. 104-123.

18. Черноусъко Ф.Л. Оценивание фазового состояния динамических систем. М., Наука, 1988.

19. Якубович В.А. S-процедура в нелинейной теории регулирования // Вестник ЛГУ, серия "Математика". 1971. №1. С.62-77

20. Якубович В.А. Минимизация квадратичных функционалов при квадратичных ограничениях и необходимость частотного условия в квадратичном критерии абсолютной устойчивости нелинейных систем управления / / Доклады АН СССР. 1973. т.209. №5. С. 1039-1042

21. Aizerman М.А., Gantmacher F.R. Absolute stability of regulator systems // Information Systems, Holden-Day, San Francisco, 1964.

22. Ben-Tal A., Teboulle M. Hidden Convexity in Some Convex Quadratically Constrained Quadratic Programming Problems // Mathematical Programming. 1996. Vol.72. P.51-63

23. Bertsekas D.P., Rhodes LB. Recursive state estimation for a set-membership description of uncertainty 11 IEEE Trans. Autom. Control. 1971. Vol.16. №2. P.117-128

24. Boyd S., Ghaoui L.E. Method of centers for minimizing generalized eigenvalues // Linear Algebra and Applications, special issue on Numerical Linear Algebra Methods in Control, Signals and Systems. 1993. №188. P.63-111

25. Boyd S., Ghaoui L.E., Feron E., Balakrishnan V. Linear Matrix Inequalities in System and Control Theory, Society for Industrial and Applied Mathematics, 1994

26. Chisci L., Garulli A., Zappa G. Recursive State Bounding by Parallelotopes, Preprint, Univ.Firenze, 1995.

27. Fu M., Lou Z.-Q., Ye Y. Approximation algorithms for quadratic programming // Journal of Combinatorial Optimization. 1998. JV«2. P.29-50

28. Golub G. H., Von Matt U. Quadratically Constrained Least Squares and Quadratic Problems // Numerische Mathematik. 1991. Vol.59. P.561-580

29. Grötschel M., Lovdsz L., Schrijver A. Geometric Algorithms and Combinatorial Optimization, Vol.2 of Algorithms and Combinatorics. Springer-Verlag, 1988

30. Jarre F. Optimal ellipsoidal approximations around the analytic center, Technical report, Intitüte für Angewandte Mathematik, University of Würzburg, 8700 Würzburg, Germany, 1993

31. Jaulin L., Kieffer M., Didrit 0., Walter E. Applied interval analysis. London: SpringerVerlag, 2001

32. John F. Extremum problems with inequalities as subsidiary conditions //In J. Moser, editor, Fritz John, Collected Papers. Birkhauser, Boston, Massachussetts. 1985. P.543-560

33. Kahan W. Circumscribing an ellipsoid about the intersection of two ellipsoids // Canad. Math. Bull. 1968. V.U. №3. P.437-441.

34. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. №4. P.373-395

35. Kuntsevich V.M., Lychak M. Guaranteed Estimates, Adaptation and Robustness in Control Systems, Lect. Notes in Contr.Inf.Sci., V.169, Springer-Verlag, 1992.

36. Kurzhanski A.B. On evolution equations in estimation problems for systems with uncertainty. Luxenburg: International Institute for Applied Systems Analisis, WP-82-48, 1982.

37. Kurzhanski A.B, Valyi I. Ellipsoidal Calculus for Estimation and Control. Boston-BaselBerlin: Birkhauser, 1997.

38. Kurzhanski A.B., Varaiya P. Ellipsoidal techniques for reachability analysis: internal approximation // System & Control Letters, 2000. №41. C. 201-211

39. Kurzhanski A.B, Varaiya P. On Ellipsoidal Techniques for Reachability Analysis. Part I: External Approximation, Part II: Internal Approximations. Box-valued Constraints // Optimization Methods and Software. 2002. Vol.17. P. 177-237

40. Matasov A.I. Estimators for uncertain dynamic systems. Boston: Kluwer, 1999.

41. Milanese M., Norton J., Piet-Lahanier H., Walter E., eds. Bounding Approaches to System Identification, Plenum Press, 1995.m

42. Nesterov Yu., Nemirovsky A. Interior-point polynomial methods in convex programming, Vol.13 of Studies in Applied Mathermatics, SIAM, Philadelphia, PA, 1994

43. Polyak B.T. Convexity of Quadratic Transformations and its Use in Control and Optimization // Journal of Optimization Theory and Applications. 1998. Vol.99. №3. P.553-583

44. Rockafellar R., Wets R. Variational Analysis, ser. Grundlehren der Mathematischen Wissenschaft. Springer-Verlag, 1998

45. Sabharwal A., Potter L. Set Estimation via Ellipsoid Approximations: Theory and Algorithms // IEEE Transactions on Signal Processing. 1997. №45. P.3107-3112

46. Schweppe F.C. Recursive state estimation: unknown but bounded errors and system inputs // IEEE Trans. Automat. Control. 1968. V.AC-13. №2. P.22-28.

47. Schweppe F.C. Uncertain dynamic systems. Englewood Cliffs, N.J.: Prentice Hall, 1973

48. Sonnevend G. An analytic center for polyhedrons and new classes of global algorithms for linear (smoth convex) programming // Lecture Notes in Control and Information Sciences, Berlin: Springer-Verlag. 1985. Vol.84. P.866-876

49. Sonnevend G., Stoer J. Global Ellipsoidal Approximations and Homotopy Methods for Solving Convex Analytic Programs // Applied Mathematics & Optimization. 1990. V.21. №. P. 139-165.

50. Walter E., Piet-Lahanier H. Exact recursive polyhedral description of feasible parameter set for bounded-error models // IEEE Trans. Autom. Contr., 1989. Vol.34. №8. P.911-915

51. Witsenhausen H.S. Sets of possible states of linear systems given perturbed observations // IEEE Trans. Autom. Contr. 1968. Vol.13. №5, P.556-558