On finitely terminating branch-and-bound algorithms for some global optimization problems

被引：26

作者：

Al-Khayyal, FA ^{[1
]}

Sherali, HD

机构：

[1] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

[2] Virginia Polytech Inst & State Univ, Dept Ind & Syst Engn, Blacksburg, VA 24061 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 2000年 / 10卷 / 04期

关键词：

finite convergence; global optimization; branch-and-bound; concave; bilinear;

D O I：

10.1137/S105262349935178X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Global optimization algorithms are typically terminated with an epsilon-approximate solution after a finite number of iterations. This paper shows how existing in finitely convergent branch-and-bound algorithms can be augmented to guarantee finite termination with an exact global solution for problems having extreme point solutions.

引用

页码：1049 / 1057

页数：9

共 23 条

[1] FINITE CONVERGENCE OF ALGORITHMS FOR NONLINEAR PROGRAMS AND VARIATIONAL-INEQUALITIES [J].

ALKHAYYAL, F ;

KYPARISIS, J .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1991, 70 (02) :319-332

[2] NOTE ON SOLVING LINEAR COMPLEMENTARITY-PROBLEMS AS JOINTLY CONSTRAINED BILINEAR PROGRAMS [J].

ALKHAYYAL, FA .

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1991, 158 (02) :583-589

[3]

ALKHAYYAL FA, 1983, MATH OPER RES, V8, P272

[4] A FINITE ALGORITHM FOR CONCAVE MINIMIZATION OVER A POLYHEDRON [J].

BENSON, HP .

NAVAL RESEARCH LOGISTICS, 1985, 32 (01) :165-177

[5] A FINITE CONCAVE MINIMIZATION ALGORITHM USING BRANCH-AND-BOUND AND NEIGHBOR GENERATION [J].

BENSON, HP ;

SAYIN, S .

JOURNAL OF GLOBAL OPTIMIZATION, 1994, 5 (01) :1-14

[6]

CHARNES A, 1963, 84 NW U OFF NAV RES

[7]

CHARNES KO, 1965, 129 NW U SYST

[8]

GACS P, 1981, MATH PROGRAM STUD, V14, P61, DOI 10.1007/BFb0120921

[9]

Hadamard J., 1893, Bull. Sci. Math., V2, P240

[10] EXHAUSTIVE NONDEGENERATE CONICAL PROCESSES FOR CONCAVE MINIMIZATION ON CONVEX POLYTOPES [J].

HAMAMI, M ;

JACOBSEN, SE .

MATHEMATICS OF OPERATIONS RESEARCH, 1988, 13 (03) :479-487

← 1 2 3 →