Applications of Semidefinite Programming

Semidefinite programming is a type of convex optimization that aims to optimize a linear function, the trace of the product of a matrix and the variable matrix X, while subject to nonlinear constraints. In a semidefinite program (SDP), the decision matrix X is required to be positive semidefinite. We examine an interior point method for solving SDPs and explore its application to the Quadratic Assignment Problem (QAP), an NP-hard problem used to assign n facilities to n locations, minimizing the quadratic objective function of the product of distances between locations and flow between facilities. Using a relaxation of the QAP formulation into an SDP, we solve QAP relaxations using the NEOS solver, a web service for numerical optimization, with the interior point method described above