Abstract
The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.
Similar content being viewed by others
References
Bomze, I. (1998), On standard quadratic optimization problems, Journal of Global Optimization 13(4): 369-387.
Borchers, B. (1997), CSDP, a C library for semidefinite programming, manuscript, http://www.nmt.edu/_borchers/csdp.html.
Floudas, C.A. and Visweswaran, V. (1995), Quadratic optimization, in Handbook of Global Optimization (R. Horst and P. Pardalos, eds.), Kluwer Academic Publishers, Dordrecht, pp. 217-269.
Garey, M.R. and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, New York.
Helmberg, C., Rendl, F., Vanderbei, R.J. and Wolkowicz, H. (1996), An interior-point method for semidefinite programming, SIAM J. Opt. 6(2): 342-361.
Horst, R., Pardalos, P. and Thoai, N. (1995), Introduction to Global Optimization, Kluwer Academic Publishers, Dordrecht.
Nowak, I. (1996), A branch-and-bound algorithm for computing the global minimum of polynomials by Bernstein-Bézier patches on simplices, Preprint M-09, BTU Cottbus.
Pardalos, M.P. and Wolkowicz, H. (eds.), (1998), Topics in Semidefinite and Interior-Point Methods, Fields Institute Communications Series, Vol. 18, American Mathematical Society.
Ramana, M. and Pardalos, P.M. (1996), Semidefinite programming, in Interior Point Methods of Mathematical Programming, T. Terlaky (ed.), Kluwer Academic Publishers, Dordrecht, 369-398.
Shor, N.Z. (1987), Quadratic optimization problems, Soviet J. Circ. Syst. Sci. 25(6): 1-11.
Vandenberghe, L. and Boyd, S. (1996), Semidefinite programming, SIAM Review 38: 49-95.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nowak, I. A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex. Journal of Global Optimization 14, 357–364 (1999). https://doi.org/10.1023/A:1008315627883
Issue Date:
DOI: https://doi.org/10.1023/A:1008315627883