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
MANGASARIAN, OL
[J]. 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
MURTY, KG
KABADI, SN
[J]. 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
PARDALOS, PM
VAVASIS, SA
[J]. MATHEMATICAL PROGRAMMING, 1992, 57 (02) : 337 - 339
[9] CHECKING LOCAL OPTIMALITY IN CONSTRAINED QUADRATIC-PROGRAMMING IS NP-HARD
PARDALOS, PM
SCHNITGER, G
[J]. OPERATIONS RESEARCH LETTERS, 1988, 7 (01) : 33 - 35
[10] PARDALOS PM, 1987, LECTURE NOTES COMPUT, V268

← 1 2 →