Rank-One Convexification for Quadratic Optimization Problems with Switching Constraints
Abstract
We investigate convexification for convex quadratic optimization with switching constraints. Such problems can be cast as mixed-integer quadratic optimization problems, where binary variables are used to encode whether a linear inequality is active or not. First, we derive the convex hull for the epigraph of a quadratic function defined by a rank-one matrix and switching penalties. Using this rank-one convexification, we develop copositive and semidefinite relaxations for general convex quadratic functions. Leveraging these findings, we construct convex formulations to the support vector machine problem with 0–1 loss. The resulting methods scale well with the number of data points, provided that the number of features is small. In terms of statistical performance, the proposed methods outperform standard support vector machine problems with hinge loss in data sets corrupted by outliers.
Funding: A. Gómez and S. Choi were supported by the Air Force Office of Scientific Research [Grants FA9550-24-1-0086 and FA9550-22-1-0369] and the National Science Foundation [Grants 2152777 and 2112533]. S. Han was supported by the NUS (Suzhou) Research Institute [Grant SZ2025-03] and the Academic Research Fund Tier 1 from the Ministry of Education, Singapore [Grant FY2024].
Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2025.0124.

