It has recently been shown (Burer, Math Program 120:479–495, 2009) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs, i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are NP-hard in general. A basic tractable relaxation is gotten by approximating the completely positive matrices with doubly nonnegative matrices, i.e., matrices which are both nonnegative and positive semidefinite, resulting in a doubly nonnegative program (DNP). Optimizing a DNP, while polynomial, is expensive in practice for interior-point methods. In this paper, we propose a practically efficient decomposition technique, which approximately solves the DNPswhile simultaneously producing lower bounds on the original NQP. We illustrate the effectiveness of our approach for solving the basic relaxation of box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For one quadratic assignment instance, a best-known lower bound is obtained. We also incorporate the lower bounds within a branch-andbound scheme for solving BoxQPs and the quadratic multiple knapsack problem. In particular, to the best of our knowledge, the resulting algorithm for globally solving BoxQPs is the most efficient to date.

The solution of trust-region and regularisation subproblems that arise in unconstrained optimization is considered. Building on the pioneering work of Gay, Moré and Sorensen, methods that obtain the solution of a sequence of parametrized linear systems by factorization are used. Enhancements using high-order polynomial approximation and inverse iteration ensure that the resulting method is both globally and asymptotically at least superlinearly convergent in all cases, including the notorious hard case. Numerical experiments validate the effectiveness of our approach. The resulting software is available as packages TRS and RQS as part of the GALAHAD optimization library, and is especially designed for large-scale problems.

Quadratic assignment problems (QAPs) are known to be among the hardest discrete optimization problems. Recent study shows that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the so-called symmetric mappings that can be used to derive strong cuts for the proposed relaxation model. We show that the bounds based on the new models are comparable to some strong bounds in the literature. Promising experimental results based on the new relaxations are reported.