Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/95560
DC FieldValueLanguage
dc.contributor.advisorGouveia, João Eduardo da Silveira-
dc.contributor.authorLacximicant, Nuno Ricardo Ferreira-
dc.date.accessioned2021-08-05T22:03:03Z-
dc.date.available2021-08-05T22:03:03Z-
dc.date.issued2021-07-28-
dc.date.submitted2021-08-05-
dc.identifier.urihttp://hdl.handle.net/10316/95560-
dc.descriptionDissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia-
dc.description.abstractProblemas 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.por
dc.description.abstractPolynomial 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.eng
dc.language.isopor-
dc.rightsopenAccess-
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/-
dc.subjectpolinómiopor
dc.subjectsomas de quadradospor
dc.subjectsomas de binómios quadradospor
dc.subjectcircuitos polinomiais não negativospor
dc.subjectpolynomialeng
dc.subjectsums of squareseng
dc.subjectsums of binomial squareseng
dc.subjectnonnegative circuit polynomialseng
dc.titleEstudo comparativo de métodos alternativos à soma de quadradospor
dc.title.alternativeComparative study of alternative methods to the sum of squareseng
dc.typemasterThesis-
degois.publication.locationDepartamento de Matemática da Universidade de Coimbra-
degois.publication.titleEstudo comparativo de métodos alternativos à soma de quadradospor
dc.peerreviewedyes-
dc.identifier.tid202753948-
thesis.degree.disciplineMatemática-
thesis.degree.grantorUniversidade de Coimbra-
thesis.degree.level1-
thesis.degree.nameMestrado em Matemática-
uc.degree.grantorUnitFaculdade de Ciências e Tecnologia - Departamento de Matemática-
uc.degree.grantorID0500-
uc.contributor.authorLacximicant, Nuno Ricardo Ferreira::0000-0002-0475-0699-
uc.degree.classification18-
uc.degree.presidentejuriPetronilho, José Carlos Soares-
uc.degree.elementojuriCaldeira, Cristina Helena de Matos-
uc.degree.elementojuriGouveia, João Eduardo da Silveira-
uc.contributor.advisorGouveia, João Eduardo da Silveira::0000-0001-8345-9754-
item.fulltextCom Texto completo-
item.languageiso639-1pt-
item.grantfulltextopen-
crisitem.advisor.deptFaculty of Sciences and Technology-
crisitem.advisor.parentdeptUniversity of Coimbra-
crisitem.advisor.researchunitCMUC - Centre for Mathematics of the University of Coimbra-
crisitem.advisor.orcid0000-0001-8345-9754-
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 simple item record

Page view(s)

25
checked on Oct 8, 2021

Download(s)

11
checked on Oct 8, 2021

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons