Quadratic programs with hollows

• 成果类型: Article
• 署名作者: Yang, Boshi; Anstreicher, Kurt; Burer, Samuel
• 署名单位: Clemson University; University of Iowa
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1157-0
• 发表日期: 2018
• 页码: 541-553
• 关键词: trust-region subproblems; constraints; optimization; minimization; sets

摘要

Let be a quadratically constrained, possibly nonconvex, bounded set, and let denote ellipsoids contained in with non-intersecting interiors. We prove that minimizing an arbitrary quadratic over is no more difficult than minimizing over in the following sense: if a given semidefinite-programming (SDP) relaxation for is tight, then the addition of l linear constraints derived from yields a tight SDP relaxation for . We also prove that the convex hull of equals the intersection of the convex hull of with the same l linear constraints. Inspired by these results, we resolve a related question in a seemingly unrelated area, mixed-integer nonconvex quadratic programming.