A computational study of global optimization solvers on two trust region subproblems. (English) Zbl 1405.90096
Summary: One of the relevant research topics to which Chris Floudas contributed was quadratically constrained quadratic programming (QCQP). This paper considers one of the simplest hard cases of QCQP, the two trust region subproblem (TTRS). In this case, one needs to minimize a quadratic function constrained by the intersection of two ellipsoids. The Lagrangian dual of the TTRS is a semidefinite program (SDP) and this result has been extensively used to solve the problem efficiently. We focus on numerical aspects of branch-and-bound solvers with three goals in mind. We provide (i) a detailed analysis of the ability of state-of-the-art solvers to complete the global search for a solution, (ii) a quantitative approach for measuring the cluster effect on each solver and (iii) a comparison between the branch-and-bound and the SDP approaches. We perform the numerical experiments on a set of 212 challenging problems provided by Kurt Anstreicher. Our findings indicate that SDP relaxations and branch-and-bound have orthogonal difficulties, thus pointing to a possible benefit of a combined method. The following solvers were selected for the experiments: Antigone 1.1, Baron 16.12.7, Lindo Global 10.0, Couenne 0.5 and SCIP 3.2.
MSC:
| 90C20 | Quadratic programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
reliability analysis; cluster effect; branch-and-bound solvers; SDP-relaxations; Celis-Dennis-Tapia subproblemSoftware:
MINPACK-2; testenv; GAMS; ANTIGONE; LINDOGlobal; GloMIQO; QPLIB; Couenne; Optimization Test Environment; BARON; LINDO; SCIPReferences:
| [1] | Adjiman, CS; Androulakis, IP; Floudas, CA, A global optimization method, \(α \)BB, for general twice-differentiable constrained NLPs—II. implementation and computational results, Comput. Chem. Eng., 22, 1159-1179, (1998) · doi:10.1016/S0098-1354(98)00218-X |
| [2] | Adjiman, CS; Dallwig, S; Floudas, CA; Neumaier, A, A global optimization method, \(α \)BB, for general twice-differentiable constrained NLPs—I. theoretical advances, Comput. Chem. Eng., 22, 1137-1158, (1998) · doi:10.1016/S0098-1354(98)00027-1 |
| [3] | Ai, W; Zhang, S, Strong duality for the CDT subproblem: a necessary and sufficient condition, SIAM J. Optim., 19, 1735-1756, (2009) · Zbl 1187.90290 · doi:10.1137/07070601X |
| [4] | Androulakis, IP; Maranas, CD; Floudas, CA, \(α \)BB: a global optimization method for general constrained nonconvex problems, J. Glob. Optim., 7, 337-363, (1995) · Zbl 0846.90087 · doi:10.1007/BF01099647 |
| [5] | Anstreicher, K; Wolkowicz, H, On Lagrangian relaxation of quadratic matrix constraints, SIAM J. Matrix Anal. Appl., 22, 41-55, (2000) · Zbl 0990.90088 · doi:10.1137/S0895479898340299 |
| [6] | Anstreicher, KM, Kronecker product constraints with an application to the two-trust-region subproblem, SIAM J. Optim., 27, 368-378, (2017) · Zbl 1357.90105 · doi:10.1137/16M1078859 |
| [7] | Averick, B.M., Carter, R.G., Moré, J.J.: The MINPACK-2 test problem collection. Argonne National Laboratory, Mathematics and Computer Science Division (1992) · Zbl 0795.90070 |
| [8] | Beck, A; Eldar, YC, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17, 844-860, (2006) · Zbl 1128.90044 · doi:10.1137/050644471 |
| [9] | Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and boundstightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124 |
| [10] | Bienstock, D, A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26, 488-498, (2016) · Zbl 1382.90083 · doi:10.1137/15M1009871 |
| [11] | Birgin, EG; Floudas, CA; Martínez, JM, Global minimization using an augmented Lagrangian method with variable lower-level constraints, Math. Program., 125, 139-162, (2010) · Zbl 1198.90322 · doi:10.1007/s10107-009-0264-y |
| [12] | Bomze, IM; Overton, ML, Narrowing the difficulty gap for the celis-dennis-tapia problem, Math. Program., 151, 459-476, (2015) · Zbl 1328.90095 · doi:10.1007/s10107-014-0836-3 |
| [13] | Brook, A; Kendrick, D; Meeraus, A, GAMS, a user’s guide, ACM Signum Newsl., 23, 10-11, (1988) · doi:10.1145/58859.58863 |
| [14] | Burer, S; Anstreicher, KM, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23, 432-451, (2013) · Zbl 1298.90062 · doi:10.1137/110826862 |
| [15] | Celis, MR; Dennis, JE; Tapia, RA; Boggs, PT (ed.); Byrd, RH (ed.); Schnabel, RB (ed.), A trust region strategy for nonlinear equality constrained optimization, (1985), Philadelphia · Zbl 0566.65048 |
| [16] | Chen, X; Yuan, Y, On local solutions of the celis-dennis-tapia subproblem, SIAM J. Optim., 10, 359-383, (2000) · Zbl 0957.65060 · doi:10.1137/S1052623498335018 |
| [17] | Chen, X; Yuan, Y, On maxima of dual function of the CDT subproblem, J. Comput. Math., 19, 113-124, (2001) · Zbl 0982.65074 |
| [18] | Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071 · doi:10.1137/1.9780898719857 |
| [19] | Domes, F., Fuchs, M., Schichl, H., Neumaier, A.: The optimization test environment. Optim. Eng. 15, 443-468 (2014). http://www.mat.univie.ac.at/ dferi/testenv.html · Zbl 1364.90006 |
| [20] | Domes, F., Neumaier, A.: Constraint aggregation in global optimization. Math. Program. 155, 375-401 (2016). http://www.mat.univie.ac.at/ dferi/research/Aggregate.pdf · Zbl 1342.90142 |
| [21] | Du, K., Kearfott, R.B.: The cluster problem in multivariate global optimization. J. Glob. Optim. 5(3), 253-265 (1994). http://interval.louisiana.edu/preprints/multcluster.pdf · Zbl 0824.90121 |
| [22] | El-Alem, M, A global convergence theory for the celis-dennis-tapia trust-region algorithm for constrained optimization, SIAM J. Numer. Anal., 28, 266-290, (1991) · Zbl 0725.65061 · doi:10.1137/0728015 |
| [23] | Floudas, C.A.: Deterministic Global Optimization: Theory, Methods and Applications. Nonconvex Optimization and Its Applications. Kluwer Academic Publisher, Dordrecht (2000) · Zbl 1037.90002 · doi:10.1007/978-1-4757-4949-6 |
| [24] | Floudas, CA; Visweswaran, V, A global optimization algorithm (GOP) for certain classes of nonconvex NLPs—I. theory, Comput. Chem. Eng., 14, 1397-1417, (1990) · doi:10.1016/0098-1354(90)80020-C |
| [25] | Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gleixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H., Sahinidis, N., Vigerske, S., Wiegele, A.: QPLIB: A Library of Quadratic Programming Instances. Technical report (February 2017). http://www.optimization-online.org/DB_HTML/2017/02/5846.html · Zbl 1112.90093 |
| [26] | Goldsztejn, A., Domes, F., Chevalier, B.: First order rejection tests for multiple-objective optimization. J. Glob. Optim. , 58, 653-672 (2014). http://www.mat.univie.ac.at/ dferi/research/FirstOrder.pdf · Zbl 1301.90082 |
| [27] | Li, G, On KKT points of celis-dennis-tapia subproblem, Sci. China Ser. A, 49, 651-659, (2006) · Zbl 1112.90093 · doi:10.1007/s11425-006-0651-2 |
| [28] | Li, G; Yuan, Y, Compute a celis-dennis-tapia step, J. Comput. Math., 23, 463-478, (2005) · Zbl 1080.65048 |
| [29] | Lin, Y; Schrage, L, The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668, (2009) · Zbl 1177.90325 · doi:10.1080/10556780902753221 |
| [30] | Martínez, JM, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4, 159-176, (1994) · Zbl 0801.65057 · doi:10.1137/0804009 |
| [31] | Misener, R., Floudas, C.A.: Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math. Program. B 136(1), 155-182 (2012). http://www.optimization-online.org/DB_HTML/2011/11/3240.html · Zbl 1257.90079 |
| [32] | Misener, R., Floudas, C.A.: GloMIQO: Global mixed-integer quadratic optimizer. J. Glob. Optim. 57(1), 3-50 (2013). ISSN 0925-5001. http://dx.doi.org/10.1007/s10898-012-9874-7 · Zbl 1272.90034 |
| [33] | Misener, R; Floudas, CA, Antigone: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2 |
| [34] | Misener, Ruth; Smadbeck, James B; Floudas, Christodoulos A, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into glomiqo 2, Optim. Methods Softw., 30, 215-249, (2015) · Zbl 1325.90071 · doi:10.1080/10556788.2014.916287 |
| [35] | Neumaier, A.: Interval methods for systems of equations. In: Encyclopedia of Mathematics and its Applications, vol. 37. Cambridge University Press, Cambridge (1990) · Zbl 0715.65030 |
| [36] | Neumaier, A; Shcherbina, O; Huyer, W; Vinkó, T, A comparison of complete global optimization solvers, Math. Program. B, 103, 335-356, (2005) · Zbl 1099.90001 · doi:10.1007/s10107-005-0585-4 |
| [37] | Nie, P, CDT like approaches for the system of nonlinear equations, Appl. Math. Comput., 172, 892-902, (2006) · Zbl 1088.65049 |
| [38] | Peng, JM; Yuan, Y, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7, 579-594, (1997) · Zbl 0891.90150 · doi:10.1137/S1052623494261520 |
| [39] | Takeda, A., Sakaue, S., Nakatsukasa, Y., Iwata, S.: A polynomial-time algorithm for nonconvex quadratic optimization with two quadratic constraints. In preparation (2015) http://www.keisu.t.u-tokyo.ac.jp/research/techrep/data/2015/METR15-03.pdf · Zbl 1328.90095 |
| [40] | Sahinidis, N.V.: Baron 12.1.0: global optimization of mixed-integer nonlinear programs. User’s Manual (2013). http://www.gams.com/dd/docs/solvers/baron.pdf · Zbl 1198.90322 |
| [41] | Schichl, H; Markót, MC; Neumaier, A, Exclusion regions for optimization problems, J. Glob. Optim., 59, 569-595, (2014) · Zbl 1297.65070 · doi:10.1007/s10898-013-0137-z |
| [42] | Schichl, H; Neumaier, A, Exclusion regions for systems of equations, SIAM J. Numer. Anal., 42, 383-408, (2004) · Zbl 1080.65041 · doi:10.1137/S0036142902418898 |
| [43] | Vigerske, S., Gleixner, A.: SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework. Technical report 16-24, ZIB, Takustr. 7, 14195 Berlin (2016) · Zbl 1398.90112 |
| [44] | Visweswaran, V; Floudas, CA, A global optimization algorithm (GOP) for certain classes of nonconvex NLPs-II. application of theory and test problems, Comput. Chem. Eng., 14, 1419-1434, (1990) · doi:10.1016/0098-1354(90)80021-3 |
| [45] | Visweswaran, V; Floudas, CA, New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints, J. Glob. Optim., 3, 439-462, (1993) · Zbl 0795.90070 · doi:10.1007/BF01096414 |
| [46] | Yang, B; Burer, S, A two-variable approach to the two-trust-region subproblem, SIAM J. Optim., 26, 661-680, (2016) · Zbl 1333.90087 · doi:10.1137/130945880 |
| [47] | Yuan, J; Wang, M; Ai, W; Shuai, T, New results on narrowing the duality gap of the extended celis-dennis-tapia problem, SIAM J. Optim., 27, 890-909, (2017) · Zbl 1471.90108 · doi:10.1137/16M1080082 |
| [48] | Yuan, Y, On a subproblem of trust region algorithms for constrained optimization, Math. Program., 47, 53-63, (1990) · Zbl 0711.90062 · doi:10.1007/BF01580852 |
| [49] | Yuan, Y, Recent advances in trust region algorithms, Math. Program., 151, 249-281, (2015) · Zbl 1317.65141 · doi:10.1007/s10107-015-0893-2 |
| [50] | Zhang, A; Hayashi, S, Celis-dennis-tapia based approach to quadratic fractional programming problems with two quadratic constraints, Numer. Algebra Control Optim., 1, 83-98, (2011) · Zbl 1219.90169 · doi:10.3934/naco.2011.1.83 |
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.
