LMI-подход к синтезу разреженных регуляторов в линейных системах управления Быков Алексей Витальевич

Содержание к диссертации

Введение

1 Линейные матричные неравенства. Обзор методов получения разреженности 13

1.1 Развитие аппарата линейных матричных неравенств 13

1.2 Разреженные представления и 1-оптимизация 18

1.3 Синтез разреженных регуляторов 23

1.4 Выводы по главе 35

2 Разреженные регуляторы в линейных системах дискретного времени 37

2.1 Введение 37

2.2 Задача стабилизации 38

2.3 Оптимальное управление 42

2.4 Численные эксперименты 53

2.5 Выводы по главе 60

3 Невыпуклый детектор матричной разреженности 61

3.1 Введение 61

3.2 Строчная матричная разреженность 63

3.3 LMI-подход в задачах управления: -оптимизация 67

3.4 Поиск разреженной структуры 70 3.5 Численные примеры 72

3.6 Выводы по главе 77

4 Аппроксимации матричной 0-квазинормы: численные исследования эффективности 78

4.1 Введение 78

4.2 Синтез разреженных регуляторов в задачах оптимального управления 80

4.3 Аппроксимации матричной 0-квазинормы 84

4.4 Результаты численных экспериментов 90

4.5 Выводы по главе 101

Заключение 102

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

• Разреженные представления и 1-оптимизация
• Оптимальное управление
• LMI-подход в задачах управления: -оптимизация
• Аппроксимации матричной 0-квазинормы

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

Актуальность темы исследования. Идея разреженности (англ. sparsity) естественным образом возникает в самых разнообразных областях науки в задачах, предполагающих наличие неединственного решения. Неединственность решения может возникать из-за того, что переменных в задаче больше, чем ограничений. Простым примером такой задачи является недоопределенная система линейных уравнений, которая при условии разрешимости имеет бесконечное множество решений. Не обладая дополнительной информацией, невозможно определить в таком случае, какое решение среди всех будет наиболее «правильным».

Во многих прикладных исследованиях среди большого множества решений, как правило, выбирают те из них, которые содержат как можно больше нулевых компонент; такие решения и называют разреженными. Например, в биологическом эксперименте, измеряя изменение в уровне экспрессии 30 000 генов, часто ожидают, что уровень экспрессии изменится не более, чем в паре сотен из них. В области обработки сигналов особый интерес представляют разреженные сигналы, так как их можно точно восстанавливать даже по набору наблюдений, не удовлетворяющих классическому критерию – теореме Котельникова (в англоязычной литературе – теорема Найквиста-Шеннона). Таким образом, в некотором смысле наиболее простое решение – содержащее как можно больше нулей – часто оказывается наиболее «правильным». Кроме того, разреженные представления позволяют уменьшить количество хранимой и передаваемой информации, что является их несомненным преимуществом.

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

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

Одними из первых еще в конце 1970-х к ₁-оптимизации прибегали ученые, занимавшиеся сейсмологической разведкой методом отраженных волн. Первые строгие результаты были получены в конце 1980-х в работах Д. Донохо (D. Donoho) и Ф. Старка (P. Stark); дальнейшие идеи сформулированы в работах Р. Тибширани (R. Tibshirani), Л. Ванденберге (L. Vandenberghe), С. Бойда (S. Boyd), Э. Канде (E. Candes), М. Фазэл (M. Fazel), Дж. Троппа (J. Tropp), А. М. Брукштейна (A. M. Bruckstein), Т. Тао (T. Tao), О. Н. Граничина, А. И. Ма-тасова, П. А. Акимова. Среди многочисленных приложений ₁-оптимизации стоит упомянуть прикладную статистику (LASSO-регуляризация), машинное обучение (борьба с переобучением и отбор признаков), алгоритмическую торговлю (оптимизация портфеля активов при наличии транзакционных издержек), теорию графов (построение разреженных графов), направление в области исследования сигналов – compressed sensing (восстановление сигнала по предыдущим значениям, которые разрежены или сжаты). Идеи compressed sensing получили дальнейшее развитие в областях сжатия данных, цифровой фотографии, обработки медицинских снимков.

В теории управления при построении стабилизирующих регуляторов также может возникнуть желание получать нулевые элементы, но уже в матрице усиления регулятора, построенного в форме статической линейной обратной связи. Такие регуляторы с большим количеством нулевых элементов называют разреженными; подобная структура позволяет, например, строить распределенные системы с децентрализованным управлением. Способы синтеза подобных регуляторов обсуждаются в работах Ф. Лина (F. Lin), М. Фардада (M. Fardad), М. Р. Йовановича (M. R. Jovanovic), Н. К. Дингры (N. K. Dhingra), А. Хассиби (A. Hassibi), С. Бойда (S. Boyd), Ф. Вольфрума (P. Wolfrum), У. Мюнца (U. Munz), Д. Зеласо (D. Zelazo), С. Шулер (S. Schuler), Ф. Альгёвера (F. Allgower). В некоторых работах перечисленных авторов разреженная структура оговаривается заранее, в других – основной акцент сделан на оптимизационных алгоритмах, таких как метод обобщенного лагранжиана (англ. augmented lagrangian method) и его

модификации, например, метод переменных направлений множителей Лагранжа (англ. alternating direction method of multipliers, ADMM); исследуются вопросы сходимости и реализации методов для разных задач оптимального управления. Все упомянутые работы объединяет искомая структура разреженности: она, как правило, поэлементная, то есть не важно, как расположены друг относительно друга нулевые элементы в матрице усиления регулятора, важно их количество. Стоит отметить, однако, что встречаются обобщения и на случай блочной нулевой структуры.

Иная структура разреженности представлена в работах Б. Т. Поляка, М. В. Хлебникова, П. С. Щербакова – ставится задача построить регулятор, в матрице усиления которого как можно больше нулевых строк или столбцов. Мотивация получения подобной структуры диктуется желанием ослабить требования к аппаратной реализации систем управления. Например, наличие нулевых строк позволяет не использовать при построении управления соответствующие этим нулевым строкам компоненты вектора управления, то есть снизить число требуемых для управления приводов (англ. actuator). Авторы развивают подход к синтезу подобного рода регуляторов, заключающийся в замене исходной задачи минимизации невыпуклого целочисленного функционала – числа ненулевых строк или столбцов – на ее выпуклое приближение. Для этого вводятся специальные матричные нормы, аппроксимирующие матричные ₀-квазинормы, которые по определению равны числу ненулевых строк или столбцов матрицы. Стоит отметить, что не удается сформулировать строгие теоретические результаты, гарантирующие наличие разреженности в матрице регулятора, однако представлены эвристические соображения, дающие основания для использования подхода; эффективность подхода проверяется на численных примерах.

Развиваемый подход существенно опирается на аппарат линейных матричных неравенств (англ. linear matrix inequalities, LMI), предполагающий сведение задач управления к задачам полуопределенного программирования (англ. SemiDefinite Programming, SDP). Основы использования LMI в рамках теории управления были заложены в работах А. М. Ляпунова, А. И. Лурье, В. Н. Постникова. В дальнейшем LMI-подход был развит в работах Р. Э. Калма-на (R. E. Kalman), В. А. Якубовича, В. М. Попова (V. M. Popov), Я. Виллемса

(J. Willems), Е. С. Пятницкого, В. И. Скородинского, С. Бойда (S. Boyd). Одним из явных преимуществ применения техники LMI является возможность распространения подхода на случай робастных постановок задач управления. В настоящее время техника линейных матричных неравенств остается популярной, в том числе среди отечественных авторов. Аппарату LMI посвящена монография Д. В. Баландина и М. М. Когана – первая книга об LMI на русском языке, а также работы представителей нижегородской школы: Д. В. Баландина, М. М. Когана, Л. Н. Кривдиной, А. А. Федюкова, П. В. Пакшина, В. В. Поздяева. Техника исследования линейных систем управления, опирающаяся на аппарат LMI, а также на концепцию инвариантных эллипсоидов, развивается в статьях и в монографии Б. Т. Поляка, М. В. Хлебникова и П. С. Щербакова.

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

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

1. Синтез разреженного управления в задаче стабилизации для систем с дискретным временем.

1. Синтез разреженного управления в задаче LQR для систем с дискретным временем.

2. Анализ неэффективности выпуклых приближений и поиск альтернативных аппроксимаций матричной ₀-квазинормы для обнаружения разреженной структуры.

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

4. Численное исследование эффективности различных аппроксимаций матричной ₀-квазинормы.

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

Соответствие шифру специальности. Работа соответствует шифру специальности 05.13.01 и охватывает следующие области исследования, входящие в специальность: п. 2. Формализация и постановка задач системного анализа, оптимизации, управления, принятия решений и обработки информации; п. 4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации.

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

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

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

На защиту выносятся следующие положения:

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

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

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

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

5. На основании результатов численного моделирования сделаны выводы об эффективности различных приближений матричной ₀-квазинормы в разреженных постановках задач управления.

Степень достоверности и апробация результатов. Результаты диссертационной работы докладывались и обсуждались на семинарах лаборатории №7 ИПУ РАН, 55-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» (г. Долгопрудный, 2012), XII Всероссийском совещании по проблемам управления – ВСПУ-2014 – (г. Москва, 2014), XXII международной конференции по автоматическому управлению «Автоматика 2015»

(г. Одесса, 2015), 12^th IFAC International Workshop on Adaptation and Learning in Control and Signal Processing (г. Эйндховен, Нидерланды, 2016). Возможность применения результатов работы обсуждалась на международном симпозиуме по новым методам диагностики и лечения в медицине (International Symposium of New Advances in Medical Diagnosis and Treatment, Huazhong University of Science and Technology, г. Ухань, Китай, 2015).

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

Публикации. Основные результаты опубликованы в 7 научных работах, среди которых 2 статьи – в рецензируемых изданиях из списка, рекомендованного ВАК.

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 111 страницах, содержит 12 иллюстраций. Библиография включает в себя 126 наименований.

Разреженные представления и 1-оптимизация

Большинство задач поиска разреженных представлений возникает в моделях, где требуется найти разложение исследуемого объекта по некоторому базису, который, как правило, состоит из большого числа линейно зависимых элементов. Такие модели и соответствующие им системы линейных уравнений называют недоопре-деленными (англ. underdetermined) или избыточными (англ. redundant, overcomplete). С одной стороны, подобные модели значительно повышают точность представления объекта [65; 100], с другой – встает вопрос выбора конкретного представления среди бесконечного множества решений недоопределенной системы. Один из популярных подходов – выбирать в некотором смысле самый простой вариант – разреженный, – то есть такой, в котором как можно больше нулевых элементов. Целесообразность поиска именно разреженных решений может быть обусловлена различными соображениями, например: В некоторых случаях априори известно, что исследуемый объект может быть представлен в виде линейной комбинации лишь небольшого числа базисных векторов. Если принимать во внимание вопросы вычислительной сложности, то чем бо лее разреженное представление имеет объект, тем меньше элементарных операций требуется для его восстановления. В задачах сжатия данных уменьшение количества используемых компонент базиса позволяет снизить количество хранимой информации. Некоторые исследователи ссылаются, несмотря на его «античность» [57], на известный методологический принцип «Бритва Оккама», который в одной из многочисленных форм гласит: «Не следует множить сущее без необходимости». Задачи поиска разреженных представлений являются трудными из-за невыпуклости и дискретности минимизируемого функционала – числа ненулевых компонент вектора; строгое доказательство NP-сложности подобных задач приводится в работах [54; 92]. Несмотря на это, было опубликовано большое число работ, предлагающих эвристические алгоритмы получения разреженных решений, которые можно разделить на следующие группы:

1. Методы полного перебора (англ. brute-force methods). Такой подход хоть и гарантирует нахождение глобального оптимума, с ростом размерности становится не применим на практике из-за экспоненциальной асимптотической сложности. Более изощренные вариации полного перебора, такие как метод ветвей и границ, не дают особого выигрыша в производительности, поэтому их применение на практике также сомнительно [90].

2. Байесовские методы. Данный подход основывается на предположении, что коэффициенты линейной комбинации, описывающей разложение объекта по базису, являются случайными переменными с априорным распределением специального «разреженного» вида. Далее наблюдения объекта используются для оценки апостериорных вероятностей, после чего отбирают наиболее удачные модели. Теоретических результатов, гарантирующих нахождение разреженного решения, для такого подхода не получено [84; 90; 103].

3. Некоторые исследователи разработали специальные численные средства нелинейного программирования, напрямую использующие, например, методы внутренней точки для получения разреженных представлений [101]; при этом гарантируется только локальная сходимость.

4. Жадные алгоритмы (англ. greedy algorithms). Известный подход, заключающийся в нахождении последовательности локально оптимальных решений при попытке получить решение, не сильно уступающее решению исходной задачи. Есть примеры как успешного применения данного подхода [52; 67; 73; 117], так и крайне неудачного [49; 55]. Подробно класс подобных методов в контексте разреженности изучен в монографии А. Миллера (A. Miller) [90] и работе В. Н. Темлякова [114].

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

Именно подход, основанный на использовании выпуклого приближения числа ненулевых компонент вектора, получил широкую известность и уже несколько десятилетий успешно применяется в различных прикладных задачах [49; 83; 97; 107; 111; 113]. Наиболее часто в качестве аппроксимации векторной 0-квазинормы (числа ненулевых элементов вектора) выбирают векторную 1-норму; такая замена дает название популярному подходу – «1-оптимизации».

История применения 1-нормы для получения разреженных представлений бе-20 рет свое начало в 1979 году, когда в своей работе Г. Тейлор (H. Taylor), С. Бэнкс (S. Banks) и Дж. МакКой (J. McCoy), развивая идеи более ранней работы Дж. Клэр-бу (J. Claerbout) и Ф. Мьюира (F. Muir) [51], предложили использовать 1-норму для восстановления данных сейсмологической разведки [113]. В течение следующего десятилетия этот подход был развит, чтобы лучше учитывать шум, присутствующий в наблюдениях [107]; появлялось все больше экспериментальных подтверждений эффективности использования 1-нормы. Строгие теоретические результаты стали появляться в конце 1980-х в работах Д. Донохо (D. Donoho), Ф. Старка (F. Stark) и Б. Логана (B. Logan) [59; 60], в которых более детально изучена способность 1-методов восстанавливать разреженные сигналы.

К середине 1990-х список приложений 1-оптимизации пополнился благодаря предложенному Р. Тибширани (R. Tibshirani) LASSO-алгоритму (англ. least absolute shrinkage and selection operator) [115], позволяющему эффективно осуществлять отбор переменных при регрессионном анализе. В численных методах гармонического анализа появляется понятие «выбор базиса» или «отыскание базиса» (англ. basis pursuit) [49], связанное с получением разреженного представления сигнала в избыточном базисе (англ. overcomplete dictionary); похожая техника под названием «минимизация полной вариации» (англ. total variation minimization) была предложена в области обработки изображений [41; 102].

Оптимальное управление

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

В работе [98] был представлен подход к синтезу разреженных регуляторов, идейно восходящий к h-оптимизации. Исходную невыпуклую постановку было предложено заменить на выпуклое приближение путем введения специальных матричных норм, которые играют роль выпуклых аппроксимаций числа ненулевых строк или столбцов матрицы. Например, для получения строчно-разреженной матрицы предлагается использовать следующую норму:

Минимизируя такую норму при ограничениях, имеющих вид линейных матричных неравенств, можно ожидать появления нулевых строк в матрице-решении. Предложенная в [20; 98] схема получила признание по ряду направлений: обобщения для нелинейных моделей [50], численные процедуры (ADMM) [56] и пр. Однако статья [98] и другие близкие работы [62; 63; 75; 86; 87] относятся в непрерывному времени; цель данной главы - осуществить переход к дискретному времени на примере задач стабилизации и оптимального управления (синтез LQ-регулятора) в разреженной постановке.

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

Рассмотрим систему, описываемую линейным векторным разностным уравнением Xk+i = Axk + Biik- (2.1) Здесь к - дискретное время, х Є Шп - состояние системы, и Є Шр, р п - управление, которое ищется в виде статической линейной обратной связи по состоянию ик = Кхк, К Є Шрхп, (2.2) матрицы А Є Rnxn, В Є Шпхр считаются известными, а пара (А, В) - управляемой. Задача заключается в отыскании матрицы усиления К такой, что замкнутая система Xk+i = AcXk-, Ас = А + ВК устойчива с заданной степенью устойчивости, определяемой как минимальное из расстояний от собственных значений \\{АС)\ 1 до единичной окружности, то есть 1 — max Aj = 1 — р; матрица К имеет нулевые строки, то есть является строчно-разреженной.

Требование шуровской устойчивости матрицы замкнутой системы эквивалентно существованию положительно-определенного решения Р - 0 дискретного матричного неравенства Ляпунова АСРАТС - Р - 0 (см., например, [21]); с учетом желаемой степени устойчивости оно приобретает вид АСРАС — р Р - О, который получается заменой Ас на . Подставляя в полученное неравенство выражение для матрицы замкнутой системы Ас, получим: (А + ВК)Р{А + К В ) — р Р - 0. Воспользуемся тем, что Р = PI = РР 1Р, где / - единичная матрица, того же размера, что и Р; предыдущее неравенство примет вид: (А + ВК)РР Р(А + К В ) — р Р - О, или (АР + ВКР)Р (РА + РК В ) — р Р - 0.

Матричные переменные Р и К входят в полученное неравенство нелинейно; введем вспомогательную переменную Y = КР, тогда неравенство преобразуется к виду: (АР + BY)P (PA +Y В ) — р Р - 0. (2.3) Далее нам потребуется результат, который будет неоднократно использоваться на протяжении всей работы. Этот результат позволяет приводить нелинейные матричные неравенства к эквивалентному линейному виду Приведем его в следующей формулировке [21]: Лемма 3 (Лемма Шура). Пусть / 11 12 \ , ч , ч п/г I I (Z ТП)уп+т)х(п+т) где М11 = MJ Є Rnxn, М12 Є Rnxm, М22 = М2Т2 є Жтхт. Тогда М у- 0 ч= М22 - 0, М11 — М12М22 М12 У о, М У 0 ч= М11 - 0, М-22 — М М М12 - 0. Применяя лемму Шура к неравенству (2.3), получим эквивалентное линейное матричное неравенство: p АР + BY PAT + YT BT p2P 0. (2.4) Любое решение этого линейного матричного неравенства (решения существуют в силу управляемости пары матриц (А, В)) дает регулятор К = YP l, стабилизирующий замкнутую систему со степенью устойчивости (1 — р). Теперь среди всех таких решений нужно найти строчно-разреженное. Для этого заметим, что, в силу правил матричного умножения, произведение двух матриц имеет по крайней мере те же нулевые строки, что и первый сомножитель:

Поэтому, используя матричную loo-норму в качестве эвристики для получения нулевых строк, будем минимизировать l loo на решениях LMI (2.4). Получаем следующее утверждение: Утверждение 2. В результате решения задачи оптимизации \\Y\\l — min при ограничениях Р РАТ + YT Вт АР + BY р2Р - 0, (2.5) с матричными переменными и можно ожидать наличие нулевых строк у матрицы , а, следовательно, и у полученного регулятора = -1, который при этом обеспечивает заданную степень устойчивости (1 - ) матрице замкнутой системы (2.1) – (2.2).

Приведенный результат позволяет обнаружить те управления, которых оказывается достаточно для стабилизации; эти «активные» входы соответствуют индексам ненулевых строк полученной матрицы усиления . Это удается сделать, так как, как правило, существует много стабилизирующих систему регуляторов: их множество соответствует множеству решений неравенства из задачи (2.5). Таким образом, довольно естественно на множестве допустимых решений искать в некотором смысле оптимальное решение, в данном случае – разреженное.

Численное решение задачи (2.5) может быть легко получено средствами системы MATLAB совместно с пакетом для решения задач выпуклой оптимизации cvx [68] и решателем SDPT3 [116]. При вычислениях строку матрицы считаем нулевой, если ее -норма (максимум среди абсолютных значений элементов строки) меньше некоторого заданного малого 0. После этого, зафиксировав полученную структуру разреженности, следует решить задачу разрешимости (англ. feasibility problem) LMI в (2.5) и получить «точные» значения элементов матрицы разреженного регулятора

LMI-подход в задачах управления: -оптимизация

В данной главе исследуются недостатки матричной 1-нормы, используемой для аппроксимации числа ненулевых строк матрицы усиления в задачах управления, а также предлагается новое приближение для матричной 0-квазинормы – невыпуклый детектор разреженности (англ. Nonconvex Sparsity Detector), NSD. Новая аппроксимация используется для получения разреженных регуляторов в задаче -оптимизации. В заключительной части главы приведены результаты численных экспериментов.

Идея, лежащая в основе подходов, предлагаемых во многих работах на тему разреженности, восходит к хорошо известному наблюдению, согласно которому минимизация 1-нормы вектора при ограничениях, имеющих вид недоопределен-ной системы линейных уравнений, приводит к разреженным решениям – векторам, содержащим малое число ненулевых компонент, иными словами, обладающим малой 0-квазинормой. Эта идея, разнообразные ее применения и многочисленные выводы подробно изложены, например, в [43]. При этом говорят, что 1-норма вектора представляет собой выпуклую аппроксимацию 0-квазинормы вектора. Существуют и другие выпуклые приближения для получения разреженных решений, а в работе [64] (см. также [48]) для решения задачи минимизации ранга матрицы предлагается использовать невыпуклую аппроксимацию в форме логарифма детерминанта (англ. log-det). Было показано, что такая аппроксимация в некоторой степени более эффективна, чем «стандартные» выпуклые приближения. Применительно к задачам управления в работе [87] для поиска разреженных матриц усиления используется похожая аппроксимация в форме суммы логарифмов (англ. sum-of-logs).

В теории управления для поиска строчно-разреженных регуляторов в работах [20; 98] предлагается использовать выпуклую аппроксимацию в виде так называемой матричной 1-нормы; поиск разреженных матриц осуществляется путем минимизации 1-нормы при ограничениях, имеющих вид линейных матричных неравенств, возникающих в постановках задач управления при описании систем в пространстве состояний. Данный подход был протестирован на различных постановках задач управления, в частности, на задаче синтеза линейно-квадратичного регулятора (LQR) в непрерывном времени, и оказался довольно эффективным. С другой стороны, для некоторых задач (с конкретными численными значениями матриц линейной модели) оптимизационной процедуре из подхода [20; 98] не удается сойтись к разреженному решению.

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

Новое приближение относится к классу DC-функций (англ. difference of convex); для минимизации невыпуклой аппроксимации будет применяться процедура CCCP (англ. concave-convex procedure) - хорошо известный численный метод оптимизации такого рода функций. В заключительной части представлены численные примеры, демонстрирующие неспособность «старого» подхода найти разреженную структуру, в то время как новый подход справляется с поставленной задачей.

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

Аппроксимации матричной 0-квазинормы

Как было показано в предыдущих главах, в задачах оптимального управления линейными системами помимо оптимизации целевого функционала может возникать требование разреженности регулятора [85; 87; 91; 126], которое заключается в наличии нулевых элементов в матрице усиления, если регулятор построен по принципу статической линейной обратной связи. Естественно, дополнительное требование к структуре матрицы регулятора неизбежно приводит к ухудшению качества управления, так как таким образом сужается множество допустимых регуляторов, на котором происходит минимизация целевого функционала. Тем не менее, в некоторых задачах требуется искать компромисс между оптимальностью и разреженностью, поэтому разумный проигрыш в значении критерия качества может считаться допустимым. Например, в задаче LQR требование разреженности с одной стороны ухудшает значение квадратичного критерия, связанного с затратами энергии в системе, с другой – позволяет сделать систему более надежной, например, за счет децентрализации управления.

В предыдущих главах подробно обсуждался подход к синтезу строчно-разрежен-ных регуляторов, в основе которого лежит замена исходной трудной задачи на ее приближение с помощью введения выпуклых и невыпуклых величин, выступающих в роли приближений матричной 0-квазинормы (числа ненулевых строк). Использование невыпуклых аппроксимаций, позволяющих в некотором смысле более эффективно получать векторные и матричные разреженные представления, обсуждается, например, в работах [44; 48; 64; 87].

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

Центральными моментами главы являются: адаптация различных приближений матричной 0-квазинормы для достижения матричной строчной разреженности, описание схемы численного эксперимента, а также сравнительный анализ результатов. В ходе эксперимента решались как тестовые задачи, так и задачи, в которых используются линеаризованные модели реальных систем, применялись различные вычислительные средства [68; 112; 116], были адаптированы алгоритмы невыпуклой оптимизации [48; 123]. 4.2 Синтез разреженных регуляторов в задачах оптимального управления

Рассмотрим классическую постановку задачи синтеза оптимального стабилизирующего управления в линейных системах с непрерывным временем. Пусть исследуемая система описывается обыкновенным дифференциальным уравнением и начальным условием: х = Ах + Ви х(0) = хо, (4.1) где x(t) Gln- вектор состояния, u(t) Glp- управление, А Є Rnxn, В Є Rnxp, пара (А, В) управляема. Если матрица А не является гурвицевой, то система (4.1) неустойчива, поэтому управление должно стабилизировать систему. Кроме того, регулятор, как правило, должен минимизировать некоторый целевой функционал на траекториях замкнутой системы. Существуют разные постановки, отличающиеся видом синтезируемого управления; для простоты будем строить управление в форме статической линейной обратной связи по состоянию: и = Кх, К є Шрхп. (4.2)

Далее будем рассматривать задачу синтеза линейно-квадратичного регулятора, при этом отметим, что численный эксперимент, ровно как и лежащий в его основе подход к достижению разреженности, могут быть легко перенесены на случай других задач оптимального управления. В задаче синтеза LQ-регулятора целевой функционал - квадратичный критерий качества - выглядит следующим образом: J = (x Rx + и Su) dt,

(4.3)

где R Є Rnxn и S Є Шрхр - заданные положительно определенные матрицы.

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

Как и в главе 2 при решении задачи LQR для системы с дискретным временем воспользуемся подходом, основанным на применении аппарата линейных матричных неравенств. В [29] показано, что LQ-регулятор можно искать как решение следующей задачи полуопределенного программирования: Задача 1. Пусть Popt, Yopt -решение задачи trP — max при ограничении АР + РАТ + BY + YT Вт Р YT —R l О = О, (4.4) тогда регулятор (4.2) с матрицей К opt — YoptPopt (4.5) стабилизирует систему (4.1), минимизируя при этом функционал (4.3), оптималь ное значение которого определяется выражением J opt = X0 Poptx0- (4.6)

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

Вопрос сравнения регуляторов по квадратичному критерию качества подробно обсуждался в главе 2. Здесь применим подход к оценке проигрыша по критерию качества «в среднем», то есть за основу возьмем соотношения (2.13) - (2.14); иными словами, показателем оптимальности регулятора выступает величина tr P l. Таким образом, величина проигрыша разреженного управления оптимальному «в среднем» равна у = %. (4.7) J opt tr ±0pt В работе [20] предложена схема, позволяющая строить разреженные регуляторы в задачах оптимального управления, в частности, в задаче LQR. На ключевом шаге для обнаружения нулевых строк в матрице регулятора предлагается минимизировать loo-норму, выступающую в роли выпуклого приближения числа ненулевых строк матрицы, то есть невыпуклой матричной /0-квазинормы