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

DOI10.1007/S10107-021-01671-WMaRDI QIDQ2044962zbMATH OpenOpenAlexFDO

Authors Kurt M. Anstreicher, Samuel Burer

Publication date 11 August 2021

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

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

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)

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.

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

Cites work

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

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)