运筹学学报 ›› 2022, Vol. 26 ›› Issue (2): 83-100.doi: 10.15960/j.cnki.issn.1007-6093.2022.02.008
收稿日期:
2020-09-25
出版日期:
2022-06-15
发布日期:
2022-05-27
通讯作者:
高岳林
E-mail:gaoyuelin@263.net
作者简介:
高岳林 E-mail: gaoyuelin@263.net基金资助:
Xiaoli HUANG1, Yuelin GAO1,2,*(), Bo ZHANG1, Xia LIU1
Received:
2020-09-25
Online:
2022-06-15
Published:
2022-05-27
Contact:
Yuelin GAO
E-mail:gaoyuelin@263.net
摘要:
为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。
中图分类号:
黄小利, 高岳林, 张博, 刘霞. 一种求解二次约束二次规划问题的自适应全局优化算法[J]. 运筹学学报, 2022, 26(2): 83-100.
Xiaoli HUANG, Yuelin GAO, Bo ZHANG, Xia LIU. An adaptive global optimization algorithm for solving quadratically constrained quadratic programming problems[J]. Operations Research Transactions, 2022, 26(2): 83-100.
表1
算例$ 1\sim 5 $利用本文算法产生的数值结果"
E | Refs | Mat | f( | Iter | Time/s | ||
1 | 本文 | - | (5.0, 1.0) | 25 | 0.727 978 | ||
[ | - | (5.0, 1.0) | 18 | 0.545 454 | |||
[ | (0, 0;0, 0) | (5.0, 1.0) | 26 | 0.809 067 | |||
2 | 本文 | - | (2.0, 1.666 666 7) | 6.777 78 | 32 | 0.988 072 5 | |
[ | - | (2.0, 1.666 666 7) | 6.777 78 | 2 210 | 125.946 97 | ||
[ | (0, 0; 0, 0) | (2.0, 1.666 666 7) | 6.777 78 | 380 | 11.545 738 | ||
3 | 本文 | - | (1.177 124, 2.177 124 3) | 1.177 124 343 | 34 | 1.117 716 1 | |
[ | - | (1.177 124 7, 2.177 123 99) | 1.177 124 686 | 129 | 2.856 784 4 | ||
[ | (1, 0;0, 1) | (1.177 125, 2.177 123 2) | 1.177 124 686 | 158 | 4.922 752 1 | ||
4 | 本文 | - | (1.0, 0.181 826 2, 0.983 330 7) | 258 | 7.842 670 9 | ||
[ | - | (1.0, 0.181 980 52, 0.983 302 4) | 1 413 | 41.312 05 | |||
[ | (0 1 1; 1 0 0; 1 0 0) | (1.0, 0.088 388 3, 0.994 369) | 94 | 2.990 738 | |||
5 | 本文 | - | (1.5, 1.224 745) | 20 | 0.592 805 9 | ||
[ | - | (1.5, 1.224 744 9) | 61 | 1.519 913 8 | |||
[ | (1 0;0 1) | (1.5, 1.224 745) | 46 | 1.401 966 1 |
表2
算例$ 6\sim 9 $利用本文算法产生的数值结果"
E | Refs | f( | Iter | Time/s | ||
6 | 本文 | (2.0, 8.0) | 10.0 | 3 | 0.183 1 | |
[ | (2.0, 8.0) | 10.0 | 0 | 0.049 7 | ||
[ | (2.0, 8.0) | 10.0 | 3 | 0.357 3 | - | |
7 | 本文 | (0, 3.640 288, 0, 2.902 878, 1.938 849, 0) | 2 | 0.226 0 | ||
[ | (0.0, 3.640 3, 0.0, 2.902 9, 1.938 8, 0.0) | 5 | 0.590 1 | - | ||
8 | 本文 | (1.314 8, 0.139 6, 0, 0.423 3) | 0.883 47 | 50 | 1.643 6 | |
[ | (1.314 8, 0.139 6, 0, 0.423 3) | 0.890 19 | 0 | 0.056 2 | ||
[ | (1.314 8, 0.139 6, 0, 0.423 3) | 0.890 19 | 1 | 0.389 8 | - | |
9 | 本文 | (0, 0) | 4 | 12 | 0.416 3849 | |
[ | (0, 0) | 4 | 9 | 0.367 51 |
表3
算例$ 10\sim 11 $利用本文算法产生的数值结果"
算例10的数值结果 | 算例11的数值结果 | |||||
Avg(Std).IT | Avg(Std).time/s | Avg(Std).IT | Avg(Std).time/s | |||
(5, 5) | 284.6(198.762 3) | 9.471 5(7.169 3) | (5, 5) | 1 064.0(237.601 8) | 22.522 9(5.009 8) | |
(10, 5) | 765.8(622.232 4) | 32.322 0(30.798 3) | (10, 5) | 1 235.3(241.408 5) | 26.408 1(5.278 2) | |
(20, 5) | 989.9(199.740 1) | 21.691 2(4.465 3) | (20, 5) | 989.9(199.740 1) | 21.691 2(4.465 3) | |
(50, 5) | 1 061.4(234.656 9) | 23.208 2(5.066 9) | (50, 5) | 1 061.4(234.656 9) | 23.208 22(5.066 9 | |
(60, 5) | 1 428(305.325 1) | 59.744 3(27.094 2) | (60, 5) | 1 095.2(187.475 2) | 38.916 2(8.906 2) | |
(80, 5) | 1 520.2(341.199 0) | 66.039 8(27.379 4) | (80, 5) | 1 166.1(306.505 9) | 46.422 9(16.309 9) | |
(100, 5) | 1 558.4(438.526 2) | 73.936 0(45.120 6) | (100, 5) | 1 085.3(238.680 1) | 42.108 3(11.659 9) | |
(200, 5) | 1 640.2(671.467 0) | 93.496 2(78.437 1) | (200, 5) | 1 166.7(207.521 1) | 50.262 0(11.815 5) | |
(500, 5) | 1 461.4(397.248 1) | 66.843 1(29.843 9) | (5, 6) | 3 453.4(645.337 6) | 73.997 2(13.901 6) | |
(5, 6) | 396.4(183.463 5) | 14.654 3(7.869 0) | (5, 7) | 11 773.0(2 655.400 0) | 254.925 2(58.111 7) | |
(5, 7) | 965.6(846.052 7) | 89.329 6(119.911 8) | (5, 8) | 43 000.0(9 781.100 0) | 1 866.000 0(272.610 0) | |
(5, 8) | 2 215.6(1 637.400 0) | 338.853 3(414.881 6) | (5, 9) | 147 930.0(21963) | 4 668.800 0(2 184.700 0) | |
(10, 6) | 1246(1 242.100 0) | 122.209 9(193.317 3) | (10, 6) | 3 626.4(716.857 9) | 304.797 5(112.053 4) | |
(10, 7) | 1 859.6(2 076.132 0) | 221.291 5(369.404 4) | (10, 7) | 12 807.0(1 828.800 0) | 3 438.800 0(820.571 2) |
表4
算例12利用本文算法产生的数值结果"
Refs | Mat | Iter | time/s | Refs | Mat | Iter | time/s | |||||
5 | 本文 | - | 1 | 0.152 2 | 20 | [ | - | 1 930 | 74.654 5 | |||
5 | [ | - | 115 | 3.825 6 | 20 | [ | 2961 | 140.260 0 | ||||
5 | [ | 186 | 6.330 0 | 20 | [ | - | 15 | 2.735 6 | ||||
5 | [ | - | 1 | 0.012 5 | 30 | 本文 | - | 1 | 0.879 1 | |||
10 | 本文 | - | 1 | 0.288 0 | 30 | [ | 6541 | 245.939 4 | ||||
10 | [ | - | 470 | 16.406 0 | 30 | [ | - | 18 | 11.256 4 | |||
10 | [ | 726 | 27.800 0 | 50 | 本文 | - | 1 | 1.472 7 | ||||
10 | [ | - | 7 | 0.256 5 | 50 | [ | 19 176 | 931.588 0 | ||||
20 | 本文 | - | 1 | 0.593 4 | 50 | [ | - | 21 | 17.352 2 |
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.
doi: 10.1016/j.ejor.2005.09.032 |
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.
doi: 10.1109/MSP.2010.936019 |
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.
doi: 10.1109/TSP.2006.872578 |
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.
doi: 10.1109/TWC.2008.070104 |
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.
doi: 10.1016/j.amc.2014.10.077 |
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.
doi: 10.1109/ACCESS.2019.2951515 |
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.
doi: 10.1007/BF00120662 |
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.
doi: 10.1016/j.amc.2014.11.032 |
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.
doi: 10.1016/j.amc.2006.08.028 |
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.
doi: 10.1007/s101079900106 |
13 |
Yamada S , Takeda A . Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization[J]. Journal of Global Optimization, 2018, 71, 313- 339.
doi: 10.1007/s10898-018-0617-2 |
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.
doi: 10.1080/10556780108805819 |
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.
doi: 10.1007/s10898-019-00793-y |
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.
doi: 10.1007/s10589-007-9137-6 |
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.
doi: 10.1007/s12532-011-0033-9 |
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.
doi: 10.1007/s10957-018-1416-0 |
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.
doi: 10.1007/s12597-018-0334-0 |
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.
doi: 10.1007/s10898-018-0726-y |
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.
doi: 10.1137/17M1128538 |
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.
doi: 10.1007/s00521-019-04191-z |
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.
doi: 10.1186/s13660-018-1764-1 |
[1] | 白富生, 冯丹, 张柯. 求解昂贵黑箱全局优化问题的自适应采样组合响应面方法[J]. 运筹学学报, 2021, 25(2): 1-14. |
[2] | 陈佳利, 张莹, 王胜刚, 谢笑盈. 一个新的填充函数及其在数据拟合问题中的应用[J]. 运筹学学报, 2021, 25(1): 81-88. |
[3] | 赵丹, 高岳林. 非线性整数规划问题的无参数填充函数算法[J]. 运筹学学报, 2020, 24(4): 63-73. |
[4] | 任烨权, 白延琴, 李倩, 余长君, 张连生. 一个求解池化问题的二阶锥逼近算法[J]. 运筹学学报, 2020, 24(2): 61-72. |
[5] | 陈永, 王薇, 徐以汎. 具有间断扩散性质的线性约束全局优化随机算法[J]. 运筹学学报, 2020, 24(1): 88-100. |
[6] | 王伟祥, 尚有林, 王朵. 求解带箱子集约束的非光滑全局优化问题的填充函数方法[J]. 运筹学学报, 2019, 23(1): 28-34. |
[7] | 蔡爽, 杨珂, 刘克. 具有机器适用限制的分布式置换流水车间问题的模型与算法[J]. 运筹学学报, 2018, 22(4): 17-30. |
[8] | 郑跃, 庄道元, 万仲平. 求解弱线性双层规划问题的一种全局优化方法[J]. 运筹学学报, 2017, 21(3): 86-94. |
[9] | 石礼堂, 陈伟. 非线性无约束优化问题的滤子填充函数算法[J]. 运筹学学报, 2017, 21(1): 55-64. |
[10] | 胡铨, 王薇. 求解带箱式约束全局优化问题的滤子填充函数方法[J]. 运筹学学报, 2016, 20(3): 57-67. |
[11] | 戴彧虹,刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报, 2014, 18(1): 69-92. |
[12] | 汤丹. 基于模拟退火的CRS算法[J]. 运筹学学报, 2011, 15(4): 124-128. |
[13] | 张丽丽, 李建宇, 李兴斯. 全局优化问题的一类积分型最优性条件 (英)[J]. 运筹学学报, 2011, 15(1): 1-10. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||