Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/105057
DC FieldValueLanguage
dc.contributor.advisorGouveia, João Eduardo da Silveira-
dc.contributor.authorBostanabad, Mina Saee-
dc.date.accessioned2023-01-31T12:21:28Z-
dc.date.available2023-01-31T12:21:28Z-
dc.date.issued2020-02-17-
dc.date.submitted2019-08-29-
dc.identifier.urihttps://hdl.handle.net/10316/105057-
dc.descriptionTese no âmbito do Programa Interuniversitário de Doutoramento em Matemática apresentada ao Departamento de Matemática da Faculdade de Ciências e Tecnologia da Universidade de Coimbra.pt
dc.description.abstractConic optimization is one of the most important and thriving research areas in the optimization field and it has a closed connection with polynomial optimization through semidefinite programming. In fact, it is known that global nonnegativity of a polynomial can be checked using sums of squares and this amounts to solving a semidefinite program. However, semidefinite programming is expensive for large-scale problems. Several attempts have been done in literature to inner approximate the positive semidefinite cone by replacing the psd condition with conditions that are cheaper but still effective in practice. In this thesis, we give some certificates for nonnegativity of polynomials using bounded factor width matrices since the cones of matrices of bounded factor width give a hierarchy of inner approximations to the PSD cone. The concept of factor width for a positive semidefinite matrix has been introduced recently and very few works have been done in this area, with the most relevant being an exploration on the cone of factor width two matrices as an inner approximation for SOS problems, by Ahmadi and Majumdar, the so called SDSOS. We will prove new results for matrices with bounded factor width and use them to derive new results on the existence of certificates of nonnegativity of polynomials. We also propose the use of the cone of nonnegative factor width two matrices as a natural inner approximation for the completely positive cone. Using projections of this cone we derive new graph-based second-order cone approximation schemes for completely positive programming. This approach is a compromise between the expressive power of existing SDP and speed of LP based inner approximations. We also present numerical results on random problems and the stable set problem to illustrate the effectiveness of our approach.pt
dc.description.abstractA optimização cónica é uma das áreas mais importantes e ativas no campo da otimização e está intimamente ligada à otimização polinomial através da programação semidefinida. De facto, é sabido que a não negatividade de polinómios pode ser verificada recorrendo a somas de quadrados, e isto resume-se a um programa semidefinido. Contudo, a programação semidefinida é dispendiosa para problemas de grande escala. Vários métodos foram propostos na literatura para aproximar pelo interior o cone de matrizes semidefinidas positivas substituindo a condição de sdp por condições mais leves mas ainda eficientes na prática. Nesta tese, estudamos certificado de não negatividade de polinómios com recurso a matrizes com largura de factores limitada, já que os cones de matrizes de largura de factores limitada formam uma hierarquia de aproximações interiores ao cone SDP. O conceito de largura de factores para uma matriz semidefinida positiva foi introduzido recentemente e poucos trabalhos forma produzidos nesta área, com o mais relevante sendo uma exploração da utilização do cone de matrizes de largura de factores menor ou igual a dois como aproximação interior para problemas de soma de quadrados, por Ahmadi e Majumdar, designada de SDSOS. Provaremos novos resultados para matrizes de largura de factores limitada e usá-los-emos para derivar novos resultados sobre a existência de certificados de não negatividade de polinómios. Propomos ainda o uso do cone das matrizes não negativas de largura de factores no máximo dois como uma aproximação interior natural para o cone de matrizes completamente positivas. Usando projeções deste cone derivamos novos esquemas de aproximação por cones de segunda ordem para programação completamente positiva. Esta abordagem oferece um compromisso entre o poder expressivo da programação semidefinida e a velocidade das aproximações interiores por programas lineares. Apresentamos ainda resultados numéricos para problemas aleatórios e problemas de independência em grafos para ilustrar a eficiência da nossa abordagem.pt
dc.language.isoengpt
dc.relationinfo:eu-repo/grantAgreement/FCT/POR_CENTRO/PD/BD/128060/2016/PT/Semidefinite programming and polynomial optimizationpt
dc.rightsembargoedAccesspt
dc.subjectBounded factor width matricespt
dc.subjectsums of squarespt
dc.subjectconic optimizationpt
dc.subjectpolynomial optimizationpt
dc.subjectcopositive optimizationpt
dc.subjectMatrizes com largura de factores limitadapt
dc.subjectsomas de quadradospt
dc.subjectotimização cónicapt
dc.subjectotimização polinomialpt
dc.subjectotimização copositivapt
dc.titleA semidefinite approach to algebraic optimizationpt
dc.title.alternativeUma abordagem semidefinida à otimização algébricapt
dc.typedoctoralThesispt
dc.peerreviewedyes-
dc.date.embargo2020-02-17*
dc.identifier.tid101621833pt
dc.subject.fosMathematicspt
thesis.degree.disciplineID03003231-
thesis.degree.leveldoutor-
thesis.degree.nameTese no âmbito do Programa Interuniversitário de Doutoramento em Matemáticapt
uc.rechabilitacaoestrangeiranopt
uc.date.periodoEmbargo0pt
item.languageiso639-1en-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairetypedoctoralThesis-
item.fulltextCom Texto completo-
item.grantfulltextopen-
item.cerifentitytypePublications-
crisitem.advisor.researchunitCMUC - Centre for Mathematics of the University of Coimbra-
crisitem.advisor.orcid0000-0001-8345-9754-
Appears in Collections:UC - Teses de Doutoramento
FCTUC Matemática - Teses de Doutoramento
Files in This Item:
File Description SizeFormat
thesis_Mina.pdf778.79 kBAdobe PDFView/Open
Show simple item record

Page view(s)

66
checked on Feb 27, 2024

Download(s)

38
checked on Feb 27, 2024

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.