DESEMPEÑO COMPUTACIONAL DE ESTRATEGIAS HÍBRIDAS PARA LA SOLUCIÓN DE PROBLEMAS CUADRÁTICOS NO CONVEXOS CON RESTRICCIONES DE CAJA

Resumen

In this paper the minimization of a non-convex quadratic function under box constraints is considered.
For solving this problem, we propose a hybrid strategy combining a cut and continuation
method with a Branch and Bound procedure, based on double non-negative relaxation. We compare
the results of the new approach with the Branch and Bound method and with the preceding hybrid
algorithm.The in
uence of characteristics of the problem in the algorithm's behavior is explored.
Computational experiments include problems of higher dimension than the ones reported in the referred
literature and show that the new strategy improves the results concern to number of explored
nodes and computation time.
KEYWORDS: Non-convex quadratic programming, Parametric optimization, Branch-and-Bound,
Double non negative relaxation, Semidenite programming.
MSC: 90C20, 90C26.