×

zbMATH — the first resource for mathematics

Bounds tightening based on optimality conditions for nonconvex box-constrained optimization. (English) Zbl 1359.90107
Summary: First-order optimality conditions have been extensively studied for the development of algorithms for identifying locally optimal solutions. In this work, we propose two novel methods that directly exploit these conditions to expedite the solution of box-constrained global optimization problems. These methods carry out domain reduction by application of bounds tightening methods on optimality conditions. This scheme is implicit and avoids explicit generation of optimality conditions through symbolic differentation, which can be memory and time intensive. The proposed bounds tightening methods are implemented in the global solver BARON. Computational results on a test library of 327 problems demonstrate the value of our proposed approach in reducing the computational time and number of nodes required to solve these problems to global optimality.

MSC:
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T, SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[2] Ali, MM; Khompatraporn, C; Zabinsky, ZB, A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems, J. Glob. Optim., 31, 635-672, (2005) · Zbl 1093.90028
[3] Amaran, S; Sahinidis, NV, Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints, TOP, 20, 154-172, (2012) · Zbl 1258.93102
[4] Bao, X; Khajavirad, A; Sahinidis, NV; Tawarmalani, M, Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7, 1-37, (2015) · Zbl 1317.90243
[5] Bao, X; Sahinidis, NV; Tawarmalani, M, Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs, Optim. Methods Softw., 24, 485-504, (2009) · Zbl 1179.90252
[6] Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming, Theory and Algorithms, 2nd edn, Series in Discrete Mathematics and Optimization. Wiley Interscience, Hoboken (1993)
[7] Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[8] Bierlaire, M; Toint, PL, Meuse: an origin-destination matrix estimator that exploits structure, Transp. Res. Part B Methodol., 29, 47-60, (1995)
[9] Bound-constrained programs. http://minlp.com/nlp-and-minlp-test-problems · Zbl 1062.90041
[10] Brooke, A., Kendrick, D., Meeraus, A.: GAMS-A User’s Guide. The Scientific Press, Redwood City (1988)
[11] Burer, S; Chen, J, Relaxing the optimality conditions of box QP, Comput. Optim. Appl., 48, 653-673, (2011) · Zbl 1242.90151
[12] 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
[13] Burer, S; Vandenbussche, D, Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, Comput. Optim. Appl., 43, 181-195, (2009) · Zbl 1170.90522
[14] Chen, J; Burer, S, Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Program. Comput., 4, 33-52, (2012) · Zbl 1257.90065
[15] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[16] Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking Optimization Software with COPS 3.0. Argonne National Laboratory Research Report (2004)
[17] Domes, F; Neumaier, A, Constraint aggregation for rigorous global optimization, Math. Program., 155, 375-401, (2016) · Zbl 1342.90142
[18] Floudas, C.A., Pardalos, P.M., Adjiman, C., Esposito, W.R., Gümüs, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization, vol. 33. Springer, Berlin (2013) · Zbl 0943.90001
[19] GLOBAL Library. http://www.gamsworld.org/global/globallib.htm · Zbl 0454.65049
[20] Hansen, P; Jaumard, B; Ruiz, M; Xiong, J, Global minimization of indefinite quadratic functions subject to box constraints, Nav. Res. Logist. (NRL), 40, 373-392, (1993) · Zbl 0782.90071
[21] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 3rd edn. Springer, Berlin (1996) · Zbl 0867.90105
[22] Hu, J; Mitchell, JE; Pang, J, An LPCC approach to nonconvex quadratic programs, Math. Program., 133, 243-277, (2012) · Zbl 1244.90177
[23] Karush, W.: Minima of Functions of Several Variables with Inequalities as Side Constraints. Master’s thesis, Department of Mathematics, University of Chicago, Chicago, IL (1939) · Zbl 1244.90177
[24] Khajavirad, A; Sahinidis, NV, Convex envelopes of products of convex and component-wise concave functions, J. Glob. Optim., 52, 391-409, (2011) · Zbl 1268.90052
[25] Khajavirad, A; Sahinidis, NV, Convex envelopes generated from finitely many compact convex sets, Math. Program., 137, 371-408, (2013) · Zbl 1284.90055
[26] Kuhn, HW; Tucker, AW; Neyman, J (ed.), Nonlinear programming, 481-492, (1951), Berkeley
[27] Lin, Y; Schrage, L, The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668, (2009) · Zbl 1177.90325
[28] Lundell, A; Westerlund, T, Convex underestimation strategies for signomial functions, Optim. Methods Softw., 24, 505-522, (2009) · Zbl 1178.90278
[29] MacMOOP Library. https://wiki.mcs.anl.gov/leyffer/index.php/MacMOOP
[30] Markót, MC; Schichl, H, Bound constrained interval global optimization in the COCONUT environment, J. Glob. Optim., 60, 751-776, (2014) · Zbl 1302.90152
[31] Meyer, CA; Floudas, CA, Convex envelopes for edge-concave functions, Math. Program., 103, 207-224, (2005) · Zbl 1099.90045
[32] Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063
[33] Moré, JJ; Garbow, BS; Hillstrom, KE, Testing unconstrained optimization software, ACM Trans. Math. Softw., 7, 17-41, (1981) · Zbl 0454.65049
[34] Nocedal, J; Hennart, JP (ed.), Solving large nonlinear systems of equations arising in mechanics, 132-141, (1982), Berlin
[35] Princeton Library. http://www.gamsworld.org/performance/princetonlib/princetonlib.htm · Zbl 1135.90034
[36] Ryoo, HS; Sahinidis, NV, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Comput. Chem. Eng., 19, 551-566, (1995)
[37] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-139, (1996) · Zbl 0856.90103
[38] Sahinidis, NV; Bliek, C (ed.); Jermann, C (ed.); Neumaier, A (ed.), Global optimization and constraint satisfaction: the branch-and-reduce approach, No. 2861, 1-16, (2003), Berlin · Zbl 1255.90102
[39] Sahinidis, NV; Tawarmalani, M, Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints, J. Glob. Optim., 32, 259-280, (2005) · Zbl 1080.90087
[40] Schichl, H; Neumaier, A, Transposition theorems and qualification-free optimality conditions, SIAM J. Optim., 17, 1035-1055, (2006) · Zbl 1136.90043
[41] Seber, G.A.F., Wild, C.J.: Nonlinear Regression. Wiley, Hoboken (2005) · Zbl 0721.62062
[42] Shectman, JP; Sahinidis, NV, A finite algorithm for global minimization of separable concave programs, J. Glob. Optim., 12, 1-36, (1998) · Zbl 0906.90159
[43] SymPy. http://sympy.org/en/index.html
[44] Tawarmalani, M; Richard, JP; Xiong, C, Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., 138, 531-577, (2013) · Zbl 1273.90165
[45] Tawarmalani, M; Sahinidis, NV, Convex extensions and convex envelopes of l.s.c. functions, Math. Program., 93, 247-263, (2002) · Zbl 1065.90062
[46] Tawarmalani, M; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[47] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[48] Toint, PL, Some numerical results using a sparse matrix updating formula in unconstrained optimization, Math. Comput., 32, 839-851, (1978) · Zbl 0381.65036
[49] Vandenbussche, D; Nemhauser, GL, A branch-and-cut algorithm for nonconvex quadratic programs with box constraints, Math. Program., 102, 559-575, (2005) · Zbl 1137.90010
[50] Vandenbussche, D; Nemhauser, GL, A polyhedral study of nonconvex quadratic programs with box constraints, Math. Program., 102, 531-557, (2005) · Zbl 1137.90009
[51] Wesolowsky, G, The Weber problem: history and perspective, Locat. Sci., 1, 5-23, (1993) · Zbl 0923.90110
[52] Zhang, Z, Parameter estimation techniques: a tutorial with application to conic Fitting, Image Vis. Comput., 15, 59-76, (1997)
[53] Zorn, K; Sahinidis, NV, Global optimization of general nonconvex problems with intermediate bilinear substructures, Optim. Methods Softw., 29, 442-462, (2013) · Zbl 1285.90043
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.