Optimization Online


2x2-convexifications for convex quadratic optimization with indicator variables

Shaoning Han(shaoning***at***usc.edu)
Andres Gomez(gomezand***at***usc.edu)
Alper Atamturk(atamturk***at***berkeley.edu)

Abstract: In this paper, we study the convex quadratic optimization problem with indicator variables. For the bivariate case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the bivariate case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including Shor's SDP relaxation, the optimal perspective relaxation as well as the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems.

Keywords: mixed-integer quadratic optimization, semidefinite programming, perspective formulation, indicator variables, convexification

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

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: University of Southern California, April 2020

Download: [PDF]

Entry Submitted: 04/15/2020
Entry Accepted: 04/15/2020
Entry Last Modified: 04/15/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