# Linear Least Squares on the Unit Simplex

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.

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.

• Why assume that $\mathrm A$ is square? – Rodrigo de Azevedo Aug 8 '16 at 15:29
• @RodrigodeAzevedo: If $A$ is not square, it is not invertible, so one needs to solve $Ax=c$ after solving the closest point problem. – copper.hat Aug 8 '16 at 16:10
• Let me get this straight. Let's say I can project $b$ into the simplex. Namely $c = \operatorname{Proj}_{\mathcal{S}} \left( b \right)$ where $\mathcal{S}$ is the Unit Simplex. Then all needed is to solve $\hat{x} = \arg \min_{x} \left\| A x - c \right\|_{2}^{2}$? – Royi Aug 27 '17 at 16:28
• @Royi: No. There is much less content to my answer than you are thinking. You need to project $b$ onto $C$ then all I am saying is that you can recover a suitable $x$ by inverting. – copper.hat Aug 27 '17 at 16:35
• I wrote least squares in case $A$ isn't invertible. – Royi Aug 27 '17 at 16:37