Quadratic Optimization Through the Lens of Adjustable Robust Optimization

Quadratic optimization (QO) has been studied extensively in the literature due to its applicability in many practical problems. Although practical, it is known that QO problems are generally NP-hard. Therefore, researchers developed many approximation methods to find good solutions. In this paper, we analyze QO problems using robust optimization techniques. To this end, we first show that any QO problem can be reformulated as a disjoint biconvex QO problem. Then, we provide an equivalent adjustable robust optimization (ARO) reformulation and leverage the methods available in the literature on ARO to approximate this reformulation. More specifically, we show that using a so-called decision rule technique to approximate the ARO reformulation is equivalent to using a reformulation-linearization technique on the original QO problem. Additionally, we design an algorithm that can find a close-to-optimal solution based on our new reformulations. Our numerical results demonstrate the efficiency of our algorithm to find near-optimal solutions, particularly for large-sized instances, compared with off-the-shelf solvers and state-of-art approaches.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous.

Funding: The research of A. Khademi was part supported by a grant from IPM [Grant 1404900034].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0577) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0577). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.