Оптимизация по сумме квадратов - Википедия - Sum-of-squares optimization

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

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

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

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

Проблема может быть выражена как

${ Displaystyle макс _ {и в mathbb {R} ^ {n}} c ^ {T} u}$

при условии

${ displaystyle 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}).}$

Здесь "SOS" представляет собой класс полиномов суммы квадратов (SOS). Вектор ${ displaystyle c in mathbb {R} ^ {n}}$ и многочлены ${ displaystyle {a_ {k, j} }}$ приведены как часть данных для задачи оптимизации. Количество ${ Displaystyle и в mathbb {R} ^ {п}}$ - переменные решения. Программы SOS могут быть преобразованы в полуопределенные программы (SDP) с помощьюдвойственность из SOS полином программа и релаксация для ограниченной полиномиальной оптимизации с использованием положительно-полуопределенные матрицы см. следующий раздел.

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

Предположим, у нас есть ${ displaystyle n}$-вариант полином ${ Displaystyle р (х): mathbb {R} ^ {n} to mathbb {R}}$ , и предположим, что мы хотели бы минимизировать этот многочлен по подмножеству ${ textstyle A substeq mathbb {R} ^ {n}}$.Предположим, кроме того, что ограничения на подмножество ${ textstyle A}$ можно закодировать с помощью ${ textstyle m}$ полиномиальные равенства степени не выше ${ displaystyle 2d}$, каждая форма ${ textstyle a_ {i} (x) = 0}$ куда ${ displaystyle a_ {i}: mathbb {R} ^ {n} to mathbb {R}}$ является многочленом степени не выше ${ displaystyle 2d}$. Естественная, хотя в целом невыпуклая программа для этой задачи оптимизации следующая:

${ displaystyle min _ {x in mathbb {R} ^ {n}} langle C, x ^ { leq d} (x ^ { leq d}) ^ { top} rangle}$

при условии:

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

${ Displaystyle х _ { emptyset} = 1}$,

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

Эта программа обычно невыпуклая, потому что ограничения (1) не выпуклые. Одна возможная выпуклая релаксация для этой задачи минимизации использует полуопределенное программирование заменить матрицу переменных первого ранга ${ Displaystyle х ^ { Leq d} (х ^ { Leq d}) ^ { top}}$ с положительно-полуопределенной матрицей ${ displaystyle X}$: мы индексируем каждый моном размера не более ${ displaystyle 2d}$ мультимножеством ${ displaystyle S}$ не более ${ displaystyle 2d}$ индексы, ${ Displaystyle S подмножество [п], | S | leq 2d}$. Для каждого такого монома создадим переменную ${ Displaystyle X_ {S}}$ в программе, и расставляем переменные ${ Displaystyle X_ {S}}$ сформировать матрицу ${ textstyle X in mathbb {R} ^ {[n] ^ { leq d} times [n] ^ { leq d}}}$, куда ${ Displaystyle mathbb {R} ^ {[п] ^ { leq d} раз [п] ^ { leq d}}}$- это множество вещественных матриц, строки и столбцы которых отождествляются с мультимножествами элементов из ${ displaystyle n}$ размером не более ${ displaystyle d}$. Затем мы записываем следующую полуопределенную программу в переменных ${ Displaystyle X_ {S}}$:

${ displaystyle min _ {X in mathbb {R} ^ {[n] ^ { leq d} times [n] ^ { leq d}}} langle C, X rangle}$

при условии:

${ displaystyle langle A_ {i}, X rangle = 0 qquad forall i in [m]}$,${ textstyle Q}$

${ Displaystyle X _ { emptyset} = 1}$,

${ Displaystyle X_ {U чашка V} = X_ {S cup T} qquad forall U, V, S, T substeq [n], | U |, | V |, | S |, | T | leq d, { text {and}} U cup V = S cup T}$,

${ displaystyle X successq 0}$,

где снова ${ textstyle C}$ - матрица коэффициентов многочлена ${ textstyle p (x)}$ что мы хотим минимизировать, и ${ textstyle A_ {i}}$ - матрица коэффициентов многочлена ${ textstyle a_ {i} (x)}$ кодирование ${ displaystyle i}$ограничение на подмножество ${ Displaystyle А подмножество mathbb {R} ^ {п}}$.

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

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

Можно взять двойник указанной выше полуопределенной программы и получить следующую программу:

${ displaystyle max _ {y in mathbb {R} ^ {m '}} y_ {0}}$,

при условии:

${ displaystyle 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}) successq 0}$.

У нас есть переменная ${ displaystyle y_ {0}}$соответствующая ограничению ${ Displaystyle langle е _ { emptyset}, X rangle = 1}$(куда ${ Displaystyle е _ { emptyset}}$матрица со всеми нулевыми элементами, за исключением записи, индексированной ${ Displaystyle ( emptyset, emptyset)}$), действительная переменная ${ displaystyle y_ {i}}$для каждого полиномиального ограничения ${ displaystyle langle X, A_ {i} rangle = 0 quad s.t.i in [m],}$и для каждой группы мультимножеств ${ Displaystyle S, T, U, V подмножество [n], | S |, | T |, | U |, | V | leq d, S cup T = U cup V}$, у нас есть двойственная переменная ${ displaystyle y_ {S, T, U, V}}$для ограничения симметрии ${ Displaystyle langle X, e_ {S, T} -e_ {U, V} rangle = 0}$. Ограничение положительной полуопределенности гарантирует, что ${ displaystyle p (x) -y_ {0}}$ представляет собой сумму квадратов многочленов над ${ Displaystyle А подмножество mathbb {R} ^ {п}}$: характеристикой положительно-полуопределенных матриц для любой положительно-полуопределенной матрицы ${ textstyle Q in mathbb {R} ^ {m times m}}$, мы можем написать ${ textstyle Q = сумма _ {я in [м]} е_ {я} е_ {я} ^ { top}}$ для векторов ${ textstyle f_ {i} in mathbb {R} ^ {m}}$. Таким образом, для любого ${ textstyle x in A подмножество mathbb {R} ^ {n}}$,

${ displaystyle { begin {align} 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} - сумма _ {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 {по симметрии}} & = (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 {выравнивается}}}$

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

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

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

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

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

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

Вычислительная стоимость

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

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

Полином ${ displaystyle p}$ это сумма площадей (SOS), если существуют многочлены ${ Displaystyle {е_ {я} } _ {я = 1} ^ {м}}$такой, что ${ Displaystyle р = сумма _ {я = 1} ^ {м} е_ {я} ^ {2}}$. Например,

${ displaystyle p = x ^ {2} -4xy + 7y ^ {2}}$

представляет собой сумму квадратов, поскольку

${ displaystyle p = f_ {1} ^ {2} + f_ {2} ^ {2}}$

куда

${ displaystyle f_ {1} = (x-2y) { text {and}} f_ {2} = { sqrt {3}} y.}$

Обратите внимание, что если ${ displaystyle p}$ это сумма квадратов, тогда ${ Displaystyle р (х) geq 0}$ для всех ${ Displaystyle х в mathbb {R} ^ {п}}$. Подробные описания полином SOS доступны.^[7][8][9]

Квадратичные формы можно выразить как ${ Displaystyle р (х) = х ^ {T} Qx}$ куда ${ displaystyle Q}$ является симметричной матрицей. Аналогично многочлены степени ≤ 2d можно выразить как

${ Displaystyle р (х) = z (х) ^ {T} Qz (х),}$

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

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

• СОСТУЛЫ, под лицензией GNU GPL. Справочное руководство доступно на arXiv: 1310.4716 [math.OC].

• CDCS-sos, пакет от CDCS, расширенный лагранжев метод решатель, чтобы иметь дело с крупномасштабными программами SOS.

• В Сумма площадей расширение Прыгать.
• Для двойственной задачи полиномиальной оптимизации с ограничениями ГлоптиПоли для MATLAB, Ncpol2sdpa для Python и MomentOpt для Юлии.

Рекомендации