Эту страницу ведет Людмила Чернышенко, студентка первого курса Математико-механического факультета Санкт-Петербургского государственного Университета. Рассказ о проекте на этой странице - для студентов.
Начнем с идеи:
На этой странице мы дадим краткое описание метода разложения многочленов в суммы квадратов, открытого Пабло Паррило в 2000 году [1], и покажем, как при помощи выпуклого программирования может быть проверено существование этого разложения.
Замечание: выпуклое программирование – раздел математического программирования, посвященный теории и методам решения задач минимизации выпуклых функций на выпуклых множествах, задаваемых системами равенств и неравенств.
Определение: для любого х ϵ Rn многочлен p(x) называется разложением в суммы квадратов, если существуют многочлены fi(x) i=1, … ,M такие, что
p(x)=
Теорема: многочлен p(x) степени 2d может быть представлен в виде суммы квадратов тогда и только тогда, когда существуют положительно полуопределенная матрица Q и вектор одночленов Z(x), содержащий одночлены вида ax1r1x2r2...xnrn, где r1+...rn ≤ d такие, что p(x)=ZT(x)QZ(x).
В общем одночлены в Z(x) не обязательно алгебраически независимы. Вычислив ZT(x)QZ(x) и приравняв коэффициенты при получившихся одночленах соответствующим коэффициентам p(x), мы получаем набор аффинных отношений между элементами Q. Проблема нахождения положительно полуопределенной матрицы Q, элементы которой удовлетворяют полученным аффинным отношениям, может быть решена при помощи выпуклого программирования. Как только для p(x) найдется соответствующая положительно-полуопределенная матрица Q, будет доказано, что p(x) может быть представлен в виде суммы квадратов.
хTАх=
=
+…+
, причем выражение
+…+
≥0 только при
≥0.
Пример (из [2]): предположим, что мы хотим узнать, может ли многочлен четвертой степени p() =
2
+2
-
+5
, зависящий от двух переменных, быть представлен в виде суммы квадратов многочленов.
Для этого определим
Z(x)=
Т
и рассчитаем следующую квадратичную форму:
p() =
2
+2
-
+5
= Z(x)Т
Z(x)
=
+
+
+2
+2
.
Из этого равенства получаем следующие отношения:
Теперь при помощи методов полуопределенного программирования мы можем найти
и
,
удовлетворяющие последнему уравнению, такие, что матрица Q будет положительно полуопределена. Эти условия выполняются при
и
.
Затем мы находим базис, в котором матрица Q будет иметь диагональный вид, и выражаем одночлены в векторе Z(x) через этот базис, перемножаем по формуле p(x)=Z(x)TQZ(x) и получаем следующее разложение в сумму квадратов:
p() =
.
Замечание: Из того, что многочлен p(x) может быть представлен в виде суммы квадратов, следует, что многочлен p(x)≥0 для всех х ϵ Rn. Однако обратное утверждение не всегда верно. Не все неотрицательные многочлены могут быть представлены в виде суммы квадратов, за исключением трех случаев:
Мы уже говорили, что положительно полуопределенная матрица, элементы которой удовлетворяют аффинным отношениям, может быть найдена при помощи методов выпуклого программирования, но для этого нам нужно убедиться, что множество, над которым мы хотим применить эти методы, является выпуклым.
Справка: Множество называется выпуклым, если оно вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки. Другими словами, множество G ϵ Rn называется выпуклым, если для любых двух точек x1 ϵ G, x2 ϵ G и для любого λ, 0≤λ≤1 верно, что λx1+(1-λ)x2 ϵ G. |
Для проверки выпуклости множества положительно полуопределенных матриц возьмем две матрицы, принадлежащие этому множеству, и проверим что матрица A=
+
, где 0≤λ≤1, будет также положительно полуопределена. Для этого рассмотрим равенство xТAx= xТ
+
)x, где 0≤λ≤1. В связи с положительной полуопределенностью матриц
и указанными выше условиями на λ, мы получаем что xТAx≥0, а это и означает, что матрица A положительно полуопределена. Следовательно, это множество является выпуклым.
Затем, убедившись, что множество положительно полуопределенных матриц является выпуклым, мы будем рассматривать такие положительно полуопределенные матрицы, элементы которых удовлетворяют полученным нами ранее аффинным отношениям.
Эти аффинные отношения образуют гиперплоскость, поэтому искомая матрица будет лежать в сечении выпуклого множества положительно-полуопределенных матриц, образованной гиперплоскостью. Как известно это сечение будет выпуклым, поэтому проблема нахождения необходимой матрицы действительно может быть решена при помощи выпуклого программирования.
Информация, используемая на данной странице, опирается на материалы статьи [2].
1. P. A. Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, Pasadena, CA, 2000.
2. A. Papachristodoulou and S. Prajna. A Tutorial on Sum of Squares Techniques for Systems Analysis. 2005 American Control Conference June 8-10, 2005. Portland, OR, USA.