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

doi:10.15960/j.cnki.issn.1007-6093.2022.02.008

Abstract

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

CLC Number:

O221.2

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.

Figures/Tables 4

References 27

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

E	Refs	Mat	$x^*$	f($x^*$)	Iter	Time/s	$\varepsilon$
1	本文	-	(5.0, 1.0)	$-$16.0	25	0.727 978	$10^{-6}$
	[8]	-	(5.0, 1.0)	$-16.0$	18	0.545 454	$10^{-6}$
	[9]	(0, 0;0, 0)	(5.0, 1.0)	$-16.0$	26	0.809 067	$10^{-6}$
2	本文	-	(2.0, 1.666 666 7)	6.777 78	32	0.988 072 5	$10^{-6}$
	[8]	-	(2.0, 1.666 666 7)	6.777 78	2 210	125.946 97	$10^{-6}$
	[9]	(0, 0; 0, 0)	(2.0, 1.666 666 7)	6.777 78	380	11.545 738	$10^{-6}$
3	本文	-	(1.177 124, 2.177 124 3)	1.177 124 343	34	1.117 716 1	$10^{-6}$
	[8]	-	(1.177 124 7, 2.177 123 99)	1.177 124 686	129	2.856 784 4	$10^{-6}$
	[9]	(1, 0;0, 1)	(1.177 125, 2.177 123 2)	1.177 124 686	158	4.922 752 1	$10^{-6}$
4	本文	-	(1.0, 0.181 826 2, 0.983 330 7)	$-10.363 636 37$	258	7.842 670 9	$10^{-6}$
	[8]	-	(1.0, 0.181 980 52, 0.983 302 4)	$-10.363 636 08$	1 413	41.312 05	$10^{-3}$
	[9]	(0 1 1; 1 0 0; 1 0 0)	(1.0, 0.088 388 3, 0.994 369)	$-10.722 732$	94	2.990 738	$10^{-6}$
5	本文	-	(1.5, 1.224 745)	$-1.162 882 7$	20	0.592 805 9	$10^{-6}$
	[8]	-	(1.5, 1.224 744 9)	$-1.162 882 7$	61	1.519 913 8	$10^{-6}$
	[9]	(1 0;0 1)	(1.5, 1.224 745)	$-1.162 882 7$	46	1.401 966 1	$10^{-6}$

E	Refs	$x^*$	f($x^*$)	Iter	Time/s	$\varepsilon$
6	本文	(2.0, 8.0)	10.0	3	0.183 1	$10^{-6}$
	[6]	(2.0, 8.0)	10.0	0	0.049 7	$10^{-6}$
	[27]	(2.0, 8.0)	10.0	3	0.357 3	-
7	本文	(0, 3.640 288, 0, 2.902 878, 1.938 849, 0)	$-16.226 619$	2	0.226 0	$10^{-6}$
	[27]	(0.0, 3.640 3, 0.0, 2.902 9, 1.938 8, 0.0)	$-16.226 620$	5	0.590 1	-
8	本文	(1.314 8, 0.139 6, 0, 0.423 3)	0.883 47	50	1.643 6	$10^{-6}$
	[6]	(1.314 8, 0.139 6, 0, 0.423 3)	0.890 19	0	0.056 2	$10^{-6}$
	[27]	(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	$10^{-6}$
	[6]	(0, 0)	4	9	0.367 51	$10^{-6}$

$(m, n)$	算例10的数值结果		$(m, n)$	算例11的数值结果
$(m, n)$	Avg(Std).IT	Avg(Std).time/s	$(m, n)$	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)

$D$	Refs	$f(x^{\ast})$	Mat	Iter	time/s	$D$	Refs	$f(x^{\ast})$	Mat	Iter	time/s
5	本文	$-25$	-	1	0.152 2	20	[8]	$-400$	-	1 930	74.654 5
5	[8]	$-25$	-	115	3.825 6	20	[9]	$-400$	$(0)_{20\times20}$	2961	140.260 0
5	[9]	$-25$	$(0)_{5\times5}$	186	6.330 0	20	[27]	$-400$	-	15	2.735 6
5	[27]	$-25$	-	1	0.012 5	30	本文	$-900$	-	1	0.879 1
10	本文	$-100$	-	1	0.288 0	30	[9]	$-900$	$(0)_{30\times30}$	6541	245.939 4
10	[8]	$-100$	-	470	16.406 0	30	[27]	$-900$	-	18	11.256 4
10	[9]	$-100$	$(0)_{10\times10}$	726	27.800 0	50	本文	$-1 500$	-	1	1.472 7
10	[27]	$-100$	-	7	0.256 5	50	[9]	$-1 500$	$(0)_{50\times50}$	19 176	931.588 0
20	本文	$-400$	-	1	0.593 4	50	[27]	$-1 500$	-	21	17.352 2

[1]	Fusheng BAI, Dan FENG, Ke ZHANG. Combined response surface method with adaptive sampling for expensive black-box global optimization [J]. Operations Research Transactions, 2021, 25(2): 1-14.
[2]	Jiali CHEN, Ying ZHANG, Shenggang WANG, Xiaoying XIE. A new filled function and its application in data fitting problems [J]. Operations Research Transactions, 2021, 25(1): 81-88.
[3]	Deqiang QU, Youlin SHANG, Yue ZHAN, Dan WU. A new parameterless filled function for global optimization problems [J]. Operations Research Transactions, 2021, 25(1): 89-95.
[4]	ZHAO Dan, GAO Yuelin. Non-parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2020, 24(4): 63-73.
[5]	CHEN Yong, WANG Wei, XU Yifan. An stochastic algorithm for global optimization with linear constraints based on intermittent diffusion [J]. Operations Research Transactions, 2020, 24(1): 88-100.
[6]	WANG Weixiang, SHANG Youlin, WANG Duo. Filled function method for solving non-smooth box constrained global optimization problems [J]. Operations Research Transactions, 2019, 23(1): 28-34.
[7]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[8]	TIAN Mingyu, YANG Yongjian. A global optimization algorithm for polynomial programming [J]. Operations Research Transactions, 2018, 22(4): 79-88.
[9]	ZHENG Yue, ZHUANG Daoyuan, WAN Zhongping. A global optimization method for solving the weak linear bilevel programming problems [J]. Operations Research Transactions, 2017, 21(3): 86-94.
[10]	WU Peipei, GAO Yuelin. A new single parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2017, 21(3): 111-118.
[11]	SHI Litang, CHEN Wei. A filled-filter function algorithm for solving unconstrained nonlinear optimization [J]. Operations Research Transactions, 2017, 21(1): 55-64.
[12]	HU Quan, WANG Wei. A filled function method based on filter for global optimization with box constraints [J]. Operations Research Transactions, 2016, 20(3): 57-67.
[13]	YE Min, WU Zhiyou, ZHANG Liang. Necessary global optimality conditions and optimization methods for cubic polynomial optimization problems with linear constraints [J]. Operations Research Transactions, 2015, 19(2): 15-28.
[14]	LV Yibing, WAN Zhongping. A global optimization method for solving the linear semivectorial bilevel programming problem [J]. Operations Research Transactions, 2015, 19(2): 29-36.
[15]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 27

Related Articles 15

Recommended Articles

Metrics

Comments