On the updating scheme in a class of collinear scaling algorithms for sparse minimization

Sorensen (Ref. 1) has proposed a class of algorithms for sparse unconstrained minimization where the sparsity pattern of the Cholesky factors of the Hessian is known. His updates at each iteration depend on the choice of a vector, and in Ref. 1 the question of choosing this vector is essentially left open. In this note, we propose a variational problem whose solution may be used to choose this vector. The major part of the computation of a solution to this variational problem is similar to the computation of a trust-region step in unconstrained minimization. Therefore, well-developed techniques available for the latter problem can be used to compute this vector and to perform the updating.This research was supported by NSF Grant DMS-8414460 and by DOE Grant DE-FG06-85ER25007, awarded to Washington State University, and by the Applied Mathematical Sciences Subprogram of the US Department of Energy under Contract W-31-109-Eng-38 while the first author was visiting the Mathematics and Computer Science Division of Argonne National Laboratory.