Thai Quynh Phong, Le Thi Hoai An, Pham Dinh Tao: "On Globally Solving Linearly Constrained Indefinite Quadratic Minimization Problems by Decomposition Branch and Bound Method".

Abstract: A decomposition branch and bound approach is considered for the global minimization of an indefinite quadratic function over a polytope. The objective function is a sum of a nonseparable convex part and a separable concave part. In many large-scale problems the number of convex variables is much larger than that of concave variables. Taking advantage of this we use a branch and bound method where branching proceeds by rectangular subdivision of the subspace of concave variables. With the help of an easily constructed convex underestimator of the objective function, a lower bound is obtained by solving a convex quadratic programming problem. Three variants using exhaustive, adaptive and w-subdivision are discussed. Computational results are presented for problems with 10–20 concave variables and up to 200 convex variables.

 

Keywords: Global minimization;  Indefinite quadratic programming;  Decomposition;  Branch and bound.
 
Citation: Thai Quynh Phong, Le Thi Hoai An and Pham Dinh Tao, On Globally Solving Linearly Constrained Indefinite Quadratic Minimization Problems by Decomposition Branch and Bound Method. RAIRO,Recherche Opérationnelle, vol. 30, no1, pp. 31-49, 1996. 
 
Link to download