English

运筹学学报 >

2022 , Vol. 26 >Issue 2: 83 - 100

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.02.008

 

一种求解二次约束二次规划问题的自适应全局优化算法

展开
  • 1. 宁夏大学数学统计学院, 宁夏银川 750021
    2. 北方民族大学宁夏科学计算与智能信息处理协同创新中心, 宁夏银川 750021
高岳林  E-mail: gaoyuelin@263.net

收稿日期: 2020-09-25

  网络出版日期: 2022-05-27

基金资助

国家自然科学基金(11961001);宁夏高等教育一流学科建设基金(NXYLXK2017B09);北方民族大学重大专项(ZDZX201901)

收起

An adaptive global optimization algorithm for solving quadratically constrained quadratic programming problems

Expand
  • 1. School of Mathematics and Statistics, Ningxia University, Yinchuan 750021, Ningxia, China
    2. Ningxia Province Cooperative Innovation Center of Scientific Computing and Intelligent Information Processing, North Minzu University, Yinchuan 750021, Ningxia, China

Received date: 2020-09-25

  Online published: 2022-05-27

Fold

摘要

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。

关键词： 二次约束二次规划; 全局优化; 分支定界; 自适应线性松弛技术; 条件二分法

本文引用格式

黄小利, 高岳林, 张博, 刘霞 . 一种求解二次约束二次规划问题的自适应全局优化算法[J]. 运筹学学报, 2022 , 26(2) : 83 -100 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.008

Abstract

In order to better solve the quadratically constrained quadratic programming problem(QCQP), an adaptive linearized relaxation technique based on the framework of the branch and bound algorithm is proposed in this paper, which theoretically proved that this new delimitation technique is considerable for solving (QCQP). The branch operation in this paper adopts the conditional dichotomy to facilitate effective division of the rectangle; the reduction technique is used to delete some regions that do not contain the global optimal solution to speed up the convergence of the algorithm. Finally, the numerical results show that the proposed algorithm in this paper is effective and feasible.

Key words： quadratically constrained quadratic programming; global optimization; branch and bound; adaptive linearized relaxation technique; conditional dichotomy

参考文献

1 Loiola E M , Abreu N M M D , Boaventura-Netto P O , et al. A survey for the quadratic assignment problem[J]. European Journal of Operational Research, 2007, 176 (2): 657- 690.
2 Luo Z Q , Ma W K , Man-Cho So A , et al. Semidefinite relaxation of quadratic optimization problems[J]. IEEE Signal Processing Magazine, 2010, 27 (3): P.20- 34.
3 Sidiropoulos N D , Davidson T N , Luo Z Q . Transmit beamforming for physical-layer multicasting[J]. IEEE Transactions on Signal Processing, 2006, 54 (6): 2239- 2251.
4 Matskani E , Sidiropoulos N D , Luo Z Q , et al. Convex approximation techniques for joint multiuser downlink beamforming and admission control[J]. IEEE Transactions on Wireless Communications, 2008, 7 (7): 2682- 2693.
5 Gao Y L , Wei F . A new bound-and-reduce approach of nonconvex quadratic programming problems[J]. Applied Mathematics and Computation, 2015, 250, 298- 308.
6 Yin J B , Jiao H W , Shang Y L . Global algorithm for generalized affine multiplicative programming problem[J]. IEEE Access, 2019, 7, 162245- 162253.
7 Pardalos P M , Vavasis S A . Quadratic programming with one negative eigenvalue is NP-hard[J]. Journal of Global Optimization, 1991, 1, 15- 22.
8 Jiao H W , Chen Y Q . A global optimization algorithm for generalized quadratic programming[J]. Journal of Applied Mathematics, 2013, 2013, 1- 9.
9 Jiao H W , Liu S Y , Lu N . A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming[J]. Applied Mathematics and Computation, 2015, 250, 973- 985.
10 Qu S J , Zhang K C , Ji Y . A global optimization algorithm using parametric linearization relaxation[J]. Applied Mathematics and Computation, 2007, 186 (1): 763- 771.
11 Wu H Z , Zhang K C . A new accelerating method for global non-convex quadratic optimization with non-convex quadratic constraints[J]. Applied Mathematics and Computation, 2009, 197 (2): 810- 818.
12 Audet C , Hansen P , Jaumard B , et al. A branch and cut algorithm for nonconvex quadratically constrained quadratic programming[J]. Mathematical Programming, 2000, 87 (1): 131- 152.
13 Yamada S , Takeda A . Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization[J]. Journal of Global Optimization, 2018, 71, 313- 339.
14 Kim S , Kojima M . Second order cone programming relaxation of nonconvex quadratic optimization problems[J]. Optimization Methods and Software, 2001, 15 (3-4): 201- 224.
15 Jiang R J , Li D . Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming[J]. Journal of Global Optimization, 2019, 75 (2): 461- 494.
16 Zhou J . A new spatial branch and bound algorithm for quadratic program with one quadratic constraint and linear constraints[J]. Mathematical Problems in Engineering, 2020, 2020 (23): 1- 8.
17 Zhou J , Xu Z J . A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints[J]. Optimization Letters, 2018, 13, 1615- 1630.
18 Burer S , Vandenbussche D . Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound[J]. Computational Optimization and Applications, 2009, 43 (2): 181- 195.
19 Chen J Q , Burer S . Globally solving nonconvex quadratic programming problems via completely positive programming[J]. Mathematical Programming Computation, 2012, 4 (1): 33- 52.
20 Luo H Z , Bai X D , Peng J M . Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods[J]. Journal of Optimization Theory and Applications, 2019, 180 (3): 964- 992.
21 Mohammad , Keyanpour , Naser , et al. On solving quadratically constrained quadratic programming problem with one non-convex constraint[J]. Opsearch, 2018, 55 (2): 320- 336.
22 Lu C , Deng Z B , Zhou J , et al. A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming[J]. Journal of Global Optimization, 2019, 73 (2): 371- 388.
23 Serafino D , Toraldo G , Marco Viola , et al. A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables[J]. SIAM Journal on Optimization, 2018, 28 (4): 2809- 2838.
24 Liu W , Yang L , Yu B . A lifting-penalty method for quadratic programming with a quadratic matrix inequality constraint[J]. Mathematics, 2020, 8, 1- 11.
25 Phan A H , Yamagishi M , Mandic D , et al. Quadratic programming over ellipsoids with applications to constrained linear regression and tensor decomposition[J]. Neural Computing and Applications, 2020, 32, 7097- 7120.
26 Sun C, Dai R. A decomposition method for nonconvex quadratically constrained quadratic programs[C]// IEEE American Control Conference, 2017: 4631-4636.
27 Ge L , Liu S Y . An accelerating algorithm for globally solving nonconvex quadratic programming[J]. Journal of Inequalities and Applications, 2018, 2018 (1): 178.
Options
文章导航

/

〈 〉