Decomposition branch and bound method for globally solving linearly constrained indefinite quadratic minimization problems. (English) Zbl 0858.90102

Summary: 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.


90C20 Quadratic programming
90C25 Convex programming
Full Text: DOI


[1] Floudas, C. A.; Pardalos, P. M., A collection of test problems for constrained global optimization algorithms, (Goos, G.; Hartmanis, J., Lecture Notes in Computer Science, Vol. 455 (1990), Springer: Springer Berlin) · Zbl 0931.92014
[2] Floudas, C. A.; Visweswaran, V., A primal-relaxed dual global optimization approach: Theory, J. Optim. Theory Appl., 78, 2, 187-225 (1993) · Zbl 0796.90056
[3] Horst, R.; Phong, T. Q.; Thoai, N. V.; de Vries, J., On solving a d.c. programming problem by a sequence of linear programs, J. Global Optim., 1, 183-203 (1991) · Zbl 0755.90076
[4] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (1993), Springer: Springer Berlin, New York
[6] Pardalos, P. M.; Glick, J. H.; Rosen, J. B., Global optimization of indefinite quadratic problems, Computing, 39, 281-291 (1987) · Zbl 0627.65072
[7] Pardalos, P. M.; Rosen, J. B., Constrained global optimization: Algorithms and applications, (Goos, G.; Hartmans, J., Lecture Notes in Computer Science (1987), Springer: Springer Berlin), number 268 · Zbl 0638.90064
[8] Phillips, A. T.; Rosen, J. B., A parallel algorithm for partially separable non-convex global minimization: Linear constraints, Ann. Oper. Res., 25, 101-118 (1990) · Zbl 0723.90063
[9] Tao, Pham D., Convergence of subgradient method for computing the bound norm of matrices, Linear Alg. Appl., 62, 163-182 (1984) · Zbl 0563.65029
[10] Tao, Pham D., Algorithmes de calcul du maximum d’une forme quadratique sur la boule unité de la norme du maximum, Numerische Mathematik, 45, 377-440 (1985)
[11] Tao, Pham D., Algorithms for solving a class of nonconvex optimization problems. sub-gradient methods, (Hiriat Urruty, J. B., Fermat Days 85. Mathematics for Optimization (1986), Elsevier, North-Holland)
[12] Tao, Pham D.; Bernoussi, El, Duality in d.c. (difference of convex functions) optimization. subgradient methods, (Hoffman, K. H.; etal., Trends in Mathematical Optimization, Vol. 84 of International Series fo Numerische Mathematik (1988), Birkhauser) · Zbl 0634.49009
[13] Visweswaran, V.; Floudas, C. A., New properties and computational improvement of the GOP algorithms with quadratic objective functions and constraints, J. Global Optim., 3, 439-462 (1993) · Zbl 0795.90070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.