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.

Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems / Cerone, Vito; Fosson, Sophie; REGRUTO TOMALINO, Diego. - ELETTRONICO. - vol. 53 n.2:(2020), pp. 1894-1899. ((Intervento presentato al convegno 21th IFAC World Congress tenutosi a Berlin, Germany (Virtual) nel July 12-17, 2020 [10.1016/j.ifacol.2020.12.2578].

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

Vito Cerone;Sophie Fosson;Diego Regruto
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.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S2405896320333309-main.pdf

accesso aperto

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Creative commons
Dimensione 599.11 kB
Formato Adobe PDF
599.11 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2847109