| The Deflation-Inflation Method for Certain Semidefinite Programming and Maximum Determinant Completion Problems (Extended Abstract) (1998) | |||||||||||||||||
Abstract | |||||||||||||||||
| ) August 13, 1998 Abstract The deflation-inflation convex optimization method is introduced. One result is a simple and practical approximation algorithm for the max cut 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 (max cut ) problem, maximum entropy, maximum determinant completion, Bregman distance, Kullback-Leibler distance, normal (Gaussian) density, Sinkhorn iteration. 1 Introduction Semidefinite programming has emerged as an important and practical optimization framework that is increasingly relevant to ... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||