Optimization Online


On the convex hull of convex quadratic optimization problems with indicators

Linchuan Wei (linchuanwei2022***at***u.northwestern.edu)
Alper Atamturk (atamturk***at***berkeley.edu)
Andres Gomez (gomezand***at***usc.edu)
Simge Kucukyavuz (simge***at***northwestern.edu)

Abstract: We consider the convex quadratic optimization problem with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of a single positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are ``finitely generated." In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.

Keywords: Convexification, quadratic optimization, indicator variables

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

Citation: Technical report, USC, December 2021

Download: [PDF]

Entry Submitted: 12/31/2022
Entry Accepted: 01/01/2022
Entry Last Modified: 01/02/2022

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