Regularization and preconditioning of KKT systems arising in nonnegative least-squares problems

被引：5

作者：

Bellavia, Stefania ^{[1
]}

Gondzii, Jacek ^{[2
]}

Morini, Benedetta ^{[1
]}

机构：

[1] Univ Florence, Dipartimento Energet S Stecco, I-50134 Florence, Italy

[2] Univ Edinburgh, Sch Math, Edinburgh EH9 3JZ, Midlothian, Scotland

来源：

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS | 2009年 / 16卷 / 01期

关键词：

bound-constrained linear least-squares problems; inexact Newton methods; iterative linear solvers; KKT systems; regularization; preconditioning; NONSYMMETRIC LINEAR-SYSTEMS; SADDLE-POINT PROBLEMS; NEWTON METHODS; BOUNDS; SUBJECT;

D O I：

10.1002/nla.610

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A regularized Newton-like method for solving nonnegative least-squares problems is proposed and analysed in this paper. A preconditioner for KKT systems arising in the method is introduced and spectral properties of the preconditioned matrix are analysed. A bound on the condition number of the preconditioned matrix is provided. The bound does not depend on the interior-point scaling matrix. Preliminary computational results confirm the effectiveness of the preconditioner and fast convergence of the iterative method established by the analysis performed in this paper. Copyright (C) 2008 John Wiley & Sons, Ltd.

引用

页码：39 / 61

页数：23

共 23 条

[1] Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization [J].

Altman, A ;

Gondzio, J .

OPTIMIZATION METHODS & SOFTWARE, 1999, 11-2 (1-4) :275-302

[2] ON THE AUGMENTED SYSTEM APPROACH TO SPARSE LEAST-SQUARES PROBLEMS [J].

ARIOLI, M ;

DUFF, IS ;

DERIJK, PPM .

NUMERISCHE MATHEMATIK, 1989, 55 (06) :667-684

[3] An interior point Newton-like method for non-negative least-squares problems with degenerate solution [J].

Bellavia, Stefania ;

Macconi, Maria ;

Morini, Benedetta .

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, 2006, 13 (10) :825-846

[4]

Benzi M, 2005, ACTA NUMER, V14, P1, DOI 10.1017/S0962492904000212

[5]

Bjorck A, 1996, NUMERICAL METHODS LE, DOI [10.1137/1.9781611971484, DOI 10.1137/1.9781611971484]

[6] An interior trust region approach for nonlinear minimization subject to bounds [J].

Coleman, TF ;

Li, YY .

SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (02) :418-445

[7]

DAVIS T, 1996, NA DIGEST, V96

[8]

Davis T., 1997, NA Digest, V97

[9]

Davis T.A., 1994, NA DIGEST, V92

[10] INEXACT NEWTON METHODS [J].

DEMBO, RS ;

EISENSTAT, SC ;

STEIHAUG, T .

SIAM JOURNAL ON NUMERICAL ANALYSIS, 1982, 19 (02) :400-408

← 1 2 3 →