Semidefinite programming and an application in combinatorics
Date:
Abstract: As a subfield of convex optimization, semidefinite programming (SDP) was the most exciting development in mathematical programming in the 1990’s, thanks to its several applications in control theory, robust optimization, combinatorial optimization and eigenvalue optimization. Along with linear programming and quadratic programming, SDP has become one of the basic modeling and optimization tools, as more and more problems are modeled as semidefinite programs. In this talk, we introduce some fundamental concepts of SDP and related issues. To be more specific, we talk about semidefinite cone, semidefinite programming and semidefinite representability of a convex set in the relationship with conic quadratic representability. One application of SDP in the problem of stability number of a graph with Lovasz’s approach is considered in the last section.