Abstract
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 G ∗. The estimation can be then reduced to a two-phase problem of enumerating first all the minimal vertex covers of G ∗ and solving next a family of second-order cone programming problems. When there is a nonzero duality gap, this duality gap estimation can lead to a strictly tighter lower bound than the strengthened Shor’s SDP bound. With the duality gap estimation improving scheme, we develop further a heuristic algorithm for obtaining a good approximate solution for standard QP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anstreicher, K.M., Burer, S.: D. C. versus copositive bounds for standard QP. J. Glob. Optim. 33, 299–312 (2005)
Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124, 33–43 (2010)
Bomze, I.M.: On standard quadratic optimization problems. J. Glob. Optim. 13, 369–387 (1998)
Bomze, I.M., De Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24(2), 163–185 (2002)
Bomze, I.M., Dür, M., De Klerk, E., Roos, C., Quist, A.J., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000)
Bomze, I.M., Locatelli, M., Tardella, F.: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. 115, 31–64 (2008)
Dukanovic, I., Rendl, F.: Copositive programming motivated bounds on the stability and the chromatic numbers. Math. Program. 121, 249–268 (2010)
Grant, M., Boyd, S.C.V.: Matlab software for disciplined convex programming, version 1. 21 (2010). http://cvxr.com/cvx
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)
Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: Weismantel, R., Aardal, K., Nemhauser, G. (eds.) Handbook on Discrete Optimization, pp. 393–514. Elsevier, Amsterdam (2005)
Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1–7 (1979)
Luz, C., Schrijver, A.: A convex quadratic characterization of the Lovász theta number. SIAM J. Discrete Math. 19(2), 382–387 (2005)
Maxfield, J.E., Minc, H.: On the matrix equation X′X=A. Proc. Edinb. Math. Soc. 13, 125–129 (1963)
McEliece, R.J., Rodemich, E.R., Rumsey, H.C.: The Lovász’ bound and some generalizations. J. Comb. Inf. Syst. Sci. 3, 134–152 (1978)
Meyer, C.D.: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia (2000)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17, 533–540 (1965)
Nesterov, Y., Nemirovsky, A.: Interior-Point Polynomial Methods in Convex Programming. SIAM, Philadelphia (1994)
Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology, CA (2000)
Rosgen, B., Stewart, L.: Complexity results on graphs with few cliques. Discrete Math. Theor. Comput. Sci. 9, 127–136 (2007)
Schrijver, A.: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Theory 25, 425–429 (1979)
Sun, X.L., Liu, C.L., Li, D., Gao, J.J.: On duality gap in binary quadratic programming. J. Glob. Optim. 53, 255–269 (2012)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505–517 (1977)
Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996)
Xia, Y., Sun, X.L., Li, D., Zheng, X.J.: On the reduction of duality gap in box constrained nonconvex quadratic program. SIAM J. Optim. 21, 706–729 (2011)
Zheng, X.J., Sun, X.L., Li, D., Xia, Y.: Duality gap estimation of linear equality constrained binary quadratic programming. Math. Oper. Res. 35, 864–880 (2010)
Acknowledgements
The authors are grateful to the two anonymous referees for their valuable comments and suggestions that have greatly helped the authors improve the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by Taiwan NSC 98-2115-M-006-010-MY2, by National Center for Theoretical Sciences of Taiwan(South), by Research Grants Council of Hong Kong under grants 414207, 414808 and 414610, by National Natural Science Foundation of China under grants 10971034, 70832002 and 11001006, by the fund of State Key Laboratory of Software Development Environment under grant SKLSDE-2011ZX-15.
Rights and permissions
About this article
Cite this article
Xia, Y., Sheu, RL., Sun, X. et al. Tightening a copositive relaxation for standard quadratic optimization problems. Comput Optim Appl 55, 379–398 (2013). https://doi.org/10.1007/s10589-012-9522-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-012-9522-7