Thursday, September 4, 2014

Seminar on "Preprocessing semidefinite optimization problems"

We are please to announce that on October the 6th 2014 a series of seminars titled "Preprocessing semidefinite optimization problems" will be held at MOSEK site in the Symbion research park

Three prominent experts of the field, namely E. De Klerk, F. Permenter and J. Dahl, will discuss recent advances and applications on semidefinite optimization problem preprocessing.

Participation is free and everybody is welcome, but for logistic reasons we would like you to register here. Refreshment will be served. Detailed titles and abstracts can be found at the end of the page.

Schedule of the day:

15:00 - 15:05 Introduction
15:05 - 15:50 E. De Klerk,
 Tilburg University (NL)
15:50 - 15:55 Break
15:55 - 16:40 F. Permenter, MIT (US)
16:40 - 16:45 Break
16:45 - 17:15 J. Dahl, MOSEK ApS (DK)
18:00 Optional networking at Nørrebro Bryghus.

We hope to see you!

How to get there: check information on the Symbion website

How to register: fill the form below or click here


Title: Exploiting special structure in semidefinite programs
Speaker: Etienne De Klerk, Tilburg University (NL)

Abstract: Semidefinite Programming (SDP) may be seen as a generalization of Linear Programming (LP). In particular, one may extend interior point algorithms for LP to SDP, but it has proven much more difficult to exploit structure in the SDP data during computation. We survey three types of special structure in SDP data:
  • a common `chordal' sparsity pattern of all the data matrices. This structure arises in applications in graph theory, and may also be used to deal with more general sparsity patterns in a heuristic way.
  • low rank of all the data matrices. This structure is common in SDP relaxations of combinatorial optimization problems, and SDP approximations of polynomial optimization problems.
  • the situation where the data matrices are invariant under the action of a permutation group, or, more generally, where the data matrices belong to a low dimensional matrix algebra. Such problems arise in truss topology optimization, particle physics, coding theory, computational geometry, and graph theory.

Title: Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
Speaker: Frank Permenter, MIT (US)

Abstract: We develop a practical semidefinite programming (SDP) facial reduction procedure that utilizes computationally efficient approximations of the positive semidefinite cone. The proposed method simplifies SDPs with no strictly feasible solution
by solving a sequence of easier optimization problems and could be a useful pre-processing step for SDP solvers. We demonstrate effectiveness of the method on SDPs arising in practice, and describe our publicly-available software implementation.
We also give a post-processing procedure for dual solution recovery that generally applies to facial-reduction-based pre-processing techniques. Joint work with Pablo Parrilo.

Title: Solving the pooling problem using semidefinite programming.
Speaker: Joachim Dahl, MOSEK ApS (DK)

Abstract: The pooling problem is a well-studied difficult nonlinear flow-problem with important applications in the oil- and refinery industry. In this talk we review how to solve this difficult non-convex problem using the Lasserre hierarchy of semidefinite relaxations, and we demonstrate how chordal structure can be exploited to solve larger instances.