Rank-one convexification for quadratic optimization problems with step function penalties

2025/04/23 by Soobin Choi, Valentina Cepeda, Choi, Soobin +5
Computer Science · Engineering · Mathematics · #90 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Topology Optimization in Engineering

paper · pdf · doi:10.48550/arxiv.2504.16330

openalex publication_date 2025/04/23 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28

Abstract

We investigate convexification for convex quadratic optimization with step function penalties. Such problems can be cast as mixed-integer quadratic optimization problems, where binary variables are used to encode the non-convex step function. First, we derive the convex hull for the epigraph of a quadratic function defined by a rank-one matrix and step function penalties. Using this rank-one convexification, we develop copositive and semi-definite relaxations for general convex quadratic functions. Leveraging these findings, we construct convex formulations to the support vector machine problem with 0--1 loss and show that they yield robust estimators in settings with anomalies and outliers.

Citations

• Convexification of Multi-period Quadratic Programs with Indicators
• Strong Formulations for Hybrid System Control
• Solving convex QPs with structured sparsity under indicator conditions
• Real-time solution of quadratic optimization problems with banded matrices and indicator variables
• A Parametric Approach for Solving Convex Quadratic Optimization with Indicators Over Trees
• Polyhedral Analysis of Quadratic Optimization Problems with Stieltjes Matrices and Indicators
• Outlier detection in regression: conic quadratic formulations
• Constrained Optimization of Rank-One Functions with Indicator Variables
• Ground(less) Truth: A Causal Framework for Proxy Labels in Human-Algorithm Decision-Making
• Explicit convex hull description of bivariate quadratic sets with indicator variables
• Safe Screening for Logistic Regression with ℓ₀-ℓ₂ Regularization
• On the convex hull of convex quadratic optimization problems with indicators
• Compact extended formulations for low-rank functions with indicator variables
• A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators
• Supermodularity and valid inequalities for quadratic optimization with indicators
• Simultaneous Feature Selection and Outlier Detection with Optimality Guarantees
• Ideal formulations for constrained convex optimization problems with indicator variables
• Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization
• Fairness Evaluation in Presence of Biased Noisy Labels
• Quadratic Optimization with Switching Variables: The Convex Hull for n = 2
• Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives
• Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens
• Rank-one Convexification for Sparse Regression
• Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms
• Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions
• The ALAMO approach to machine learning
• Learning Optimized Risk Scores
• Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
• Best Subset Selection via a Modern Optimization Lens
• Supersparse Linear Integer Models for Optimized Medical Scoring Systems
• Making Risk Minimization Tolerant to Label Noise
• On the mixing set with a knapsack constraint
• Noise Tolerance under Risk Minimization
• A Joint Location-Inventory Model

Related

• 2x2 convexifications for convex quadratic optimization with indicator variables
• New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure
• SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Constructing Tight Quadratic Relaxations for Global Optimization: II. Underestimating Difference-of-Convex (D.C.) Functions