Global optimization of a class of nonconvex quadratically constrained quadratic programming problems

被引：2
作者：
Xia, Yong [1 ,2 ]
机构：
[1] Minist Educ, LMIB, Beijing 100191, Peoples R China
[2] Beihang Univ, Sch Math & Syst Sci, Beijing 100191, Peoples R China
来源：
ACTA MATHEMATICA SINICA-ENGLISH SERIES | 2011年 / 27卷 / 09期
基金：
中国国家自然科学基金;
关键词：
Nonconvex programming; quadratically constrained quadratic programming; quadratic assignment problem; polynomial solvability; strong duality; RELAXATION;
D O I：
10.1007/s10114-011-8351-4
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper we study a class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.
引用
收藏
页码：1803 / 1812
页数：10
相关论文
共 50 条
  • [21] On the sequential quadratically constrained quadratic programming methods
    Solodov, MV
    MATHEMATICS OF OPERATIONS RESEARCH, 2004, 29 (01) : 64 - 79
  • [22] Global optimization of nonconvex factorable programming problems
    Sherali, HD
    Wang, HJ
    MATHEMATICAL PROGRAMMING, 2001, 89 (03) : 459 - 478
  • [23] On convex relaxations for quadratically constrained quadratic programming
    Kurt M. Anstreicher
    Mathematical Programming, 2012, 136 : 233 - 251
  • [24] A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming
    Cheng Lu
    Zhibin Deng
    Jing Zhou
    Xiaoling Guo
    Journal of Global Optimization, 2019, 73 : 371 - 388
  • [25] Global optimization algorithm for mixed integer quadratically constrained quadratic program
    Zhao, Yingfeng
    Liu, Sanyang
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2017, 319 : 159 - 169
  • [26] KKT SOLUTION AND CONIC RELAXATION FOR SOLVING QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING PROBLEMS
    Lu, Cheng
    Fang, Shu-Cherng
    Jin, Qingwei
    Wang, Zhenbo
    Xing, Wenxun
    SIAM JOURNAL ON OPTIMIZATION, 2011, 21 (04) : 1475 - 1490
  • [27] A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming
    Lu, Cheng
    Deng, Zhibin
    Zhou, Jing
    Guo, Xiaoling
    JOURNAL OF GLOBAL OPTIMIZATION, 2019, 73 (02) : 371 - 388
  • [28] A new convex relaxation for quadratically constrained quadratic programming
    Wu, Duzhi
    Hu, Aiping
    Zhou, Jie
    Wu, Songlin
    FILOMAT, 2013, 27 (08) : 1511 - 1521
  • [29] CONVEX HULL PRESENTATION OF A QUADRATICALLY CONSTRAINED SET AND ITS APPLICATION IN SOLVING QUADRATIC PROGRAMMING PROBLEMS
    Xia, Yong
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2009, 26 (06) : 769 - 778
  • [30] First- and Second-Order Optimality Conditions for Quadratically Constrained Quadratic Programming Problems
    Flores-Bazan, Fabian
    Mastroeni, Giandomenico
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2022, 193 (1-3) : 118 - 138
12345