An efficient parallel scheme for minimizing a sum of Euclidean norms (Q1123548)

For the problem \(F(x)=\sum_{i}w_ i\| A_ ix-b_ i\|_ 2\to \min\), where \(w_ i>0\), \(x\in {\mathbb{R}}^ n\), \(b\in {\mathbb{R}}^{m_ i}\), \(A_ i\) \(m_ i\times n\) matrices, Newton's method with line search is developed. Using QR decompositions of the \(A_ i\) saves considerable time in evaluating \(\nabla F\), \(\nabla^ 2F\) and the line search factors. The implementation of the algorithm of an Alliant FX/8 vector multiprocessor system is described. Numerical examples are given. The computing times are so low that a vector computer seems not to be necessary at all for this type of problem.