Semidefinite programming for discrete optimization and matrix completion problems (Q697582): Difference between revisions

This paper presents a survey on two important areas of applications for semi-definite programming (SDP), namely discrete optimization and matrix completion problems. The first part is devoted to (Lagrangian) SDP relaxations of discrete optimization problems. First of all several relaxations of the max-cut problem (MC) are given and their equivalence to the SDP relaxation is shown. The main algorithms proposed to compute SDP bounds and some qualitative results about them are shortly overviewed. New SDP relaxations of the MC are then obtained applying a recipe due to [\textit{S. Poljak, F. Rendl, H. Wolkowicz, J. Glob. Optim. 7, No. 1, 51--73 (1995; Zbl 0843.90088)]. This recipe is applied at the end of the first part to other discrete optimization problems including graph partitioning, max clique, etc. In the second part several SDP algorithms for the positive semidefinite and the Euclidean distance matric completion problems are presented. The algorithms are shown to be efficient for large sparse problems. Some existence results for completions and an approach to solving large sparse completion problems are given. A similar approach, which does not take adavantage of sparcity and has difficulties for solving large sparse problems, is then presented for Euclidean distance matrix completion. Finally a new characterization of Euclidean distance matrices is given and an algorithm exploiting succesfully sparsity is derived from this characterization.}