A preconditioning framework for sequences of diagonally modified linear systems arising in optimization
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.
Entry Submitted: 12/28/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|