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

Московский государственный университет им. М.В. Ломоносова

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

01.01.07 — прикладная математика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

Важенцев Андрей Юрьевич

Москва 2004 г.

Работа выполнена в Московском государственном университете им. М.В. Ломоносова на кафедре системного анализа факультета Вычислительной математики и кибернетики.

Научный руководитель: доктор физико-математических наук,

академик РАН А.Б. Куржанский.

Официальные оппоненты: доктор физико-математических наук,

Защита состоится 1 декабря 2004 года в 1530 на заседании диссертационного совета Д 501.001.43 при Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в научной библиотеке им. A.M. Горького Московского государственного университета им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус.

Автореферат разослан_октября 2004 г.

Ученый секретарь

профессор Ф.П. Васильев;

доктор физико-математических наук, профессор М.И. Гусев.

Ведущая организация:

Институт проблем управления РАН.

диссертационного совета, профессор

Е.В. Захаров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Исследование динамических систем с неопределенностью является одним из наиболее востребованных направлений современной математической теории. Особое внимание уделяется проблемам оценивания в задачах управления и наблюдения. Результаты, полученные в этой области, находят приложения в различных областях человеческой деятельности, таких как автоматизация, робототехника и телекоммуникация. Классические задачи оценивания основаны на предположении, что статистические характеристики возмущений параметров системы известны. Однако во многих приложениях такое описание неопределенности не является адекватным в силу отсутствия достаточного количества экспериментальных данных или их статистической неустойчивости. По этой причине, начиная с 60-х годов прошлого столетия, в рамках теории гарантированного оценивания развивается альтернативный подход, связанный с предположением об ограниченности неопределенных параметров модели некоторыми известными множествами. Разработка основ теории связана с именами Н.Н. Кра-совского [3], А.Б. Куржанского [4], X. Витзенхаузена [19], Ф. Швеппе [17], Д. Бертсекаса [11]. В рамках этого направления, используя теорию множеств, выпуклый и многозначный анализ, удается получить как точные аналитические описания множеств возможных состояний изучаемой системы, так и их гарантированные, то есть внутренние или внешние, аппроксимации в виде множеств канонической формы, таких как многогранники [18], параллелотопы [1] и эллипсоиды [9, 15]. Особой популярностью пользуются эллипсоидальные множества, что в значительной степени обусловлено активным развитием теории так называемого эллипсоидального исчисления, в рамках которой проводится разработка методов гарантированного эллипсоидального оценивания для результатов различных операций над эллипсоидами. Существенный вклад в изучение эллипсоидальных методов для задач динамики принадлежит С. Бойду [12], А.Б. Куржанскому [15,16], Ф.Л. Чер-ноусько [9] и их ученикам. Самыми востребованными (в плане оценивания) операциями над эллипсоидами в настоящее время являются алгебраическая сумма и геометрическая разность, которые активно используются в процессе исследования задач управления и наблюдения для линейных динамических систем с эллипсоидальными ограничениями на неизвестные параметры [9, 15]. Однако не меньший интерес вызывает проблема оценивания пересечения эллипсоидов, которая возникает в частности в задачах наблюдения в условиях неопределенности [2] или управления при наличии фазовых ограничений [15]. Отметим, что, в то время как первый класс задач обычно связан с построением внешних оценок, для второго

ЮС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С О»

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

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

Основные результаты работы.

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

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

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

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

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

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

Методы исследования. Рассматриваемая в диссертации проблема внутреннего оценивания, а также дополнительные требования относительно количественных и качественных свойств искомого решения, являются непосредственным продолжением и развитием идей, заложенных в теории эллипсоидального исчисления [15]. Также в работе активно применялись методы линейной алгебры, математического анализа, теории матриц и матричных преобразований [5], а также выпуклого анализа [6].

Апробация работы. Результаты работы были представлены в виде докладов на семинарах кафедры системного анализа факультета ВМиК МГУ (рук. А.Б. Куржанский), кафедры оптимального управления факультата ВМиК МГУ (рук. Ф.П. Васильев), института проблем управления РАН (рук. Б.Т. Поляк), а также на следующих конференциях:

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

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

Публикации. По теме диссертации опубликовано 3 работы.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и библиографии. Общий объем диссертации составляет 126 страниц. Библиография включает 52 наименования.

Краткое содержание работы. Во введении формулируются основные цели работы, обосновывается ее актуальность, дается обзор литературы по альтернативным методам оценивания, а также приводится краткое описание глав. Постановка задачи начинается с определения класса (невырожденных) эллипсоидов Еп = {£(а, О) | а € Я", ф = 0! > 0}, где

= {жеЯ" | (х-а>Я-\х-а)) < 1}.

Далее для произвольной бинарной операции вводится

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

ДЦб.й) с ?(£и£г) (или &(£!,&) 2 ), V» е П.

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

£2) = с1 и (или ?(£и £2) = Пп Ха(£ъ£2)).

После этого ставится задача построения качественно и количественно удовлетворительного метода внутреннего эллипсоидального оценивания пересечения эллипсоидов.

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

Для произвольной пары различных эллипсоидов = г € {1,2}

определяется класс

2аъа2{£ъ€2) = {х € Я." | ахК^х) + а2Щх) < 1}, К,г(х) = (ж-йь^^ж-а,)), ¿€{1,2}

и числовая характеристика £2) = тт{/С1(х) | К2(х) = 1}.

Теорема 1 Если т^а П £2) Ф 0, то эллипсоид £~ — ¿Гаьа2(£1; £2), где

1-Е-

<*г = -Я = тт( 1, /Апт^г, £з-г)), г € {1,2}

I — £Х£2

является налучшей в своем классе внутренней оценкой £\ Л £2, то есть

^ф£~С£1П£2 и £~ Э£, У£е2(£и£2) : £С£1Г)£2.

Отметим, что задачу внутреннего оценивания пересечения можно свести к задаче внешнего оценивания объединения эллипсоидов, воспользовавшись тем, что для любого в € 1гЛ(£1 П £2) ф 0 поляры (£\ — в)° и (£2 — в)" также являются эллипсоидами, удовлетворяющими соотношению

для любого эллипсоида бщ, такого что 0 € При этом для двойственной

задачи оценивания существует решение в классе 2(£\,£2). Ключевую роль играет числовая характеристика ¿¿шахС^ь^г) = тах-^К^х) | К2{х) = 1}.

Теорема 2 Эллипсоид £+ = 2аиа2(£1,£2), где

а,- = ——, иц = тах( 1, ¿¿тахСй, £3-1)), ¿€{1,2} I — и)\Ш2

является наилучшей в своем классе внешней оценкой £\ и £2, то есть <Ьф£+Э£1и£2 и £+С£, У£е£(£1,£2) : £ Э£хи£г

Совместное использование (1) и теоремы 2 позволяет в конечном итоге получить из единственной внешней оценки £д Э (£\ ~ в)° и (£2 — в)0 бесконечное семейство различных внутренних оценок за счет неод-

нозначности выбора 9 € т1(£1 Л £2). Ни один из полученных внешних или

Рис. 1; Единичные оценки вида £~ С £1 П £2 и £+ Э £1 и £2

Рис. 2: Семейство оценок вида в+ (£})" с£1П£г

внутренних методов оценивания (рис. 1,2) нельзя назвать качественно удовлетворительным, хотя можно заметить, что последний метод, основанный на полярной двойственности, является количественно удовлетворительным.

Практическое использование представленных методов оценивания связано с возможностью эффективного вычисления И Дтах^Ъ^О-Традиционно, численные методы для задач подобного и более общего вида строятся на основе применения так называемой S-процедуры [7, 10]. Однако в данной работе был рассмотрен альтернативный подход, суть которого заключается в использовании специфических свойств однопараметрических семейств внешних оценок суммы и внутренних оценок геометрической разности эллипсоидов, представленных в работе [15]. В результате вычисление

удается свести к одномерной задаче оптимизации. Например, если £\ = £(0, Е), а £2 = £ (о, С}), то

ре[1,7]

тах Ег^Атах(аа/ — р<2),

если 7 > 1 если 7 = 1

НЫпРиЬ) =

тах ^Лщь (<? - р аа'),

оРИ.тгЧ *

если 0 < 7 < 1

если 7 = 0 если 7 > 0 если 7 = 0

где 7 = (а, ф 1а), а Ат^А) и Ат^А) — соответственно минимальное и максимальное собственные значения симметричной матрицы А.

Во второй главе рассматривается вопрос о том, в какой мере можно "улучшить" двойственную задачу внешнего оценивания (£i~— 0)° за счет выбора 6 € int(£i П£г) в соотношении (1). Критерием качества является "симметрия взаимного расположения." В основе лежит утверждение

Теорема 3 Для любых {81,82) 6 Е„ х Е„ найдутся Ъ е R" и А е R"xn (det Л ф 0), такие что A£í + b = 5(0, Е), А82 + Ь = 8{a, Q), где

а = (с1)...,с*,0,...)0)', Q = diag{A¿}t"=1, a ¿o, Xi^Xjiijtj), Vi,je[i,¿). {¿>

Отметим, что число к в представлении (2) однозначно определяется парой (¿•Ь^г)) и в данной работе обозначается как asym(£i,£"2) = к. При этом случай к — 0 соответствует концентрическим эллипсоидам, а А; = 1 — эллипсоидам, которые с точностью до некоторого аффинного преобразования обладают осевой симметрией относительно прямой, проходящей через их центры. Таким образом, возможность приведения {£\ — в)0 U (£2 _ 0)" к центральной или осевой симметрии связана с изучением множеств где

Поэтому данная глава посвящена условиям непустоты и аналитическому описанию множеств ©о, ©i, а также подмноже£Гв§с^язанного с дополнительным (помимо осевой симметрии) условием на (£i — 9(£¡ — интерпретируемым как отсутствие "строгой сравнимости по включению" проекций на ось симметрии (причины введения ©Í станут видны чуть ниже).

Оказалось, что для конкретных £¿ = £(a,i,Qi), i G {1)2} {z = a\ — a<ij, строение ©о И ©i тесно связано со свойствами следующих матриц

А именно, имеют место следующие взаимно однозначные соответствия:

0eRn h= (а1Гб)GRn+1

в € intfo п 82) {h,nih)<0, (h,Ü2h)< 0

0е©о Ь, является собственным вектором

0e©i к лежит в двумерном инвариантном подпространстве П1'Пг и при этом не является собственным вектором

Отсюда было получено аналитическое (качественное) описание ©о, ©г- В частности, если азут^!,^) = П, то в случае своей непустоты множество

во состоит из единственной точки, а Эх — из совокупности открытых отрезков с концами н а д£и д£2- Если ая^п^е^г) м п, то ©д ©1 у т иметь (но не обязательно имеют) более сложное строение.

Далее выяснилось, что наличие свойства непустоты ©о, ©1 и ©^ однозначно определяется расположением корней некоторой функции /(•), определенной для всех комплексных тг, таких что г £ 1т(<Э1 — тгфг)) по правилу

Было выделено 4 случая, которые связаны с ©о,©1,©1 следующим образом

функция /(•) имеет...

только простые вещ. корни комплексные корни корень кратности 2 корень кратности 3

к & 0

©о = 0

©1^0 ©1 = 0

©'х = 0 ©! = ©1^0

Каждый случай в таблице проиллюстрирован конкретной парой эллипсоидов из с дополнительными построениями в виде точек и прямых линий, которые соответствуют собственным векторам и двумерным инвариантным подпространствам! О^Пг- Таким образом, для получения ©о, ©1 и ©^ достаточно пересечь вспомогательные множества С 'пЛ(£1 П£г)-

В целом из представленной схемы вытекает, что единственным случаем, не допускающим приведения ни к одному из рассмат-

риваемых видов симметрии является наличие у /(•) корня кратности 3. Во всех остальных случаях одно (и только одно) из множеств ©о ИЛИ ©^ не пусто. Однако, при этом в работе показывается, что если /(•) имеет корень кратности 3, то конкретные £1,82 можно как угодно точно приблизить другой парой эллипсоидов, для которых /(•) уже будет иметь только простые вещественные корни.

Третья глава посвящена построению недоминируемых внутренних эллипсоидальных оценок для: SiCiSi. В основе лежит рассмотрение двойственной задачи оценивания (Е\ — в)" U (£2 — ДЛЯ в G ©о U ©i (при условии ©oU©i ф 0). При этом акцент делается на получении качественно и количественно удовлетворительного решения, что в силу (1) гарантирует наличие аналогичных свойств у решения исходной задачи. Напомним, что для выпуклого компакта Л4 G 2Rn внутренняя (внешняя) оценка £ £ Еп называется недоминируемой, если она является максимальной (минимальной) по включению среди всех возможных эллипсоидальных оценок. При этом в работе показывается, что достаточным условием недоминируемости является

dim со(д£ ПдМ) =п & 3{х{ед£ПдМ- афф. нез. (3)

Конкретно, в случае ©о 0 получаем задачу удовлетворительного внешнего оценивания объединения концентрических эллипсоидов.

Теорема 4 Пусть £i = £(а, Qi), i £ {1,2}. Тогда, если Q2 — Qi имеет ровно т € [1, п — 1] положительных собственных значений, то семейство эллипсоидов £$ = £(а, Ql + (Q2 - Qi)VV'(Q2 - Qi)), V € V, где

V = {V G Rnxm I V\Q2 - Qi)V = E}

качественно и количественно удовлетворительно оценивает co(£j U £2), то есть f") £у = Co(£i U £2), и при этом для всех £у выполняется (3).

С другой стороны, для случая ©^ ^ 0 в работе приводится аналитическое описание некоторого непустого подмножества 0" С такого что при всех

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

Таким образок, в общем случае (за исключением наличия у корня кратности 3) проблема построения внутренних недоминируемых оценок для

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

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

Рис. 3: Семейство внешних недоминируемых оценок для (¿1—0)° и (£г— в случае, когда в е 0О ^ 0 (слева) и л&£(©1 (5 а в а ) .

Рис. 4: Семейство внутренних недоминируемых оценок для ^П^ в случае, когда /(•) имеет только простые вещ. (слева) или комплексные (справа) корни.

Список цитируемой литературы

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

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

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

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

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

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

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

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

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

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

[И] Bertsekas D.P., Rhodes I. В. Recursive state estimation for a set-membership description of uncertainty // IEEE Trans. Autom. Control. 1971. Vol.16. №2. P.117-128

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

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

[14] Kurzhanski А.В., Fihppova T.F. On the theory of trajectory tubes — a mathematical formalism for uncertain dynamics, viability and control // Advances in Nonlinear Dynamics and Control: A Report from Russia. PSCT 17. Boston-Basel-Berlin: Birkhauser, 1993. P. 122-188.

[15] Kurzhanski A.B, Valyi I. Ellipsoidal Calculus for Estimation and Control. Boston-Basel-Berlin: Birkhauser, 1997.

[16] 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

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

[18] 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

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

Публикации по теме диссертации

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

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

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

Издательство ООО "МАКС Пресс". Лицензия ИД № 00510 от 01.12 99 г. Подписано к печати 25.10.2004 г. Формат 60x90 1/16. Ует печ л. 1,0. Тираж 100 экз. Заказ 1077. Тел. 939-3890,939-3891, 928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М В. Ломоносова. 2-й учебный корпус, 627 к.

24850

л

е

а Сп

ЧJ

Содержание и

Введение

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

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

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

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

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

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

Заключение

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