On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables

Linchuan Wei, Andrés Gómez*, Simge Küçükyavuz

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 [Formula Presented], they can be improved for other constraints arising in inference problems with hierarchical structure or multi-collinearity.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings
EditorsDaniel Bienstock, Giacomo Zambelli
PublisherSpringer
Pages433-447
Number of pages15
ISBN (Print)9783030457709
DOIs
StatePublished - 2020
Event21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 - London, United Kingdom
Duration: Jun 8 2020Jun 10 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020
CountryUnited Kingdom
CityLondon
Period6/8/206/10/20

Keywords

  • Combinatorial constraints
  • Convexification
  • Indicator variables
  • Perspective formulation
  • Quadratic optimization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables'. Together they form a unique fingerprint.

Cite this