3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why assume that $\mathrm A$ is square? $\endgroup$ – Rodrigo de Azevedo Aug 8 '16 at 15:29
  • $\begingroup$ @RodrigodeAzevedo: If $A$ is not square, it is not invertible, so one needs to solve $Ax=c$ after solving the closest point problem. $\endgroup$ – copper.hat Aug 8 '16 at 16:10
  • $\begingroup$ 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} $? $\endgroup$ – Royi Aug 27 '17 at 16:28
  • $\begingroup$ @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. $\endgroup$ – copper.hat Aug 27 '17 at 16:35
  • $\begingroup$ I wrote least squares in case $ A $ isn't invertible. $\endgroup$ – Royi Aug 27 '17 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.