Abstract

Semidefinite Programming (SDP) is a mathematical technique that came into prominence in the late 1990s with the rise of Machine Learning. In fact, SDPs can be used for classification. In addition, SDPs represent a wide range of optimization problems from scheduling to maximal violations of quantum inequalities. This talk will explore the foundations of SDP in Linear Programming (LP) and some applications of LP. Then, the talk will continue onto SDPs and the landmark relaxation of the NP-Complete MAX -CUT problem that first demonstrated the power of SDPs. The talk will conclude with the links between LP, SDP , and other “programming” problems with respect to complexity.