ISSN:
1573-2916
Keywords:
Global optimization
;
Nonconvex quadratic programming
;
Semidefinite programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1008315627883
