Optimization Online


A preconditioning framework for sequences of diagonally modified linear systems arising in optimization

Stefania Bellavia(stefania.bellavia***at***unifi.it)
Valentina De Simone(valentina.desimone***at***unina2.it)
Daniela di Serafino(daniela.diserafino***at***unina2.it)
Benedetta Morini(benedetta.morini***at***unifi.it)

Abstract: We propose a framework for building preconditioners for sequences of linear systems of the form $(A+\Delta_k) x_k=b_k$, where $A$ is symmetric positive semidefinite and $\Delta_k$ is diagonal positive semidefinite. Such sequences arise in several optimization methods, e.g., in affine-scaling methods for bound-constrained convex quadratic programming and bound-constrained linear least squares, as well as in trust-region and overestimation methods for convex unconstrained optimization problems and nonlinear least squares. For all the matrices of a sequence, the preconditioners are obtained by updating any preconditioner for $A$ available in the $LDL^T$ form. The preconditioners in the framework satisfy the natural requirement of being effective on slowly varying sequences; furthermore, under an additional property they are also able to cluster eigenvalues of the preconditioned matrix when some entries of $\Delta_k$ are sufficiently large. We present two low-cost preconditioners sharing the above-mentioned properties and evaluate them on sequences of linear systems generated by the reflective Newton method applied to bound-constrained convex quadratic programming problems, and on sequences arising in solving nonlinear least-squares problems with the Regularized Euclidean Residual method. The results of the numerical experiments show the effectiveness of these preconditioners.

Keywords: Sequences of linear systems, preconditioning, incomplete $LDL^T$ factorization, large-scale convex optimization.

Category 1: Nonlinear Optimization

Citation: Technical Report 2/2011, Dipartimento di Energetica ``Sergio Stecco'', Universita' di Firenze, Italy.

Download: [PDF]

Entry Submitted: 12/28/2011
Entry Accepted: 12/28/2011
Entry Last Modified: 12/28/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society