A non-convex adaptive regularization approach to binary optimization

Binary optimization is a long-time problem ubiquitous in many engineering applications, e.g., automatic control, cyber-physical systems and machine learning. From a mathematical viewpoint, binary optimization is an NP-hard problem, to solve which one can find some suboptimal strategies in the literature. Among the most popular approaches, semidefinite relaxation has attracted much attention in the last years. In contrast, this work proposes and analyzes a non-convex regularization approach, through which we obtain a relaxed problem whose global minimum corresponds to the true binary solution of the original problem. Moreover, because the problem is non-convex, we propose an adaptive regularization that promotes the descent towards the global minimum. We provide both theoretical results that characterize the proposed model and numerical experiments that prove its effectiveness with respect to state-of-the-art methods.