Article ID: | iaor2002478 |
Country: | United States |
Volume: | 107 |
Issue: | 2 |
Start Page Number: | 331 |
End Page Number: | 354 |
Publication Date: | Nov 2000 |
Journal: | Journal of Optimization Theory and Applications |
Authors: | Thoai N.V. |
Keywords: | duality |
The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.