Quadratic Optimization with Switching Variables: The Convex Hull for $n = 2

Samuel Burer; Kurt Anstreicher

doi:10.48550/arxiv.2002.04681

Back

Quadratic Optimization with Switching Variables: The Convex Hull for $n = 2

Preprint

Open access

Quadratic Optimization with Switching Variables: The Convex Hull for $n = 2

Samuel Burer and Kurt Anstreicher

02/11/2020

DOI: 10.48550/arxiv.2002.04681

Files and links (1)

url

https://doi.org/10.48550/arxiv.2002.04681View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

We consider quadratic optimization in variables $(x,y)$ where $0\le x\le y$, and $y\in\{0,1\}^n$. Such binary $y$ are commonly refered to as "indicator" or "switching" variables and occur commonly in applications. One approach to such problems is based on representing or approximating the convex hull of the set $\{ (x,xx^T, yy^T) : 0\le x\le y\in\{0,1\}^n\}$. A representation for the case $n=1$ is known and has been widely used. We give an exact representation for the case $n=2$ by starting with a disjunctive representation for the convex hull and then eliminating auxilliary variables and constraints that do not change the projection onto the original variables. An alternative derivation for this representation leads to an appealing conjecture for a simplified representation of the convex hull for $n=2$ when the product term $y_1y_2$ is ignored.

Mathematics - Optimization and Control

Details

Title: Subtitle: Quadratic Optimization with Switching Variables: The Convex Hull for $n = 2
Creators: Samuel Burer
Kurt Anstreicher
Resource Type: Preprint
DOI: 10.48550/arxiv.2002.04681
Language: English
Date posted: 02/11/2020
Academic Unit: Business Analytics; Industrial and Systems Engineering; Computer Science
Record Identifier: 9984380704502771

Metrics

25 Record Views