Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/95560
Title: Estudo comparativo de métodos alternativos à soma de quadrados
Other Titles: Comparative study of alternative methods to the sum of squares
Authors: Lacximicant, Nuno Ricardo Ferreira
Orientador: Gouveia, João Eduardo da Silveira
Keywords: polinómio; somas de quadrados; somas de binómios quadrados; circuitos polinomiais não negativos; polynomial; sums of squares; sums of binomial squares; nonnegative circuit polynomials
Issue Date: 28-Jul-2021
Serial title, monograph or event: Estudo comparativo de métodos alternativos à soma de quadrados
Place of publication or event: Departamento de Matemática da Universidade de Coimbra
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.
Description: Dissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia
URI: https://hdl.handle.net/10316/95560
Rights: openAccess
Appears in Collections:UC - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat
Dissertação_Nuno_Ferreira.pdf953.92 kBAdobe PDFView/Open
Show full item record

Page view(s)

109
checked on Mar 26, 2024

Download(s)

58
checked on Mar 26, 2024

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons