Equality Constrained Non Negative Linear Least Squares (Unit Simplex Constraint)

I have the following constrained linear least-squares problem:

$$\min_{x \in \mathbb{R}^n} \frac{1}{2}||Ax-b||_2^2,$$

$$\text{subject to } \sum_{i=1}^n x_i = 1 \text{ and } x_i \geq 0, \text{ for } i=1,...,n.$$

If we discard the equality constraint, we have a standard non-negative least-squares (NNLS) problem, which can be solved by any NNLS solver.

On the other hand, if we discard the non-negativity constraints, we have a least-squares problem with an equality constraint, which can be solved in closed form (up to a matrix inverse calculation) by using Lagrange multipliers, for instance.

However, considering both constraints, I do not see any method that is particularly suitable for the problem. Of course, I could use the projected gradient descent method, but this one is pretty generic and does not exploit the linear least-squares nature of the problem.

My questions are:

1- Is there any numerical optimization algorithm that is particularly suitable for this problem?

2- Or can I reformulate the problem in a less constrained form so that can it be solved by a standard NNLS solver?

My attempt:

The Lagrangian is:

$$L(x,\lambda,\mu) = \frac{1}{2}||Ax-b||_2^2 + \lambda (\mathbf{1}^Tx - 1) - \mu^T x,$$ where $$\lambda$$ is a scalar, $$\mu$$ is $$n$$-dimensional and $$\mathbf{1}$$ is an $$n$$-dimensional vector of ones.

Thus, writing the KKT conditions, we get:

$$\begin{pmatrix} A^TA & \mathbf{1} & -I \\ \mathbf{1}^T & 0 & \mathbf{0}^T \end{pmatrix}\begin{pmatrix} x \\ \lambda \\ \mu\end{pmatrix} = \begin{pmatrix} A^Tb \\ 1 \end{pmatrix}, \text{ } \mu_i \geq 0, \text{ and } \mu_i x_i = 0, \text{ for } i=1,...,n.$$

I don't know how to proceed from here, due to the complementary slackness constraints...

• That’s precisely the purpose of the $n$-dimensional vector $\mu$. – learner Sep 11 '19 at 10:37
• Sorry, please ignore my earlier comment- wasn't reading carefully. – Brian Borchers Sep 11 '19 at 13:55
• Related - math.stackexchange.com/questions/2935650. – Royi Mar 18 '20 at 21:06

Your problem can be formulated as convex quadratic programming problem with a linear equality constraint and nonnegativity constraints on $$x$$.

$$\min \frac{1}{2}\left( x^{T}(A^{T}A)x - 2(b^{T}A)x + b^{T}b \right)$$

subject to

$$\sum_{i=1}^{n} x_{i}=1$$

$$x \geq 0$$.

As a practical matter, you're probably best off using a well-written library routine for linearly constrained quadratic programming. There are many of them available in a variety of programming languages. If you need to implement this yourself, then implementing an active set QP solver is relatively straight forward.

• could you please elaborate a bit more on how to formulate this problem as a quadratic programming one? – learner Sep 11 '19 at 12:22