A computational study of global optimization solvers on two trust region subproblems

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.