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

Thai Quynh Phong; Le Thi Hoai An; Pham Dinh Tao

Oper. Res. Lett. 17, No. 5, 215-220 (1995).

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.

MSC:

90C20	Quadratic programming
90C25	Convex programming

Keywords:

decomposition branch-and-bound approach; global minimization; indefinite quadratic function; \(w\)-subdivision

References:

[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
[5]	L.D. Muu, T.Q. Phong and Pham Dinh Tao, “Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions”, Comput. Optim. Appl.; L.D. Muu, T.Q. Phong and Pham Dinh Tao, “Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions”, Comput. Optim. Appl. · Zbl 0834.90101
[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