On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming

• 成果类型: Article
• 署名作者: Ding, Yichuan; Ge, Dongdong; Wolkowicz, Henry
• 署名单位: Stanford University; Shanghai Jiao Tong University; University of Waterloo
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1100.0473
• 发表日期: 2011
• 页码: 88-104
• 关键词: Bounds

摘要

We analyze two popular semidefinite programming relaxations for quadratically constrained quadratic programs with matrix variables. These relaxations are based on vector lifting and on matrix lifting; they are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline for how to choose a less expensive semidefinite programming relaxation and still obtain a strong bound. The main technique used to show the equivalence and that allows for the simplified constraints is the recognition of a class of nonchordal sparse patterns that admit a smaller representation of the positive semidefinite constraint.