The quadratically-constrained quadratic program

Minimizing a nonconvex quadratic function over a nonconvex feasible region described by a set of nonconvex quadratic constraints is a difficult problem because many local optimal solutions could exist. In this thesis, global optimization algorithms are used which surmount this obstacle. Two ideas are explored: a branch and bound algorithm known as the Reformulation-Linearization Technique and the application of d.c. programming techniques.; The Reformulation-Linearization Technique solves linear relaxations which bound the optimal objective function value of the original problem. Ideas are explored which improve the algorithm's computational effectiveness so that it can be more easily applied to larger problems. Nonlinear programming techniques are used to find local optimal solutions. The interval Newton method is used within the branch and bound framework to accelerate convergence near an optimal solution and to eliminate branches which do not contain the optimal solution. A method for finding tighter lower bounds is presented. Computational results study the impact of these ideas.; Two of the most successful approaches to d.c. programming problems (which includes the quadratically constrained quadratic program) are outer approximation and conical branch and bound algorithms. These methods are explained and two strategies are given for applying these to quadratically constrained problems. The relative effectiveness of these strategies is compared by solving test problems using both the outer approximation and branch and bound algorithms.