Abstract :

In this talk we shall discuss the design and analysis of approximation algorithms for nonconvex quadratic optimization, using the so-called Semidefinite Programming (SDP) relaxation approach. Semidefinite Programming is a recently developed tool in optimization. A great deal of advancement has been made in the past 15 years with regard to the theoretical properties, solution methods, and practical applications of SDP. As one particular application, SDP has been used to solve NP-hard combinatorial problems. The first such successful example in this category is perhaps the celebrated 0.878-approximation algorithm of Goemans and Williamson (1995) for the max-cut problem. In this talk we shall present some new results on using the SDP relaxation method for solving nonconvex quadratic optimization with inequality constraints.