Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems

arXiv2003.08696MaRDI QIDQ6337027FDOQ6337027

Authors: V. Cerone, Sophie M. Fosson, D. Regruto 

Publication date: 19 March 2020

Abstract: Boolean quadratic optimization problems occur in a number of applications. Their mixed integer-continuous nature is challenging, since it is inherently NP-hard. For this motivation, semidefinite programming relaxations (SDR's) are proposed in the literature to approximate the solution, which recasts the problem into convex optimization. Nevertheless, SDR's do not guarantee the extraction of the correct binary minimizer. In this paper, we present a novel approach to enhance the binary solution recovery. The key of the proposed method is the exploitation of known information on the eigenvalues of the desired solution. As the proposed approach yields a non-convex program, we develop and analyze an iterative descent strategy, whose practical effectiveness is shown via numerical results.

This page was built for publication: Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337027)