Non-negative least squares

Remarks

The problem always has a solution. The image of the non-negative orthant under $A$ is a closed convex cone, and $Ax^*$ is the nearest point of that cone to $b$. The objective is a convex function, so NNLS is a convex quadratic programming problem, and the solution is unique when $A$ has full column rank. By the Karush–Kuhn–Tucker conditions, $x$ is a solution if and only if, with $w = A^T(b - Ax)$, one has $x \ge 0$, $w \le 0$ and $x_i w_i = 0$ for every $i$. Example: for $A = I$ the solution is $x^*_i = \max(b_i, 0)$, which satisfies these conditions. The classical algorithm is the active-set method of Lawson and Hanson, published in their 1974 book Solving Least Squares Problems. It moves variables between a free set and a set fixed at zero. At each step it solves an unconstrained least squares problem on the free set, and it stops after finitely many steps. Projected gradient and coordinate descent methods are used for large problems.