Optimization Online


A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators

Peijing Liu(peijingl***at***usc.edu)
Salar Fattahi(fattahi***at***umich.edu)
Andres Gomez(gomezand***at***usc.edu)
Simge Kucukyavuz(simge***at***northwestern.edu)

Abstract: In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This enables us to construct a compact extended formulation for the closure of the convex hull of the epigraph of the mixed-integer convex problem. Furthermore, we propose a novel decomposition method for general (sparse) Q, which leverages the efficient algorithm for the path case. Our computational experiments demonstrate the effectiveness of the proposed method compared to state-of-the-art mixed-integer optimization solvers.

Keywords: Quadratic optimization, indicator variables, sparsity, decomposition, graphical models, Fenchel dual, convex hull

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Applications -- Science and Engineering (Statistics )

Citation: Technical report, USC, October 2021

Download: [PDF]

Entry Submitted: 10/21/2021
Entry Accepted: 10/21/2021
Entry Last Modified: 10/21/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society