The following paper, “On fast trust region methods for quadratic models with linear constraints” by Michael J.D. Powell, was submitted to Mathematical Programming Computation in August 2014, andwas still in review when we became aware of Mike’s deteriorating health. Unfortunately, despite our best efforts and those of two referees, Mike died before we were able to send him our verdict. Both referees had concerns about points that needed further explanation, but in all likelihood—and after a few clarifying iterations—the paper would ultimately have been published. As we believe that the ideas central to the paper are of general interest to the journal’s readership, we have taken the unusual step of publishing the paper “as is”. Readers might, like the referees, question some of the statements made, but we feel it would be wrong tosecond guess Mike’s intentions, and have chosen to leave such statements alone.Mike had a profound effect on computational nonlinear optimization. We dedicate this paper to his memory.

Quadratic models Qk (x), x ? Rn, of the objective function F(x), x ? Rn, are used by many successful iterative algorithms for minimization, where k is the iteration number. Given the vector of variables xk ? Rn, a new vector xk+1 may be calculated that satisfies Qk (xk+1) < Qk (xk ), in the hope that it provides the reduction F(xk+1) < F(xk ). Trust region methods include a bound of the form xk+1 ? xk  ? k . Also we allow general linear constraints on the variables that have to hold at xk and at xk+1. We consider the construction of xk+1, using only of magnitude n² operations on a typical iteration when n is large. The linear constraints are treated by active sets, which may be updated during an iteration, and which decrease the number of degrees of freedom in the variables temporarily, by restricting x to an affine subset of Rn. Conjugate gradient and Krylov subspace methods are addressed for adjusting the reduced variables, but the resultant steps are expressed in terms of the original variables. Termination conditions are given that are intended to combine suitable reductions in Qk (·) with a sufficiently small number of steps. The reason for our work is that xk+1 is required in the LINCOA software of the author, which is designed for linearly constrained optimization without derivatives when there are hundreds of variables. Our studies go beyond the final version of LINCOA, however, which employs conjugate gradients with termination at the trust region boundary. In particular, we find that, if an active set is updated at a point that is not the trust region centre, then the Krylov method may terminate too early due to a degeneracy. An extension to the conjugate gradient method for searching round the trust region boundary receives attention too, but it was also rejected from LINCOA, because of poor numerical results. The given techniques of LINCOA seem to be adequate in practice.

The equality generalized traveling salesman problem (E-GTSP) is an extension of the traveling salesman problem (TSP) where the set of cities is partitioned into clusters, and the salesman has to visit every cluster exactly once. It is well known that any instance of E-GTSP can be transformed into a standard asymmetric instance of the TSP, and therefore solved with a TSP solver. This paper evaluates the performance of the state-of-the art TSP solver Lin–Kernighan–Helsgaun (LKH) on transformed E-GTSP instances. Although LKH is used without any modifications, the computational evaluation shows that all instances in a well-known library of benchmark instances, GTSPLIB, could be solved to optimality in a reasonable time. In addition, it was possible to solve a series of new very-large-scale instances with up to 17,180 clusters and 85,900 vertices. Optima for these instances are not known but it is conjectured that LKH has been able to find solutions of a very high quality. The program’s performance has also been evaluated on a large number of instances generated by transforming arc routing problem instances into E-GTSP instances. The program is free of charge for academic and non-commercial use and can be downloaded in source code.

Quadratic programming problems (QPs) that arise from dynamic optimization problems typically exhibit a very particular structure. We address the ubiquitous case where these QPs are strictly convex and propose a dual Newton strategy that exploits the block-bandedness similarly to an interior-point method. Still, the proposed method features warmstarting capabilities of active-set methods. We give details for an efficient implementation, including tailored numerical linear algebra, step size computation, parallelization, and infeasibility handling. We prove convergence of the algorithm for the considered problem class. A numerical study based on the open-source implementation qpDUNES shows that the algorithm outperforms both well-established general purpose QP solvers as well as state-of-the-art tailored control QP solvers significantly on the considered benchmark problems.

In this paper, we present a majorized semismooth Newton-CG augmented Lagrangian method, called SDPNAL+, for semidefinite programming (SDP) with partial or full nonnegative constraints on the matrix variable. SDPNAL+ is a much enhanced version of SDPNAL introduced by Zhao et al. (SIAM J Optim 20:1737–1765, 2010) for solving generic SDPs. SDPNAL works very efficiently for nondegenerate SDPs but may encounter numerical difficulty for degenerate ones. Here we tackle this numerical difficulty by employing a majorized semismooth Newton- CG augmented Lagrangian method coupled with a convergent 3-block alternating direction method of multipliers introduced recently by Sun et al. (SIAM J Optim, to appear). Numerical results for various large scale SDPs with or without nonnegative constraints show that the proposed method is not only fast but also robust in obtaining accurate solutions. It outperforms, by a significant margin, two other competitive publicly available first order methods based codes: (1) an alternating direction method of multipliers based solver called SDPAD by Wen et al. (Math Program Comput 2:203– 230, 2010) and (2) a two-easy-block-decomposition hybrid proximal extragradient method called 2EBD-HPE by Monteiro et al. (Math Program Comput 1–48, 2014). In contrast to these two codes, we are able to solve all the 95 difficult SDP problems arising from the relaxations of quadratic assignment problems tested in SDPNAL to an accuracy of 10?6 efficiently, while SDPAD and 2EBD-HPE successfully solve 30 and 16 problems, respectively. In addition, SDPNAL+ appears to be the only viable method currently available to solve large scale SDPs arising from rank-1 tensor approximation problems constructed by Nie and Wang (SIAM J Matrix Anal Appl 35:1155–1179, 2014). The largest rank-1 tensor approximation problem we solved (in about 14.5 h) is nonsym(21,4), in which its resulting SDP problem has matrix dimension n = 9261 and the number of equality constraints m = 12,326,390.