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

• 成果类型: Article
• 署名作者: Anstreicher, Kurt M.; Burer, Samuel
• 署名单位: University of Iowa
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01671-w
• 发表日期: 2021
• 页码: 421-441
• 关键词: integer nonlinear programs

摘要

We consider quadratic optimization in variables (x, y) where 0 <= x <= y, and y is an element of {0, 1}(n). Such binary variables are commonly referred 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 <= x <= y is an element of{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 auxiliary 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.