Tutte seminar - Toh Kim Chuan

Semidefinite programming: algorithms and applications

Abstract:

Semidefinite programming (SDP) problems are linear optimization problems over the set of positive semidefinite symmetric matrices. The last two decades have seen dramatic advances in the theory and practice of SDP, stimulated in part by the realization that SDP is an extremely powerful modeling tool. Applications of SDP include signal processing, relaxations of combinatorial and polynomial optimization problems, covariance matrix estimation, and sensor network localization. The first part of the talk will describe several applications, such as matrix completion, that have attracted recent interest in large scale SDP. The second part focuses on algorithms for solving SDP. First, we present primal-dual path-following interior-point methods (IPMs) for solving medium scale SDPs and demonstrate that such SDPs can efficiently be solved if structures are properly exploited. Next, we present inexact IPMs (for which linear systems are solved by iterative solvers) for solving large scale SDPs and discuss the inherent limitations of such methods. Finally, we present augmented Lagrangian methods (ALMs) for solving large scale SDPs and discuss their advantages over inexact IPMs. Numerical experiments on a variety of large SDPs show that the ALMs can be very efficient when the SDPs are nondegenerate.