Outer-product-free sets for polynomial optimization and oracle-based cuts

• 成果类型: Article
• 署名作者: Bienstock, Daniel; Chen, Chen; Munoz, Gonzalo
• 署名单位: Columbia University; University System of Ohio; Ohio State University; Universidad de O'Higgins
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01484-3
• 发表日期: 2020
• 页码: 105-148
• 关键词: constrained quadratic programs; minimal-inequalities; global optimization; cutting-planes; convex-sets; nonconvex; branch; algorithm; relaxations; ENVELOPES

摘要

This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set S boolean AND P, where S is a closed set, and P is a polyhedron. Given an oracle that provides the distance from a point to S, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidden zones, or S-free sets, derived from the oracle. We also consider the special case of polynomial optimization. Accordingly we develop a theory of outer-product-free sets, where S is the set of real, symmetric matrices of the form xxT. All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify several families of such sets. These families are used to generate strengthened intersection cuts that can separate any infeasible extreme point of a linear programming relaxation efficiently. Computational experiments demonstrate the promise of our approach.