Global Minimization in Nonconvex All-Quadratic Programming

Gary R. Reeves
Additional contact information
Gary R. Reeves: Miami University

Management Science, 1975, vol. 22, issue 1, 76-86

Abstract: This paper describes a branch and bound algorithm for the global minimization of a quadratic objective function subject to quadratic constraints over a bounded interval. No assumptions are made regarding the convexity of either the objective or the constraints. The algorithm consists of three basic steps. First, a local minimum is identified. Next, an interval surrounding this point over which the point is global is determined and eliminated. This interval is determined using linear programming techniques. Finally, bounding convex envelope approximating problems are constructed and solved globally over any remaining intervals. Intervals with bounds greater than the best local minimum objective value are eliminated. Successive iterations of the algorithm take place over the current remaining interval with lowest bound. The algorithm terminates when all intervals have been eliminated. Convergence of the algorithm to a global minimum "within \epsilon " in a finite number of iterations is demonstrated. The algorithm has been programmed and tested on a wide range of problems. Computational results have been encouraging. They indicate that for problems tested the algorithm determined a good feasible local minimum rapidly. As problem size increased the majority of time was spent not in determining a local minimum but in verifying that the minimum was global.

Date: 1975
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.22.1.76 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:22:y:1975:i:1:p:76-86

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().