Solving convex QPs with structured sparsity under indicator conditions

2024/11/18 by Bienstock, Daniel, Chen, Tongtong · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2411.11722

Abstract

We study convex optimization problems where disjoint blocks of variables are controlled by binary indicator variables that are also subject to conditions, e.g., cardinality. Several classes of important examples can be formulated in such a way that both the objective and the constraints are separable convex quadratics. We describe a family of polynomial-time approximation algorithms and negative complexity results.

Cited by

• Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators

Related

• A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators
• A note on quadratic constraints with indicator variables: Convex hull description and perspective relaxation
• 2x2 convexifications for convex quadratic optimization with indicator variables
• Sparse Conic Reformulation of Structured QCQPs based on Copositive Optimization with Applications in Stochastic Optimization
• An Outer Approximation Method for Solving Mixed-Integer Convex Quadratic Programs with Indicators