4
$\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$
0

1 Answer 1

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$
11
  • 1
    $\begingroup$ Why assume that $\mathrm A$ is square? $\endgroup$ Aug 8, 2016 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, 2016 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, 2017 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, 2017 at 16:35
  • $\begingroup$ I wrote least squares in case $ A $ isn't invertible. $\endgroup$
    – Royi
    Aug 27, 2017 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.