Quadratic optimization with switching variables: the convex hull for n=2

DOI10.1007/S10107-021-01671-WzbMATH Open1473.90104arXiv2002.04681OpenAlexW3177377053MaRDI QIDQ2044962FDOQ2044962

Authors: Kurt M. Anstreicher, Samuel Burer 

Publication date: 11 August 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We consider quadratic optimization in variables $(x,y)$ where $0lexley$, and $yin{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,x{x}^T,y{y}^T):0lexleyin{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_1{y}_2$ is ignored.

Full work available at URL: https://arxiv.org/abs/2002.04681

Recommendations

• \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables
• Convex hull representations of special monomials of binary variables
• Computable representations for convex hulls of low-dimensional quadratic forms
• Strong formulations for conic quadratic optimization with indicator variables
• Perspective reformulations of mixed integer nonlinear programs with indicator variables

zbMATH Keywords

semidefinite programmingquadratic optimizationconvex hullswitching variablesperspective cone

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22) Mixed integer programming (90C11)

Cites Work

• Matrix Analysis
• Convex programming for disjunctive convex optimization
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Perspective cuts for a class of convex 0-1 mixed integer programs
• A strong conic quadratic reformulation for machine-job assignment with controllable processing times
• On the Matrix Equation X′X = A
• A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Computable representations for convex hulls of low-dimensional quadratic forms
• The Convex Envelope of (n–1)-Convex Functions
• Valid Inequalities for the Pooling Problem with Binary Variables
• On nonconvex quadratic programming with box constraints
• Perspective reformulations of mixed integer nonlinear programs with indicator variables
• Polynomial optimization, sums of squares, and applications
• Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach
• Convex quadratic relaxations for mixed-integer nonlinear programs in power systems
• Strong formulations for quadratic optimization with M-matrices and indicator variables
• On valid inequalities for quadratic programming with continuous variables and binary indicators

Cited In (4)

• \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables
• A graph-based decomposition method for convex quadratic optimization with indicators
• Permanently going back and forth between the ``quadratic world and the ``convexity world in optimization
• On the convex hull of convex quadratic optimization problems with indicators

This page was built for publication: Quadratic optimization with switching variables: the convex hull for \(n=2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2044962)