Skip to main content
Log in

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bomze, I. (1998), On standard quadratic optimization problems, Journal of Global Optimization 13(4): 369-387.

    Google Scholar 

  2. Borchers, B. (1997), CSDP, a C library for semidefinite programming, manuscript, http://www.nmt.edu/_borchers/csdp.html.

  3. 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.

    Google Scholar 

  4. Garey, M.R. and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, New York.

    Google Scholar 

  5. 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.

    Google Scholar 

  6. Horst, R., Pardalos, P. and Thoai, N. (1995), Introduction to Global Optimization, Kluwer Academic Publishers, Dordrecht.

    Google Scholar 

  7. 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.

  8. Pardalos, M.P. and Wolkowicz, H. (eds.), (1998), Topics in Semidefinite and Interior-Point Methods, Fields Institute Communications Series, Vol. 18, American Mathematical Society.

  9. 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.

    Google Scholar 

  10. Shor, N.Z. (1987), Quadratic optimization problems, Soviet J. Circ. Syst. Sci. 25(6): 1-11.

    Google Scholar 

  11. Vandenberghe, L. and Boyd, S. (1996), Semidefinite programming, SIAM Review 38: 49-95.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008315627883

Navigation