How to convexify the intersection of a second order cone and a nonconvex quadratic

• 成果类型: Article
• 署名作者: Burer, Samuel; Kilinc-Karzan, Fatma
• 署名单位: University of Iowa; Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1045-z
• 发表日期: 2017
• 页码: 393-429
• 关键词: global optimization method; disjunctive cuts; alpha-bb; PROGRAMS; PERSPECTIVE; constraints; algorithm

摘要

A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown-by several authors using different techniques-that the convex hull of the intersection of an ellipsoid, , and a split disjunction, with , equals the intersection of with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form and , where is a SOCr cone, is a nonconvex cone defined by a single homogeneous quadratic, and H is an affine hyperplane. Under several easy-to-verify conditions, we derive simple, computable convex relaxations and , where is a SOCr cone. Under further conditions, we prove that these two sets capture precisely the corresponding conic/convex hulls. Our approach unifies and extends previous results, and we illustrate its applicability and generality with many examples.