Rank-One Convexification for Quadratic Optimization Problems with Switching Constraints

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 .

Authors

Institutions

Publication Details

Journal
INFORMS Journal on Optimization
Published
2026-11-16
DOI
https://doi.org/10.1287/ijoo.2025.0124
Primary Topic
Advanced Optimization Algorithms Research
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Rank-One Convexification for Quadratic Optimization Problems with Switching Constraints

Soobin Choi, Andrés Gómez, Shaoning Han, Valentina Cepeda
INFORMS Journal on Optimization
Advanced Optimization Algorithms Research
article

Rank-One Convexification for Quadratic Optimization Problems with Switching Constraints

Soobin Choi, Andrés Gómez, Shaoning Han, Valentina Cepeda
article en

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 .

INFORMS Journal on Optimization
University of Southern California (US), Universidad de Los Andes (CO), National University of Singapore (SG)
Ministry of Education - Singapore
Advanced Optimization Algorithms Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon