×
Hou, Zhisong; Jiao, Hongwei; Cai, Lei; Bai, Chunyang

Branch-delete-bound algorithm for globally solving quadratically constrained quadratic programs. (English) Zbl 1372.90077

Open Math. 15, 1212-1224 (2017).
Summary: This paper presents a branch-delete-bound algorithm for effectively solving the global minimum of quadratically constrained quadratic programs problem, which may be nonconvex. By utilizing the characteristics of quadratic function, we construct a new linearizing method, so that the quadratically constrained quadratic programs problem can be converted into a linear relaxed programs problem. Moreover, the established linear relaxed programs problem is embedded within a branch-and-bound framework without introducing any new variables and constrained functions, which can be easily solved by any effective linear programs algorithms. By subsequently solving a series of linear relaxed programs problems, the proposed algorithm can converge the global minimum of the initial quadratically constrained quadratic programs problem. Compared with the known methods, numerical results demonstrate that the proposed method has higher computational efficiency.

Cited in 2 Documents

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
65K05 Numerical mathematical programming methods

Keywords:

quadratically constrained quadratic programs; global optimization; linearizing method; deleting technique; branch-delete-bound algorithm
Cite Review PDF
Full Text: DOI
OA License

References:

[1] Jiao H., Liu S., An efficient algorithm for quadratic sum-of-ratios fractional programs problem, Numer. Func. Anal. Opt., (in press),; Jiao, H.; Liu, S., An efficient algorithm for quadratic sum-of-ratios fractional programs problem, Numer. Func. Anal. Opt. · Zbl 1387.90243 · doi:10.1080/01630563.2017.1327869
[2] Gao Y., Wei F., A new bound-and-reduce approach of nonconvex quadratic programming problems, Appl. Math. Comput., 2015, 250, 298-308; Gao, Y.; Wei, F., A new bound-and-reduce approach of nonconvex quadratic programming problems, Appl. Math. Comput., 250, 298-308 (2015) · Zbl 1328.90096
[3] Azab A., Quadratic assignment problem mathematical modelling for process planning, Int. J. Comput. Integ. M., 2016, 29, 561- 580; Azab, A., Quadratic assignment problem mathematical modelling for process planning, Int. J. Comput. Integ. M., 29, 561-580 (2016)
[4] Kong X., Huang G., Fan Y., Li Y., A duality theorem-based algorithm for inexact quadratic programming problems: Application to waste management under uncertainty, Eng. Optimiz., 2016, 48, 562-581; Kong, X.; Huang, G.; Fan, Y.; Li, Y., A duality theorem-based algorithm for inexact quadratic programming problems: Application to waste management under uncertainty, Eng. Optimiz., 48, 562-581 (2016)
[5] Jiao H., Chen Y., Yin J., Optimality condition and iterative thresholding algorithm for \(l_p\)-regularization problems, SpringerPlus, 2016,; Jiao, H.; Chen, Y.; Yin, J., Optimality condition and iterative thresholding algorithm for \(l_p\)-regularization problems, SpringerPlus (2016) · doi:10.1186/s40064-016-3516-3
[6] Jiao H., Wang Z., Chen Y., Global optimization algorithm for sum of generalized polynomial ratios problem, Appl. Math. Model., 2013, 37(1), 187-197; Jiao, H.; Wang, Z.; Chen, Y., Global optimization algorithm for sum of generalized polynomial ratios problem, Appl. Math. Model., 37, 1, 187-197 (2013) · Zbl 1349.90693
[7] Wang Z.-J., Li K.W., Group decision making with incomplete intuitionistic preference relations based on quadratic programming models, Comput. Ind. Eng., 2016, 93, 162-170; Wang, Z.-J.; Li, K. W., Group decision making with incomplete intuitionistic preference relations based on quadratic programming models, Comput. Ind. Eng., 93, 162-170 (2016)
[8] Bose S., Gayme D.F., Chandy K.M., Low S.H., Quadratically constrained quadratic programs on acyclic graphs with application to power flow, IEEE Trans. Control Net. Syst., 2015, 2, 278-287; Bose, S.; Gayme, D. F.; Chandy, K. M.; Low, S. H., Quadratically constrained quadratic programs on acyclic graphs with application to power flow, IEEE Trans. Control Net. Syst., 2, 278-287 (2015) · Zbl 1370.90168
[9] Jiao H., Liu S., Yin J., Zhao Y., Outcome space range reduction method for global optimization of sum of affine ratios problem, Open Math., 2016, 14, 736-746; Jiao, H.; Liu, S.; Yin, J.; Zhao, Y., Outcome space range reduction method for global optimization of sum of affine ratios problem, Open Math., 14, 736-746 (2016) · Zbl 1349.90692
[10] Sherali H.D., Tuncbilek C.H., A reformulation-convexification approach for solving nonconvex quadratic programming problems, J. Glob. Optim., 1995, 7, 1-31; Sherali, H. D.; Tuncbilek, C. H., A reformulation-convexification approach for solving nonconvex quadratic programming problems, J. Glob. Optim., 7, 1-31 (1995) · Zbl 0844.90064
[11] Voorhis T.V., A global optimization algorithm using lagrangian underestimates and the interval newton method, J. Glob. Optim., 2002, 24, 349-370; Voorhis, T. V., A global optimization algorithm using lagrangian underestimates and the interval newton method, J. Glob. Optim., 24, 349-370 (2002) · Zbl 1046.90067
[12] Linderoth J., A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program., 2005, 103, 251-282; Linderoth, J., A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program., 103, 251-282 (2005) · Zbl 1099.90039
[13] Burer S., Vandenbussche D., A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Math. Program., 2008, 113, 259-282; Burer, S.; Vandenbussche, D., A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Math. Program., 113, 259-282 (2008) · Zbl 1135.90034
[14] Zheng X.J., Sun X.L., Li D., Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, Math. Program., 2011, 129, 301-329; Zheng, X. J.; Sun, X. L.; Li, D., Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, Math. Program., 129, 301-329 (2011) · Zbl 1236.90089
[15] Thoai N.V., Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints, J. Optim. Theory Appl., 2000, 107, 331-354; Thoai, N. V., Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints, J. Optim. Theory Appl., 107, 331-354 (2000) · Zbl 0997.90058
[16] Shen P., Duan Y., Ma Y., A robust solution approach for nonconvex quadratic programs with additional multiplicative constraints, Appl. Math. Comput., 2008, 201, 514-526; Shen, P.; Duan, Y.; Ma, Y., A robust solution approach for nonconvex quadratic programs with additional multiplicative constraints, Appl. Math. Comput., 201, 514-526 (2008) · Zbl 1156.65063
[17] Gao Y., Shang Y., Zhang L., A branch and reduce approach for solving nonconvex quadratic programming problems with quadratic constraints, OR transactions, 2005, 9, 9-20; Gao, Y.; Shang, Y.; Zhang, L., A branch and reduce approach for solving nonconvex quadratic programming problems with quadratic constraints, OR transactions, 9, 9-20 (2005)
[18] Gao Y., Xue H., Shen P., A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems, Appl. Math. Comput., 2005, 168, 1409-1418; Gao, Y.; Xue, H.; Shen, P., A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems, Appl. Math. Comput., 168, 1409-1418 (2005) · Zbl 1087.65061
[19] Shen P., Liu L., A global optimization approach for quadratic programs with nonconvex quadratic constraints, Chin. J. Eng. Math., 2008, 25, 923-926; Shen, P.; Liu, L., A global optimization approach for quadratic programs with nonconvex quadratic constraints, Chin. J. Eng. Math., 25, 923-926 (2008) · Zbl 1174.90728
[20] Qu S.-J., Zhang K.-C., Ji Y., A global optimization algorithm using parametric linearization relaxation, Appl. Math. Comput., 2007, 186, 763-771; Qu, S.-J.; Zhang, K.-C.; Ji, Y., A global optimization algorithm using parametric linearization relaxation, Appl. Math. Comput., 186, 763-771 (2007) · Zbl 1116.65070
[21] Shen P., Jiao H., A new rectangle branch-and-pruning appproach for generalized geometric programming, Appl. Math. Comput., 2006, 183, 1027-1038; Shen, P.; Jiao, H., A new rectangle branch-and-pruning appproach for generalized geometric programming, Appl. Math. Comput., 183, 1027-1038 (2006) · Zbl 1112.65058
[22] Wang Y., Liang Z., A deterministic global optimization algorithm for generalized geometric programming, Appl. Math. Comput., 2005, 168, 722-737; Wang, Y.; Liang, Z., A deterministic global optimization algorithm for generalized geometric programming, Appl. Math. Comput., 168, 722-737 (2005) · Zbl 1105.65335
[23] Jiao H., Chen Y., A global optimization algorithm for generalized quadratic programming, J. Appl. Math., 2013,; Jiao, H.; Chen, Y., A global optimization algorithm for generalized quadratic programming, J. Appl. Math., 2013 · Zbl 1397.90291 · doi:10.1155/2013/215312
[24] Wang Y.J., Zhang K.C., Gao Y.L., Global optimization of generalized geometric programming, Comput. Math. Appl., 2004, 48, 1505-1516; Wang, Y. J.; Zhang, K. C.; Gao, Y. L., Global optimization of generalized geometric programming, Comput. Math. Appl., 48, 1505-1516 (2004) · Zbl 1066.90096
[25] Shen P., Linearization method of global optimization for generalized geometric programming, Appl. Math. Comput., 2005, 162, 353-370; Shen, P., Linearization method of global optimization for generalized geometric programming, Appl. Math. Comput., 162, 353-370 (2005) · Zbl 1071.65089
[26] Shen P., Li X., Branch-reduction-bound algorithm for generalized geometric programming, J. Glob. Optim., 2013, 56, 1123-1142; Shen, P.; Li, X., Branch-reduction-bound algorithm for generalized geometric programming, J. Glob. Optim., 56, 1123-1142 (2013) · Zbl 1300.90032
[27] Jiao H., Liu S., Lu N., A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming, Appl. Math. Comput., 2015, 250, 973-985; Jiao, H.; Liu, S.; Lu, N., A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming, Appl. Math. Comput., 250, 973-985 (2015) · Zbl 1328.65137
[28] Jiao H., Liu S., Zhao Y., Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints, Appl. Math. Model., 2015, 39, 7568-7582; Jiao, H.; Liu, S.; Zhao, Y., Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints, Appl. Math. Model., 39, 7568-7582 (2015) · Zbl 1443.90037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.