An Algorithm for Finding Nonnegative Minimal Norm Solutions of Linear Systems

Abstract

A system of linear equations $Ax = b$, in $n$ unknowns and $m$ equations which has a nonnegative solution is considered. Among all its solutions, the one which has the least norm is sought when $\mathbb{R}^n$ is equipped with a strictly convex norm. We present a globally convergent, iterative algorithm for computing this solution. This algorithm takes into account the special structure of the problem. Each iteration cycle of the algorithm involves the solution of a similar quadratic problem with a modified objective function. Duality conditions for optimality are studied. Feasibility and global convergence of the algorithm are proved. As a special case we implemented and tested the algorithm for the $\ell^p$-norm, where $1 < p < ∞$. Numerical results are included.