Article ID: | iaor20132760 |
Volume: | 55 |
Issue: | 2 |
Start Page Number: | 379 |
End Page Number: | 398 |
Publication Date: | Jun 2013 |
Journal: | Computational Optimization and Applications |
Authors: | Li Duan, Sun Xiaoling, Xia Yong, Sheu Ruey-Lin |
Keywords: | programming: quadratic, heuristics |
We focus in this paper the problem of improving the semidefinite programming (SDP) relaxations for the standard quadratic optimization problem (standard QP in short) that concerns with minimizing a quadratic form over a simplex. We first analyze the duality gap between the standard QP and one of its SDP relaxations known as ‘strengthened Shor’s relaxation’. To estimate the duality gap, we utilize the duality information of the SDP relaxation to construct a graph