Программа оптимизации по сумме квадратов - это задача оптимизации с линейной функцией стоимости и определенным типом ограничения на переменные решения. Эти ограничения имеют форму, заключающуюся в том, что, когда переменные решения используются в качестве коэффициентов в определенных полиномах , эти полиномы должны обладать полиномиальным свойством SOS . При фиксации максимальной степени задействованных многочленов оптимизация по сумме квадратов также известна как иерархия релаксации Лассерра в полуопределенном программировании .
Методы оптимизации по сумме квадратов применялись в различных областях, включая теорию управления (в частности, для поиска полиномиальных функций Ляпунова для динамических систем, описываемых полиномиальными векторными полями), статистику, финансы и машинное обучение. [1] [2] [3] [4]
Проблема оптимизации
Проблема может быть выражена как
при условии
Здесь "SOS" представляет собой класс полиномов суммы квадратов (SOS). Вектор и многочлены приведены как часть данных для задачи оптимизации. Количество- переменные решения. Программы SOS могут быть преобразованы в полуопределенные программы ( ПО ) , используя двойственность в полиномиальной SOS программы и релаксацию для сдержан Полинома оптимизации с использованием положительных полуопределенных матриц , смотрите в следующий раздел.
Двойная задача: полиномиальная оптимизация с ограничениями
Предположим, у нас есть -переменный многочлен , и предположим, что мы хотели бы минимизировать этот многочлен по подмножеству . Предположим, кроме того, что ограничения на подмножество можно закодировать с помощью полиномиальные равенства степени не выше , каждая форма где является многочленом степени не выше . Естественная, хотя обычно невыпуклая программа для этой задачи оптимизации следующая:
при условии:
- , ( 1 )
- ,
где это -мерный вектор с одним элементом для каждого одночлена из степени не более , так что для каждого мультимножества , - матрица коэффициентов многочлена что мы хотим свести к минимуму, и - матрица коэффициентов многочлена кодирование ограничение на подмножество . Дополнительный фиксированный постоянный индекс в нашем пространстве поиска,, добавлен для удобства записи многочленов а также в матричном представлении.
Эта программа обычно невыпуклая, потому что ограничения ( 1 ) не выпуклые. Одна возможная выпуклая релаксация для этой задачи минимизации использует полуопределенное программирование для замены матрицы переменных ранга один с положительно-полуопределенной матрицей : мы индексируем каждый моном размера не более мультимножеством не более индексы, . Для каждого такого монома создадим переменную в программе, и расставляем переменные сформировать матрицу , где - множество вещественных матриц, строки и столбцы которых отождествляются с мультимножествами элементов из по размеру не больше . Затем мы записываем следующую полуопределенную программу в переменных:
при условии:
- ,
- ,
- ,
- ,
где снова - матрица коэффициентов многочлена что мы хотим свести к минимуму, и - матрица коэффициентов многочлена кодирование ограничение на подмножество .
Третье ограничение гарантирует, что значение одночлена, которое встречается несколько раз в матрице, одинаково во всей матрице, и добавляется, чтобы сделать соблюдать симметрии, присутствующие в квадратичной форме .
Двойственность
Можно взять двойник указанной выше полуопределенной программы и получить следующую программу:
- ,
при условии:
- .
У нас есть переменная соответствующий ограничению (где это матрица со всеми нулевыми элементами, за исключением записи, проиндексированной ), действительная переменная для каждого полиномиального ограничения и для каждой группы мультимножеств , у нас есть двойственная переменная для ограничения симметрии . Ограничение положительной полуопределенности гарантирует, что представляет собой сумму квадратов многочленов над : характеристикой положительно-полуопределенных матриц для любой положительно-полуопределенной матрицы , мы можем написать для векторов . Таким образом, для любого,
где мы определили векторы с коэффициентами полинома степени не выше . Это дает доказательство суммы квадратов, что значение над .
Вышеупомянутое также может быть распространено на регионы определяется полиномиальными неравенствами.
Иерархия суммы квадратов
Иерархия суммы квадратов (иерархия SOS), также известная как иерархия Лассерра, представляет собой иерархию выпуклых релаксаций возрастающей мощности и увеличения вычислительных затрат. Для каждого натурального числа соответствующая выпуклая релаксация известна как й уровень или-й раунд иерархии SOS. В1-й тур, когда , соответствует базовой полуопределенной программе или оптимизации по сумме квадратов по многочленам степени не выше. Чтобы расширить базовую программу выпуклости науровень иерархии до -го уровня в программу добавляются дополнительные переменные и ограничения, чтобы программа учитывала полиномы степени не выше .
Иерархия SOS получила свое название от того факта, что значение целевой функции на -й уровень ограничен доказательством суммы квадратов с использованием многочленов степени не выше через дуальное (см. «Двойственность» выше). Следовательно, любое доказательство суммы квадратов, использующее многочлены степени не выше может использоваться для ограничения объективного значения, позволяя доказать гарантии герметичности релаксации.
В сочетании с теоремой Берга это дополнительно означает, что при достаточно большом количестве раундов релаксация становится сколь угодно жесткой на любом фиксированном интервале. Результат Берга [5] [6] утверждает, что любой неотрицательный действительный многочлен в пределах ограниченного интервала может быть аппроксимирован с точностью на этом интервале с суммой квадратов действительных многочленов достаточно высокой степени, и, следовательно, если является полиномиальным целевым значением как функцией точки , если неравенство справедливо для всех в интересующей нас области должно быть доказательство этого факта методом суммы квадратов. Выбор чтобы быть минимумом целевой функции по допустимой области, мы имеем результат.
Вычислительная стоимость
При оптимизации функции в переменные, -й уровень иерархии можно записать как полуопределенную программу над переменные и могут быть решены во времени используя метод эллипсоида.
Фон суммы квадратов
Многочлен является суммой квадратов ( SOS ), если существуют многочлены такой, что . Например,
представляет собой сумму квадратов, так как
где
Обратите внимание, что если это сумма квадратов, то для всех . Доступны подробные описания полиномиального SOS . [7] [8] [9]
Квадратичные формы могут быть выражены как где является симметричной матрицей. Точно так же многочлены степени ≤ 2 d могут быть выражены как
где вектор содержит все одночлены степени . Это известно как матричная форма Грама . Важным фактом является то, чтоявляется SOS тогда и только тогда, когда существует симметричная положительно-полуопределенная матрица такой, что . Это обеспечивает связь между полиномами SOS и положительно-полуопределенными матрицами.
Программные инструменты
- SOSTOOLS под лицензией GNU GPL . Справочное руководство доступно по адресу arXiv: 1310.4716 [math.OC] .
- CDCS-sos , пакет от CDCS , расширенного решателя лагранжевых методов , для работы с крупномасштабными программами SOS.
- Расширение SumOfSquares для JuMP .
- Для двойной задачи ограниченной полиномиальной оптимизации GloptiPoly для MATLAB, Ncpol2sdpa для Python и MomentOpt для Julia.
Рекомендации
- ^ Сумма квадратов: теория и приложения: краткий курс AMS, сумма квадратов: теория и приложения, 14-15 января 2019 г., Балтимор, Мэриленд . Parrilo, Pablo A .; Томас, Рекха Р. Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-1-4704-5025-0. OCLC 1157604983 .CS1 maint: другие ( ссылка )
- ^ Тан, В., Паккард, А., 2004. " Поиск управляющих функций Ляпунова с использованием сумм программирования квадратов ". В: Allerton Conf. по связи, управлению и вычислениям . С. 210–219.
- ^ Тан, В., Топку, У., Зайлер, П., Балас, Г., Паккард, А., 2008. Анализ достижимости и локального усиления нелинейных динамических систем с помощью моделирования . В: Proc. конференции IEEE по решениям и контролю. С. 4097–4102.
- ^ А. Чакраборти, П. Зайлер и Г. Балас, « Восприимчивость контроллеров полета F / A-18 к режиму падающего листа: нелинейный анализ », AIAA Journal of Guidance, Control, and Dynamics, vol. 34 нет. 1 (2011), стр. 73–85.
- ^ Берг, Кристиан (1987). Ландау, Генри Дж. (Ред.). «Многомерная проблема моментов и полугруппы» . Материалы симпозиумов по прикладной математике .
- ^ Лассер, Дж. (01.01.2007). «Аппроксимация суммой квадратов неотрицательных многочленов» . SIAM Обзор . 49 (4): 651–669. arXiv : математика / 0412398 . DOI : 10.1137 / 070693709 . ISSN 0036-1445 .
- ^ Паррило, П., (2000) Структурированные полуопределенные программы и методы полуалгебраической геометрии в устойчивости и оптимизации . Кандидат наук. дипломная работа Калифорнийского технологического института.
- ^ Паррило, П. (2003) " Расслабления полуопределенного программирования для полуалгебраических задач ". Математическое программирование Сер. В 96 (2), 293–320.
- ^ Лассер, Дж. (2001) " Глобальная оптимизация с многочленами и проблема моментов ". Журнал SIAM по оптимизации , 11 (3), 796 {817.