Conference Agenda

Semidefinite Programming (SDP) is an extension of Linear Programming (LP). A matrix-variable is optimized over the intersection of the cone of positive semidefinite matrices with an affine space. It turns out that SDP can provide significantly stronger practical results than LP and that it can be applied in a lot of different areas, like combinatorial optimization, control theory, engineering, or polynomial optimization.

In this talk we will show how to apply SDP to efficiently approximate NP-hard combinatorial optimization problems, like graph partitioning or minimum sum-of-squares clustering. Linked to the question of modeling a problem using semidefinite programming is the question of solving the resulting SDP. Standard methods like interior point algorithms are not applicable already to medium-sized problems due to the number of constraints or the size of the matrix. We will present alternative methods in order to obtain approximate solutions to the SDP in reasonable time and using affordable memory requirements.