Many real-world applications, although being non-linear, can be well described by linearized models. Therefore, Linear Programming (LP) became a widely studied and applied technique in many areas of science, industry and economy. Semidefinite Programming (SDP) is an extension of LP. A matrixvariable is optimized over the intersection of the cone of positive semidefinite matrices with an affine space. It turned out, that SDP can provide significantly stronger practical results than LP. Since then SDP turned out to be practical in a lot of different areas, like combinatorial optimization, control theory, engineering, and more recently in polynomial optimization.

Due to the numerous areas of applications, solving SDPs became a widely studied subject. Interior-Point Methods are the most popular algorithms nowadays. Recently, bundle methods and applying an augmented Lagrangian algorithm have been used for solving SDPs.

In this talk I will state the basic concept of SDP. I will show how to apply SDP to approximate the max-cut problem and the coloring problem, two combinatorial optimization problems. Via the SDP relaxations of these two combinatorial optimization problems I will explain the methods for solving SDPs, in particular the recently developed bundle method for max-cut and the boundary point method to compute the Lovasz theta-number.