DECOMPOSITION BRANCH-AND-BOUND METHOD FOR GLOBALLY SOLVING LINEARLY CONSTRAINED INDEFINITE QUADRATIC MINIMIZATION PROBLEMS

被引：30

作者：

PHONG, TQ

AN, LTH

TAO, PD

机构：

[1] LMI-INSA Rouen, 76131 Mont Saint Aignan Cedex, Place Emile Blondel

来源：

OPERATIONS RESEARCH LETTERS | 1995年 / 17卷 / 05期

关键词：

GLOBAL MINIMIZATION; INDEFINITE QUADRATIC PROGRAMMING; DECOMPOSITION; BRANCH AND BOUND;

D O I：

10.1016/0167-6377(95)00014-B

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：215 / 220

页数：6

共 12 条

[1] Floudas, Pardalos, A collection of test problems for constrained global optimization algorithms, Lecture Notes in Computer Science, 455, (1990)
[2] Floudas, Visweswaran, A primal-relaxed dual global optimization approach: Theory, J. Optim. Theory Appl., 78, 2, pp. 187-225, (1993)
[3] Horst, Phong, Thoai, de Vries, On solving a d.c. programming problem by a sequence of linear programs, J. Global Optim., 1, pp. 183-203, (1991)
[4] Horst, Tuy, Global Optimization: Deterministic Approaches, (1993)
[5] Pardalos, Glick, Rosen, Global optimization of indefinite quadratic problems, Computing, 39, pp. 281-291, (1987)
[6] Pardalos, Rosen, Constrained global optimization: Algorithms and applications, Lecture Notes in Computer Science, (1987)
[7] Phillips, Rosen, A parallel algorithm for partially separable non-convex global minimization: Linear constraints, Ann. Oper. Res., 25, pp. 101-118, (1990)
[8] Tao, Convergence of subgradient method for computing the bound norm of matrices, Linear Alg. Appl., 62, pp. 163-182, (1984)
[9] Tao, Algorithmes de calcul du maximum d'une forme quadratique sur la boule unité de la norme du maximum, Numerische Mathematik, 45, pp. 377-440, (1985)
[10] Tao, Algorithms for solving a class of nonconvex optimization problems. sub-gradient methods, Fermat Days 85. Mathematics for Optimization, (1986)

← 1 2 →