Trust-region and other regularisations of linear least-squares problems

Coralia Cartis(coralia.cartised.ac.uk)
Nicholas Gould(nick.gouldcomlab.ox.ac.uk)
Philippe Toint(philippe.tointfundp.ac.be)

Abstract: We consider methods for regularising the least-squares solution of the linear system Ax = b. In particular, we propose iterative methods for solving large problems in which a trust-region bound ||x|| <= Delta is imposed on the size of the solution, and in which the least value of linear combinations of ||Ax-b||_2^q and a regularisation term ||x||_2^p for various p and q =1,2 is sought. In each case, one of more ``secular'' equations are derived, and fast Newton-like solution procedures are suggested. The resulting algorithms are available as part of the GALAHAD optimization library.

Keywords: linear least-squares, regularisation, trust-region, secular equation

Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: Technical report Numerical Analysis Group Oxford University.

Download: [PDF]

Entry Submitted: 02/03/2008
Entry Accepted: 02/03/2008
Entry Last Modified: 02/03/2008

Modify/Update this entry