A Linear Programming Approach to Semidefinite Programming Problems

A semidefinite programming problem can be regarded as a convex nonsmooth optimization problem, so it can be represented as a semi-infinite linear programming problem. Thus, in principle, it can be solved using a cutting plane approach; we describe such a method. The cutting plane method uses an interior point algorithm to solve the linear programming relaxations approximately, because this resulted in the generation of better constraints than a simplex cutting plane method. Further, the bundle method of Helmberg and Rendl can be used to generate a set of linear constraints. Typically, these alone are not sufficient to give a good linear programming relaxation. Nonetheless, if they are used in conjunction with some families of problem specific constraints, tight LP relaxations can be obtained.