Optimization Online


On the convexification of constrained quadratic optimization problems with indicator variables

Linchuan Wei(LinchuanWei2022***at***u.northwestern.edu)
Andres Gomez(gomezand***at***usc.edu)
Simge Kucukyavuz(simge***at***northwestern.edu)

Abstract: Motivated by modern regression applications, in this paper, we study the convexification of quadratic optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear objective, indicator variables, and combinatorial constraints. We prove that for a separable quadratic objective function, the perspective reformulation is ideal independent from the constraints of the problem. In contrast, while rank-one relaxations cannot be strengthened by exploiting information from k-sparsity constraint for k greater than one, they can be improved for other constraints arising in inference problems with hierarchical structure or multi-collinearity.

Keywords: Convexification, perspective formulation, indicator variables, quadratic optimization, combinatorial constraints

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

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Research report AG 20.01, ISE, University of Southern California, January 2020

Download: [PDF]

Entry Submitted: 01/14/2020
Entry Accepted: 01/14/2020
Entry Last Modified: 01/14/2020

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