| NEC Research Institute Technical Report | 1998 |
Abstract: The deflation-inflation convex optimization method is introduced. One result is a simple and practical approximation algorithm for the \maxcut problem based on the semidefinite programming relaxation and analysis of Goemans and Williamson. Another consequence is a closed-form expression for the maximum-determinant completion of a positive definite band matrix. Local and global convergence results are established, along with other properties. The overall development reveals an interesting interplay between the language and outlook of probability, and that of positive definite matrices and mathematical programming.
Keywords: Semidefinite programming, Maximum cut (\maxcut) problem, maximum entropy, maximum determinant completion, Bregman distance, Kullback-Leibler distance, normal (Gaussian) density, Sinkhorn iteration.