A semidefinite approach to algebraic optimization

Abstract

Conic 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.

A 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.