A polyhedral study of nonconvex quadratic programs with box constraints

• 成果类型: Article
• 署名作者: Vandenbussche, D; Nemhauser, GL
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-004-0549-0
• 发表日期: 2005
• 页码: 531-557
• 关键词: Optimization; facets

摘要

By reformulating quadratic programs using necessary optimality conditions, we obtain a linear program with complementarity constraints. For the case where the only constraints are bounds on the variables, we study a relaxation based on a subset of the optimality conditions. By characterizing its convex hull, we obtain a large class of valid inequalities. These inequalities are used in a branch-and-cut scheme, see [13].