2020/03/19 by V. Cerone, Sophie M. Fosson, Cerone, V. +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Error Correcting Code Techniques #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2003.08696
openalex publication_date 2020/03/19 · openalex created_date 2020/03/23 · openalex updated_date 2026/07/28
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.