Franz Rendl

Algorithms to solve Semidefinite Programs


I will review various methods to solve SDP. The starting point are interior-point path-following methods. The primal-dual variant has turned out to be the most successful approach, we will also briefly touch the primal and dual versions as well.
A critical issue consists in solving the Newton equations. We compare direct versus iterative methods. Moreover, we discuss some more recent methods to solve larger-scale SDP. We discuss the use of the bundle method to work with the Lagrangian dual, thereby decreasing the number of primal constraints.
Finally, we look at some non-standard solution approaches, such as the spectral bundle method, that applies to SDP having the constant trace property, and the 'Boundary Point Method', which is derived from augmented Lagrangian technique applied to the dual SDP.


slides:
are here now



previous abstract back to the doctoralschool website next abstract