Optimization Online


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

Tiago Montanher (tiago.de.morais.montanher***at***univie.ac.at)
Arnold Neumaier (Arnold.Neumaier***at***univie.ac.at)
Ferenc Domes (ferenc.domes***at***univie.ac.at)

Abstract: 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.

Keywords: Reliability analysis; Cluster effect; Branch-and-bound solvers; SDP-relaxations; Celis-Dennis-Tapia subproblem

Category 1: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Category 2: Global Optimization

Category 3: Global Optimization (Applications )

Citation: Submitted.

Download: [PDF]

Entry Submitted: 04/02/2018
Entry Accepted: 04/02/2018
Entry Last Modified: 04/02/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society