Оптимизация суммы квадратов

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

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

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

Проблема оптимизации

Учитывая вектор $c\in \mathbb {R} ^{n}$ и полиномы $a_{k,j}$ для $k=1,\dots N_{s}$, $j=0,1,\dots ,n$, задача оптимизации суммы квадратов записывается как

$${\begin{aligned}{\underset {u\in \mathbb {R} ^{n}}{\text{maximize}}}\quad &c^{T}u\\{\text{subject to}}\quad &a_{k,0}(x)+a_{k,1}(x)u_{1}+\cdots +a_{k,n}(x)u_{n}\in {\text{SOS}}\quad (k=1,\ldots ,N_{s}).\end{aligned}}$$

Здесь «SOS» представляет класс полиномов суммы квадратов (SOS).Количества $u\in \mathbb {R} ^{n}$ являются переменными решения. Программы SOS можно преобразовать в полуопределенные программы (SDP) с использованием двойственности полиномиальной программы SOS и ослабления полиномиальной оптимизации с ограничениями с использованием положительно-полуопределенных матриц , см. следующий раздел.

Двойная задача: полиномиальная оптимизация с ограничениями

Предположим, у нас есть $n$-вариативный полином $p(x):\mathbb {R} ^{n}\to \mathbb {R}$ и предположим, что мы хотели бы минимизировать этот многочлен по подмножеству ${\textstyle A\subseteq \mathbb {R} ^{n}}$. Предположим, далее, что ограничения на подмножество ${\textstyle A}$ можно закодировать с помощью ${\textstyle m}$ полиномиальные равенства степени не более $2d$, каждая из форм ${\textstyle a_{i}(x)=0}$ где $a_{i}:\mathbb {R} ^{n}\to \mathbb {R}$ является полиномом степени не более $2d$. Естественная, хотя и невыпуклая, программа для этой задачи оптимизации выглядит следующим образом: $$\min _{x\in \mathbb {R} ^{n}}\langle C,x^{\leq d}(x^{\leq d})^{\top }\rangle$$подлежит:

$$\langle A_{i},x^{\leq d}(x^{\leq d})^{\top }\rangle =0\qquad \forall \ i\in [m],$$ ( 1 )

$$x_{\emptyset }=1,$$где ${\textstyle x^{\leq d}}$ это $n^{O(d)}$-мерный вектор с одной записью для каждого монома в $x$ степени максимум $d$, так что для каждого мультимножества $S\subset [n],|S|\leq d,$ ${\textstyle x_{S}=\prod _{i\in S}x_{i}}$, ${\textstyle C}$ представляет собой матрицу коэффициентов многочлена ${\textstyle p(x)}$ которые мы хотим свести к минимуму, и ${\textstyle A_{i}}$ представляет собой матрицу коэффициентов многочлена ${\textstyle a_{i}(x)}$ кодирование $i$-th ограничение на подмножество $A\subset \mathbb {R} ^{n}$. Дополнительный фиксированный постоянный индекс в нашем пространстве поиска, $x_{\emptyset }=1$, добавлено для удобства записи полиномов ${\textstyle p(x)}$ и ${\textstyle a_{i}(x)}$ в матричном представлении.

Эта программа, как правило, невыпуклая, поскольку ограничения ( 1 ) не являются выпуклыми. Одна из возможных выпуклых релаксаций для этой задачи минимизации использует полуопределенное программирование для замены матрицы переменных первого ранга. $x^{\leq d}(x^{\leq d})^{\top }$ с положительно-полуопределенной матрицей $X$: индексируем каждый моном не более $2d$ по мультимножеству $S$ максимум $2d$ индексы, $S\subset [n],|S|\leq 2d$. Для каждого такого монома создадим переменную $X_{S}$ в программе, и расставляем переменные $X_{S}$ чтобы сформировать матрицу ${\textstyle X\in \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}$, где $\mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}$– это набор действительных матриц, строки и столбцы которых отождествляются с мультимножествами элементов из $n$ размера максимум $d$. Затем запишем следующую полуопределенную программу в переменных $X_{S}$: $$\min _{X\in \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}\langle C,X\rangle$$подлежит: $$\langle A_{i},X\rangle =0\qquad \forall \ i\in [m],Q$$$$X_{\emptyset }=1,$$$$X_{U\cup V}=X_{S\cup T}\qquad \forall \ U,V,S,T\subseteq [n],|U|,|V|,|S|,|T|\leq d,{\text{ and}}\ U\cup V=S\cup T,$$$$X\succeq 0,$$

где снова ${\textstyle C}$ – матрица коэффициентов полинома ${\textstyle p(x)}$ которые мы хотим свести к минимуму, и ${\textstyle A_{i}}$ – матрица коэффициентов полинома ${\textstyle a_{i}(x)}$ кодирование $i$-th ограничение на подмножество $A\subset \mathbb {R} ^{n}$.

Третье ограничение гарантирует, что значение монома, который появляется в матрице несколько раз, одинаково во всей матрице, и добавляется, чтобы сделать $X$ соблюдайте симметрии, присутствующие в квадратичной форме $x^{\leq d}(x^{\leq d})^{\top }$.

Двойственность

Можно взять двойственную полуопределенную программу и получить следующую программу: $$\max _{y\in \mathbb {R} ^{m'}}y_{0},$$подлежит: $$C-y_{0}e_{\emptyset }-\sum _{i\in [m]}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T}-e_{U,V})\succeq 0.$$

У нас есть переменная $y_{0}$ соответствующий ограничению $\langle e_{\emptyset },X\rangle =1$ (где $e_{\emptyset }$ - это матрица, в которой все записи равны нулю, за исключением записи, индексированной $(\varnothing ,\varnothing )$), действительная переменная $y_{i}$для каждого полиномиального ограничения $\langle X,A_{i}\rangle =0\quad s.t.i\in [m],$ и для каждой группы мультимножеств $S,T,U,V\subset [n],|S|,|T|,|U|,|V|\leq d,S\cup T=U\cup V$, у нас есть двойная переменная $y_{S,T,U,V}$для ограничения симметрии $\langle X,e_{S,T}-e_{U,V}\rangle =0$. Ограничение положительной полуопределенности гарантирует, что $p(x)-y_{0}$ представляет собой сумму квадратов многочленов над $A\subset \mathbb {R} ^{n}$: путем характеристики положительно-полуопределенных матриц для любой положительно-полуопределенной матрицы ${\textstyle Q\in \mathbb {R} ^{m\times m}}$, мы можем написать ${\textstyle Q=\sum _{i\in [m]}f_{i}f_{i}^{\top }}$ для векторов ${\textstyle f_{i}\in \mathbb {R} ^{m}}$. Таким образом, для любого ${\textstyle x\in A\subset \mathbb {R} ^{n}}$, $${\begin{aligned}p(x)-y_{0}&=p(x)-y_{0}-\sum _{i\in [m']}y_{i}a_{i}(x)\qquad {\text{since }}x\in A\\&=(x^{\leq d})^{\top }\left(C-y_{0}e_{\emptyset }-\sum _{i\in [m']}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T}-e_{U,V})\right)x^{\leq d}\qquad {\text{by symmetry}}\\&=(x^{\leq d})^{\top }\left(\sum _{i}f_{i}f_{i}^{\top }\right)x^{\leq d}\\&=\sum _{i}\langle x^{\leq d},f_{i}\rangle ^{2}\\&=\sum _{i}f_{i}(x)^{2},\end{aligned}}$$

где мы определили векторы ${\textstyle f_{i}}$ с коэффициентами многочлена степени не выше $d$. Это дает доказательство суммы квадратов, что значение ${\textstyle p(x)\geq y_{0}}$ над $A\subset \mathbb {R} ^{n}$.

Вышеуказанное также может быть распространено на регионы. $A\subset \mathbb {R} ^{n}$ определяется полиномиальными неравенствами.

Иерархия суммы квадратов

Иерархия суммы квадратов (иерархия SOS), также известная как иерархия Лассерра, представляет собой иерархию выпуклых релаксаций возрастающей мощности и увеличения вычислительных затрат. Для каждого натурального числа ${\textstyle d\in \mathbb {N} }$ соответствующая выпуклая релаксация известна как ${\textstyle d}$уровень или ${\textstyle d}$-й раунд иерархии SOS. The ${\textstyle 1}$первый раунд, когда ${\textstyle d=1}$, соответствует базовой полуопределенной программе или оптимизации суммы квадратов по полиномам степени не выше $2$. Чтобы расширить базовую выпуклую программу на ${\textstyle 1}$первый уровень иерархии ${\textstyle d}$-м уровне в программу добавляются дополнительные переменные и ограничения, чтобы программа учитывала полиномы не более степени $2d$.

Иерархия SOS получила свое название от того факта, что значение целевой функции в ${\textstyle d}$-й уровень ограничен доказательством суммы квадратов с использованием многочленов степени не выше ${\textstyle 2d}$ через двойственность (см. «Двойственность» выше). Следовательно, любое доказательство суммы квадратов, использующее многочлены степени не выше ${\textstyle 2d}$ может быть использовано для ограничения целевого значения, что позволяет доказать гарантии остроты релаксации.

В сочетании с теоремой Берга это далее означает, что при достаточном количестве раундов релаксация становится сколь угодно жесткой на любом фиксированном интервале. Результат Берга утверждает, что каждый неотрицательный действительный полином в пределах ограниченного интервала может быть аппроксимирован с точностью ${\textstyle \varepsilon }$ на этом интервале с суммой квадратов действительных многочленов достаточно высокой степени, и, следовательно, если ${\textstyle OBJ(x)}$ - полиномиальное целевое значение как функция точки ${\textstyle x}$, если неравенство ${\textstyle c+\varepsilon -OBJ(x)\geq 0}$ держится для всех ${\textstyle x}$ в интересующей области, то должно быть доказательство этого факта суммой квадратов. Выбор ${\textstyle c}$ чтобы быть минимумом целевой функции в допустимой области, мы имеем результат.

Стоимость вычислений

При оптимизации функции в ${\textstyle n}$ переменные, ${\textstyle d}$-й уровень иерархии можно записать в виде полуопределенной программы над ${\textstyle n^{O(d)}}$ переменные и могут быть решены за время ${\textstyle n^{O(d)}}$ используя метод эллипсоида .

Фон суммы квадратов

Основная статья: Полиномиальный SOS

Полином $p$ является суммой квадратов ( SOS ), если существуют многочлены $\{f_{i}\}_{i=1}^{m}$ такой, что ${\textstyle p=\sum _{i=1}^{m}f_{i}^{2}}$. Например, $$p=x^{2}-4xy+7y^{2}$$представляет собой сумму квадратов, поскольку $$p=f_{1}^{2}+f_{2}^{2}$$где $$f_{1}=(x-2y){\text{ and }}f_{2}={\sqrt {3}}y.$$Обратите внимание, что если $p$ это сумма квадратов, тогда $p(x)\geq 0$ для всех $x\in \mathbb {R} ^{n}$. подробные описания полиномиального SOS . Доступны

Квадратичные формы можно выразить как $p(x)=x^{T}Qx$ где $Q$ является симметричной матрицей. Аналогично полиномы степени ≤ 2 d можно выразить как $$p(x)=z(x)^{\mathsf {T}}Qz(x),$$где вектор $z$ содержит все мономы степени $\leq d$. Это известно как форма матрицы Грама . Важным фактом является то, что $p$ является SOS тогда и только тогда, когда существует симметричная и положительно-полуопределенная матрица $Q$ такой, что $p(x)=z(x)^{\mathsf {T}}Qz(x)$.Это обеспечивает связь между полиномами SOS и положительно-полуопределенными матрицами.

Программные инструменты

• SOSTOOLS , лицензия GNU GPL . Справочное руководство доступно по адресу arXiv:1310.4716 [math.OC] , а презентация о его внутреннем устройстве доступна здесь .
• CDCS-sos — пакет из CDCS , расширенного решателя метода Лагранжа , предназначенный для работы с крупномасштабными программами SOS.
• Расширение SumOfSquares для JuMP для Julia.
• TSSOS for Julia, инструмент полиномиальной оптимизации, основанный на иерархиях моментного SOS, адаптированных к разреженности.
• Для двойной задачи полиномиальной оптимизации с ограничениями используйте GloptiPoly для MATLAB/Octave, Ncpol2sdpa для Python и MomentOpt для Julia.