On the gap between the quadratic integer programming problem and its semidefinite relaxation

• 成果类型: Article
• 署名作者: Malik, U; Jaimoukha, IM; Halikias, GD; Gungah, SK
• 署名单位: Imperial College London; City St Georges, University of London
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0692-2
• 发表日期: 2006
• 页码: 505-515
• 关键词: minimum trace; maximum cut; optimization; matrices; set

摘要

Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): gamma := max {x(T) Qx : x is an element of {-1, 1}(n)} <= min {trace(D) : D - Q greater than or similar to 0} =: (gamma) over bar where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap (gamma) over bar gamma. We establish the uniqueness of the SDR solution and prove that gamma = (gamma) over bar if and only if gamma(r) := n(-1) max {x(T) VVT x : x is an element of {-1, 1}(n)} = 1 where V is an orthogonal matrix whose columns span the (r - dimensional) null space of D - Q and where D is the unique SDR solution. We also give a test for establishing whether gamma = (gamma) over bar that involves 2(r-1) function evaluations. In the case that gamma(r) < 1 we derive an upper bound on gamma which is tighter than <(gamma)over bar>. Thus we show that 'breaching' the SDR gap for the QIP problem is as difficult as the solution of a QIP with the rank of the cost function matrix equal to the dimension of the null space of D - Q. This reduced rank QIP problem has been recently shown to be solvable in polynomial time for fixed r.