Least-squares over the unit simplex

Question

I am interested in the non-negative least squares problem subject to one equality constraint

$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} & \mathrm 1_n^T \mathrm x = 1\\ & \mathrm x \geq 0_n\end{array}$$

Each element of vector $\mathrm x$ is non-negative and they sum to one. Is there any closed solution or fast iterative method? The dimension of $\mathrm x$ is not very big, but I need a fast method as this optimization is to be executed many times for different sub-sampled data sets.

Answer 1

Here is one approach that works if $A$ is invertible:

You are projecting $b$ onto the convex set $A \Sigma$, where $\Sigma = \{ x | x_k \ge 0, \sum_k x_k = 1\}$.

Let $C = \operatorname{co} \{ A e_k \}_k$, then the problem becomes one of finding the closest point $c\in C$ to $b$. Then the solution is $x=A^{-1} c$.

I am not current, but an efficient algorithm for solving this problem is given in Wolfe, P. ,Finding the Nearest Point in a Polytope, Mathematical Programming, Vol. 11, pp. 128–149,1976.

If $A$ is not invertible, one needs to solve $Ax = c$ to obtain a solution.