Cum laude for Luis Felipe Vargas for research in optimization

Luis Felipe Vargas explains his research to fellow mathematicians: “Computing the size of the largest clique can be formulated as linear optimization over the cone of copositive matrices, thereby lifting the usual problem formulation from vectors to well-structured matrices with a high modelling power. In 2000, Parrilo introduced approximation hierarchies for this cone, based on the algebraic notion of sums of squares of polynomials, and, in 2002, de Klerk and Pasechnik used them to design tractable bounds for the maximum clique parameter. In my research, I have unraveled structural properties of these hierarchies. Together with colleagues, I have shown that these bounds recover the clique parameter exactly. For this, we show that certain graph polynomials enjoy several properties related with sums of squares. This result offers the first substantial progress in twenty years on an open question by de Klerk and Pasechnik. In addition, I characterized the matrix sizes for which the hierarchies suffice to capture the full copositive cone. In my work the interplay between algebra and optimization is two-ways: we use algebraic techniques as powerful toolbox for designing tractable approximations for optimization problems, but we also give novel contributions about sums of squares representations of positive polynomials. My results have also somewhat surprising complexity implications: Deciding whether a polynomial has finitely many minimizers in a simplex region is NP-hard, while this question restricted to linear functions has a polynomial-time algorithm.”