A relaxation method for nonconvex quadratically constrained quadratic programs |
| |
| Authors: | Faiz A Al-Khayyal Christian Larsen Timothy Van Voorhis |
| |
| Institution: | (1) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia, USA;(2) Department of Management, University of Odense, Odense, Denmark |
| |
| Abstract: | We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489. |
| |
| Keywords: | Quadratic constraints quadratic programming relaxation linearization technique branch and bound global optimization |
| 本文献已被 SpringerLink 等数据库收录！ |
