Abstract
It has been observed that the Handelman’s certificate of positivity of a polynomial over a compact polyhedron offers a hierarchical relaxation scheme for polynomial programs. The Handelman hierarchy seems particularly suitable for a class of combinatorial optimizations that are formulated as a zero-diagonal quadratic program over a hypercube. In this paper, we present an error analysis of Handelman hierarchy applied to the special class of polynomial programs and its implications in the computation of the combinatorial optimization problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arora, S., Bollobás, B., Lovász, L.: Proving integrality gaps without knowing the linear program. In: FOCS ‘02: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pp. 313–322 (2002)
Balas E., Ceria S., Cornuéjols G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58(3), 295–324 (1993)
Cheung K.K.H.: On Lovász-Schrijver lift-and-project procedures on the Dantzig–Fulkerson–Johnson relaxation of the TSP. SIAM J. Optim. 16(2), 380–399 (2005)
Cheung K.K.H.: Computation of the Lasserre ranks of some polytopes. Math. Oper. Res. 32(1), 88–94 (2007)
Cook W., Dash S.: On the matrix-cut rank of polyhedra. Math. Oper. Res. 26(1), 19–30 (2001)
De Klerk E., Laurent M.: Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube. SIAM J. Optim. 20(6), 3104–3120 (2010)
Handelman D.: Representing polynomials by positive linear functions on compact convex polyhedra. Pac. J. Math. 132(1), 35–62 (1988)
Harant J.: Some news about the independence number of a graph. Discuss Math Graph Theory 20(1), 71–80 (2000)
Hong S.-P., Tunçel L.: Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra. Discret. Appl. Math. 156(1), 25–41 (2008)
Lasserre J.B.: Semidefinite programming vs. LP relaxations for polynomial programming. Math. Oper. Res. 27(2), 347–360 (2002)
Laurent M.: A Comparison of the Sherali-Admas, Lovász-Schrijver and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28(3), 470–496 (2003)
Lovász L., Schrijver A.: Cones of matrices and set-functions and 0–1 optimization. SIAM J. Discret. Math. 1(2), 166–190 (1991)
Park M.-J., Hong S.-P.: Rank of handelman hierarchy for max-cut. Oper. Res. Lett. 39(5), 323–328 (2011)
Putinar M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969–984 (1993)
Schmüdgen K.: The K-moment problem for compact semi-algebraic sets. Mathematische Annalen 289(2), 203–206 (1991)
Sherali H.D., Adams W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero–one programmings. SIAM J. Discret. Math. 3(3), 411–430 (1990)
Sherali H.D., Tuncbilek C.H.: A global optimization algorithm for polynomial programming problems using a reformulation linearization technique. J. Glob. Optim. 2(1), 101–112 (1992)
Stephen T., Tunçel L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24(1), 1–7 (1999)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Park, MJ., Hong, SP. Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications. J Glob Optim 56, 727–736 (2013). https://doi.org/10.1007/s10898-012-9906-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-012-9906-3