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...

  • $\begingroup$ That’s precisely the purpose of the $n$-dimensional vector $\mu$. $\endgroup$ – learner Sep 11 '19 at 10:37
  • 1
    $\begingroup$ Sorry, please ignore my earlier comment- wasn't reading carefully. $\endgroup$ – Brian Borchers Sep 11 '19 at 13:55
  • $\begingroup$ Related - math.stackexchange.com/questions/2935650. $\endgroup$ – 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.

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

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.