Convex hull of two quadratic or a conic quadratic and a quadratic inequality

• 成果类型: Article
• 署名作者: Modaresi, Sina; Vielma, Juan Pablo
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1084-5
• 发表日期: 2017
• 页码: 383-409
• 关键词: chvatal-gomory closure; cuts; progress

摘要

In this paper we consider an aggregation technique introduced by YA +/- ldA +/- ran (J Math Control Inf 26:417-450, 2009) to study the convex hull of regions defined by two quadratic inequalities or by a conic quadratic and a quadratic inequality. YA +/- ldA +/- ran (2009) shows how to characterize the convex hull of open sets defined by two strict quadratic inequalities using Linear Matrix Inequalities. We show how this aggregation technique can be easily extended to yield valid conic quadratic inequalities for the convex hull of open sets defined by two strict quadratic inequalities or by a strict conic quadratic and a strict quadratic inequality. We also show that for sets defined by a strict conic quadratic and a strict quadratic inequality, under one additional containment assumption, these valid inequalities characterize the convex hull exactly. We also show that under certain topological assumptions, the results from the open setting can be extended to characterize the closed convex hull of sets defined with non-strict conic and quadratic inequalities.