SCAIM Seminar: Nathan Krislock

During the last two decades, semidefinite optimization has grown into a significant field of research with applications in many diverse areas such as graph theory, distance geometry, combinatorial optimization, low-rank matrix completion, and polynomial optimization.In this talk, I will discuss my work in two of these areas, namely distance geometry and combinatorial optimization.

In distance geometry, Euclidean distance matrices (EDMs) have recently received revived interest due to their use in modern applications such as sensor network localization, protein structure determination, and machine learning.  The second reason for this revived interest is the fact that we now have semidefinite optimization solvers that we can use to solve problems involving EDMs (however, we are limited in the size of problems we can solve efficiently due to the high complexity of these semidefinite solvers).  I will discuss my theoretical contribution relating cliques in the graph of a partial EDM to identifying a reduced problem formulation, and how I used this result to develop numerical methods to solve large-scale instances in each of the three modern applications mentioned above.

In combinatorial optimization, semidefinite optimization is used to efficiently compute high-quality bounds to many difficult (in fact, NP-hard) problems, such as Max-Cut and binary quadratic optimization. This has led to the development of state-of-the-art branch-and-bound methods for solving such problems to optimality.  I will discuss my work on a bounding procedure for Max-Cut which has been obtained by adding a regularization term to the standard semidefinite bound- this allows us to use basic numerical tools (a eigenvalue decomposition method, and a quasi-Newton optimization method) to compute high-quality semidefinite bounds efficiently.  I will show how this new bounding procedure gives a significant improvement over the current state-of-the-art method.