New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability (Q930342)

For the problem of minimizing a quadratic indefinite form over a simplex known and new bounds for the optimal objective function value are derived. Main tools for this are semidefinite programming and the decomposition of the objective function into the difference of two convex functions. The different bounds are completely compared and a new bound is developed which dominates all the other bounds, especially also Shrijver's improvement of Lovasz's \(\theta\) function. Interesting results are also obtained with respect to the Lagrangean duality, where tight dual formulations are found. Special topics in this interesting and comprehensive paper are convex underestimation bounds, Nowak's bound and copositive as well as decomposition bounds.