×

A novel optimization method for nonconvex quadratically constrained quadratic programs. (English) Zbl 1474.90318

Summary: This paper presents a novel optimization method for effectively solving nonconvex quadratically constrained quadratic programs (NQCQP) problem. By applying a novel parametric linearizing approach, the initial NQCQP problem and its subproblems can be transformed into a sequence of parametric linear programs relaxation problems. To enhance the computational efficiency of the presented algorithm, a cutting down approach is combined in the branch and bound algorithm. By computing a series of parametric linear programs problems, the presented algorithm converges to the global optimum point of the NQCQP problem. At last, numerical experiments demonstrate the performance and computational superiority of the presented algorithm.

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Visweswaran, V.; Floudas, C. A., A global optimization algorithm (GOP) for certain classes of nonconvex NLPs II: applications of theory and test problems, Computers and Chemical Engineering, 14, 1417-1434 (1990)
[2] Rutenberg, D. P.; Shaftel, T. L., Product design: sub-assemblies for multiple markets, Managment Science, 18, 4, B220-B231 (1971)
[3] Demands, E. V.; Tang, C. S., Linear control of a Markov production system, Operations Research, 40, 259-278 (1992) · Zbl 0825.90517
[4] Phan-huy-Hao, E., Quadratically constrained quadratic programming: some applications and a method for solution, Zeitschrift für Operations Research A, 26, 3, 105-119 (1982) · Zbl 0479.90065
[5] Weintraub, A.; Vera, J., A cutting plane approach for chance constrained linear programs, Operations Research, 39, 5, 776-785 (1991) · Zbl 0744.90065 · doi:10.1287/opre.39.5.776
[6] Phong, T. Q.; Tao, P. D.; An, L. T. H., A method for solving d.c. programming problems: application to fuel mixture nonconvex optimization problem, Journal of Global Optimization, 6, 1, 87-105 (1995) · Zbl 0835.90096 · doi:10.1007/BF01106607
[7] Al-Khayyal, F. A.; Larsen, C.; van Voorhis, T., A relaxation method for nonconvex quadratically constrained quadratic programs, Journal of Global Optimization, 6, 3, 215-230 (1995) · Zbl 0835.90060 · doi:10.1007/BF01099462
[8] Al-Khayyal, F.; van Voorhis, T.; Floudas, C. A., Accelerating convergence of branch and bound algorithms for quadratically constrained optimization problems, State of the Art in Global Optimization: Computational Methods and Applications, 7 (1996), London, UK: Kluwer Academic, London, UK · Zbl 0871.90060
[9] Filar, J. A.; Schultz, T. A., Bilinear programming and structured stochastic games, Journal of Optimization Theory and Applications, 53, 1, 85-104 (1987) · Zbl 0593.90091 · doi:10.1007/BF00938818
[10] Sherali, H. D.; Tuncbilek, C. H., A reformulation-convexification approach for solving nonconvex quadratic programming problems, Journal of Global Optimization, 7, 1, 1-31 (1995) · Zbl 0844.90064 · doi:10.1007/BF01100203
[11] Van Voorhis, T., A global optimization algorithm using Lagrangian underestimates and the interval Newton method, Journal of Global Optimization, 24, 3, 349-370 (2002) · Zbl 1046.90067 · doi:10.1023/A:1020383700229
[12] Linderoth, J., A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Mathematical Programming B, 103, 2, 251-282 (2005) · Zbl 1099.90039 · doi:10.1007/s10107-005-0582-7
[13] Burer, S.; Vandenbussche, D., A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Mathematical Programming A, 113, 2, 259-282 (2008) · Zbl 1135.90034 · doi:10.1007/s10107-006-0080-6
[14] Zheng, X. J.; Sun, X. L.; Li, D., Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, Mathematical Programming B, 129, 2, 301-329 (2011) · Zbl 1236.90089 · doi:10.1007/s10107-011-0466-y
[15] Thoai, N. V., Duality bound method for the general quadratic programming problem with quadratic constraints, Journal of Optimization Theory and Applications, 107, 2, 331-354 (2000) · Zbl 0997.90058 · doi:10.1023/A:1026437621223
[16] Gao, Y.; Xue, H.; Shen, P., A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems, Applied Mathematics and Computation, 168, 2, 1409-1418 (2005) · Zbl 1087.65061 · doi:10.1016/j.amc.2004.10.024
[17] Gao, Y.; Shang, Y.; Zhang, L., A branch and reduce approach for solving nonconvex quadratic programming problems with quadratic constraints, OR Transactions, 9, 2, 9-20 (2005)
[18] Shen, P.; Duan, Y.; Ma, Y., A robust solution approach for nonconvex quadratic programs with additional multiplicative constraints, Applied Mathematics and Computation, 201, 1-2, 514-526 (2008) · Zbl 1156.65063 · doi:10.1016/j.amc.2007.12.039
[19] Shen, P. P.; Liu, L. M., A global optimization approach to quadratic programming problems with nonconvex quadratic constraints, Chinese Journal of Engineering Mathematics, 25, 5, 923-926 (2008) · Zbl 1174.90728
[20] Qu, S.-J.; Zhang, K.-C.; Ji, Y., A global optimization algorithm using parametric linearization relaxation, Applied Mathematics and Computation, 186, 1, 763-771 (2007) · Zbl 1116.65070 · doi:10.1016/j.amc.2006.08.028
[21] Jiao, H.; Chen, Y., A global optimization algorithm for generalized quadratic programming, Journal of Applied Mathematics, 2013 (2013) · Zbl 1397.90291 · doi:10.1155/2013/215312
[22] Wang, Y.; Liang, Z., A deterministic global optimization algorithm for generalized geometric programming, Applied Mathematics and Computation, 168, 1, 722-737 (2005) · Zbl 1105.65335 · doi:10.1016/j.amc.2005.01.142
[23] Shen, P.; Jiao, H., A new rectangle branch-and-pruning approach for generalized geometric programming, Applied Mathematics and Computation, 183, 2, 1027-1038 (2006) · Zbl 1112.65058 · doi:10.1016/j.amc.2006.05.137
[24] Shen, P., Linearization method of global optimization for generalized geometric programming, Applied Mathematics and Computation, 162, 1, 353-370 (2005) · Zbl 1071.65089 · doi:10.1016/j.amc.2003.12.101
[25] Shen, P.; Li, X., Branch-reduction-bound algorithm for generalized geometric programming, Journal of Global Optimization, 56, 3, 1123-1142 (2013) · Zbl 1300.90032 · doi:10.1007/s10898-012-9933-0
[26] Hou, X. P.; Shen, P. P.; Chen, Y. Q., A global optimization algorithm for signomial geometric programming problem · Zbl 1470.90092
[27] Tsai, J.-F.; Lin, M.-H.; Hu, Y.-C., On generalized geometric programming problems with non-positive variables, European Journal of Operational Research, 178, 1, 10-19 (2007) · Zbl 1109.90050 · doi:10.1016/j.ejor.2005.11.037
[28] Nazemi, A.; Sharifi, E., Solving a class of geometric programming problems by an efficient dynamic model, Communications in Nonlinear Science and Numerical Simulation, 18, 3, 692-709 (2013) · Zbl 1311.90143 · doi:10.1016/j.cnsns.2012.07.016
[29] Shen, P.-P.; Bai, X.-D., Global optimization for generalized geometric programming problems with discrete variables, Optimization, 62, 7, 895-917 (2013) · Zbl 1278.90321 · doi:10.1080/02331934.2011.604871
[30] Lange, K.; Zhou, H., MM algorithms for geometric and signomial programming, Mathematical Programming, 143, 1-2, 339-356 (2014) · Zbl 1286.90110 · doi:10.1007/s10107-012-0612-1
[31] Floudas, C. A.; Gounaris, C. E., A review of recent advances in global optimization, Journal of Global Optimization, 45, 1, 3-38 (2009) · Zbl 1180.90245 · doi:10.1007/s10898-008-9332-8
[32] Shen, P. P.; Liu, L. M., A linearization method for the global optimal solution of a quadratic programming problem with nonconvex quadratic constraints, Numerical Mathematics, 30, 3, 261-267 (2008) · Zbl 1174.65421
[33] Floudas, C. A.; Pardalos, P. M.; Adjiman, C. S.; Esposito, W. R.; Gümüş, Z. H.; Harding, S. T.; Klepeis, J. L.; Meyer, C. A.; Schweiger, C. A., Handbook of Test Problems in Local and Global Optimization, 33 (1999), Boston, Mass, USA: Kluwer Academic, Boston, Mass, USA · Zbl 0943.90001
[34] Lin, M.-H.; Tsai, J.-F., Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems, European Journal of Operational Research, 216, 1, 17-25 (2012) · Zbl 1242.90177 · doi:10.1016/j.ejor.2011.06.046
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.