Journal
JOURNAL OF GLOBAL OPTIMIZATION
Volume 24, Issue 3, Pages 349-370Publisher
KLUWER ACADEMIC PUBL
DOI: 10.1023/A:1020383700229
Keywords
Lagrangian dual; interval Newton method; convex underestimate; quadratically constrained quadratic program
Ask authors/readers for more resources
Convex relaxations can be used to obtain lower bounds on the optimal objective function value of nonconvex quadratically constrained quadratic programs. However, for some problems, significantly better bounds can be obtained by minimizing the restricted Lagrangian function for a given estimate of the Lagrange multipliers. The difficulty in utilizing Lagrangian duality within a global optimization context is that the restricted Lagrangian is often nonconvex. Minimizing a convex underestimate of the restricted Lagrangian overcomes this difficulty and facilitates the use of Lagrangian duality within a global optimization framework. A branch-and-bound algorithm is presented that relies on these Lagrangian underestimates to provide lower bounds and on the interval Newton method to facilitate convergence in the neighborhood of the global solution. Computational results show that the algorithm compares favorably to the Reformulation-Linearization Technique for problems with a favorable structure.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available