Estudo comparativo de métodos alternativos à soma de quadrados

Abstract

Problemas de otimização polinomial são problemas de elevada importância na área da otimização e a sua resolução equivale a verificar a não negatividade de um polinómio, que é um problema NP-difícil para polinómios com grau pelo menos quatro. Ora a não negatividade de um polinómio pode ser certificada através da escrita do polinómio como soma de quadrados de outros polinómios que, no entanto, não capturam a totalidade dos polinómios não negativos. Uma forma encontrada de contornar esta limitação originou a introdução dos chamados polinómios $r$-SOS, que incluem todos os polinómios positivos. Contudo, a verificação desta propriedade das somas de quadrados, efetuada através de programação semidefinida, é dispendiosa e não é praticável para problemas de grande escala.Devido a esta limitação associada às somas de quadrados, estudos recentes levaram à introdução de dois métodos alternativos de verificação da não negatividade de um polinómio: a soma de binómios quadrados (SOBS ou SDSOS), envolvendo programação cónica de segunda ordem e a soma de circuitos polinomiais não negativos (SONC), envolvendo programação geométrica. O objetivo deste trabalho é explorar as relações entre polinómios que são somas de circuitos polinomiais não negativos e os polinómios $r$-SOS e $r$-SOBS, para algum $r$, duas hierarquias que são variantes mais fortes das somas de quadrados e somas de binómios quadrados, respetivamente.No decorrer do estudo, para além de darmos resposta ao problema a que nos tínhamos proposto, recuperamos experimentalmente algumas observações já conhecidas e conjeturamos novos resultados que pensamos ainda não serem conhecidos.

Polynomial optimization problems are problems with an extreme relevance in optimization and their resolution can be reduced to verify the nonnegativity of a polynomial, which is an NP-hard problem for polynomials with degree at least four. Nonnegativity of a polynomial can be certified through writing the polynomial as a sum of squares of other polynomials, however, this property doesn't capture all nonnegative polynomials. A way that was found to bypass this limitation was the introduction of the $r$-SOS polynomials class, which includes every positive polynomial. However, verifying this sums of squares property, done through semidefinite programming, is costly and is not practical for large scale problems (either in degree or in number of variables of a polynomial).Due to this limitation associated with the sums of squares, recent studies proposed two alternative methods of verifying nonnegativity: sums of binomial squares (SOBS or SDSOS), involving second order cone programming, and sums of nonnegative circuit polynomials (SONC), involving geometric programming. The goal of this work is to explore the relations between sums of nonnegative circuit polynomials and $r$-SOS and $r$-SOBS polynomials, for some $r$, two hierarchies that strengthen sums of squares and sums of binomial squares, respectively. Throughout the study, we provide not only the answer to the proposed problem, but also recover, experimentally, some previously known observations and conjecture new results which we think are not yet known.