On fast trust region methods for quadratic models with linear constraints

  • 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 n2 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:M. J. D. Powell
DOI:https://doi.org/10.1007/s12532-015-0084-4
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2015
Tag:Software; Theoretical Computer Science
Volume:7
Issue:3
Page Number:31
First Page:237
Last Page:267
Mathematical Programming Computation :MPC 2015 - Issue 3
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.