Most optimization problems in real-life are hard to solve optimally. However, for practical purposes it is usually sufficient to settle for near-optimal solutions that can be found quickly. Fast and more accurate approximations can be computed using semidefinite programming, a novel powerful optimization tool, with a much greater modelling power than the common linear techniques. PhD student Antonios Varvitsiotis from Centrum Wiskunde & Informatica (CWI) studied this research area and defended his PhD thesis 'Combinatorial Conditions for Low Rank Solutions in Semidefinite Programming' on 25 November at Tilburg University.
Low-rank solutions (meaning that the number of essential columns in the matrix is low) to semidefinite programs are important, since they yield better approximations for hard optimization problems. Moreover, researchers can use them to model geometric questions, like reconstructing a molecule from partial data on pairwise distances between its atoms. To investigate these kinds of problems, Varvitsiotis set up a link between semidefinite programming and combinatorics. With any semidefinite program he associated a graph (a 'mathematical picture' with dots and lines), encoding the sparsity (or density) of the data matrices. Looking at the structure of this graph, and using the theory of forbidden graph minors, Varvitsiotis was able to characterize the existence of optimal solutions of rank at most 4.
Varvitsiotis says: "The main idea is to exploit the sparsity of the data in a semidefinite program - that is a novelty. No one really looked at those questions before. Now the challenge is to make the results constructive: not only proving that a solution of low rank exists, but also finding it. This is the next step in obtaining better approximation algorithms." Antonios Varvitsiotis is a PhD student at Centrum Wiskunde & Informatica under the supervision of Monique Laurent in the Networks & Optimization group. His research was funded with the Spinoza Award from Lex Schrijver.
More information:
PhD thesis of Antonios Varvitsiotis
Networks & Optimization Group at CWI
Picture: PhD defence of Antonios Varvitsiotis from CWI at Tilburg University, 25 November 2013.
