A RELAXATION METHOD FOR NONCONVEX QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMS

被引：81

作者：

ALKHAYYAL, FA

LARSEN, C

VANVOORHIS, T

机构：

[1] GEORGIA INST TECHNOL,SCH IND & SYST ENGN,ATLANTA,GA 30332

[2] ODENSE UNIV,DEPT MANAGEMENT,ODENSE,DENMARK

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 1995年 / 6卷 / 03期

关键词：

QUADRATIC CONSTRAINTS; QUADRATIC PROGRAMMING; RELAXATION LINEARIZATION TECHNIQUE; BRANCH AND BOUND; GLOBAL OPTIMIZATION;

D O I：

10.1007/BF01099462

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is nonconvex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.

引用

页码：215 / 230

页数：16

共 27 条

[21]

Press W.H., 1994, NUMERICAL RECIPES C, V2nd ed.

[22]

RUTENBERG DP, 1971, MANAGE SCI B-APPL, V18, pB220

[23]

SHERALI HD, 1992, J GLOBAL OPTIM, V2, P101, DOI DOI 10.1007/BF00121304

[24]

Shor N. Z., 1990, Annals of Operations Research, V25, P163, DOI 10.1007/BF02283692

[25]

VANDEPANNE C, 1966, MANAGE SCI, V12, P748

[26] NEW PROPERTIES AND COMPUTATIONAL IMPROVEMENT OF THE GOP ALGORITHM FOR PROBLEMS WITH QUADRATIC OBJECTIVE FUNCTIONS AND CONSTRAINTS [J].

VISWESWARAN, V ;

FLOUDAS, CA .

JOURNAL OF GLOBAL OPTIMIZATION, 1993, 3 (04) :439-462

[27]

Visweswaran V., 1990, COMPUT CHEM ENG, V14, P1417

← 1 2 3 →