NECESSARY AND SUFFICIENT CONDITION FOR LOCAL MINIMA OF A CLASS OF NONCONVEX QUADRATIC PROGRAMS

被引：4

作者：

CAO, JM ^{[1
]}

机构：

[1] SW JIAOTONG UNIV,DEPT TRANSPORTAT ENGN,CHENGDU 610031,PEOPLES R CHINA

来源：

MATHEMATICAL PROGRAMMING | 1995年 / 69卷 / 03期

关键词：

NONCONVEX QUADRATIC PROGRAMMING; LOCAL MINIMUM; NP-COMPLETE; NECESSARY AND SUFFICIENT CONDITION;

D O I：

10.1007/BF01585567

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The author (1992, 1993) earlier studied the equivalence of a class of 0-1 quadratic programs and their relaxed problems. Thus, a class of combinatorial optimization problems can be solved by solving a class of nonconvex quadratic programs. In this paper, a necessary and sufficient condition for local minima of this class of nonconvex quadratic programs is given; this will be the foundation for study of algorithms.

引用

页码：403 / 411

页数：9

共 12 条

[1]

CAO JM, 1993, J SW JIAOTONG U, V1, P72

[2]

CAO JM, 1992, OR DECISION MAKING, P142

[3]

CONTESSE L, 1980, NUMER MATH, V34, P315, DOI 10.1007/BF01396705

[4] LOCALLY UNIQUE SOLUTIONS OF QUADRATIC PROGRAMS, LINEAR AND NON-LINEAR COMPLEMENTARITY-PROBLEMS [J].

MANGASARIAN, OL .

MATHEMATICAL PROGRAMMING, 1980, 19 (02) :200-212

[5]

MORE JJ, 1991, MATH PROGRAM, V49, P397

[6] SOME NP-COMPLETE PROBLEMS IN QUADRATIC AND NONLINEAR-PROGRAMMING [J].

MURTY, KG ;

KABADI, SN .

MATHEMATICAL PROGRAMMING, 1987, 39 (02) :117-129

[7]

Pardalos P., 1991, J GLOBAL OPTIM, V1, P15, DOI DOI 10.1007/BF00120662

[8] OPEN QUESTIONS IN COMPLEXITY THEORY FOR NUMERICAL OPTIMIZATION [J].

PARDALOS, PM ;

VAVASIS, SA .

MATHEMATICAL PROGRAMMING, 1992, 57 (02) :337-339

[9] CHECKING LOCAL OPTIMALITY IN CONSTRAINED QUADRATIC-PROGRAMMING IS NP-HARD [J].

PARDALOS, PM ;

SCHNITGER, G .

OPERATIONS RESEARCH LETTERS, 1988, 7 (01) :33-35

[10]

PARDALOS PM, 1987, LECTURE NOTES COMPUT, V268

← 1 2 →