Solve Linear Least Squares Problem with Unit Simplex Constraint

$$ \min_x ||Ax - b||_2\; \;\text{given }x \geq 0\;\;\text{and}\;\;\textbf{1}^Tx = 1 $$ I am trying to do the above optimization, I was using common Quadratic programming libraries but their speed is too less. I believe this problem needs much less general optimization routine. I was able to find non-negative least squares optimizations but they didn't offer any linear constrains. I read in few articles online that the dimensionality of the problem can be reduces by considering $x_n = 1- \sum_{i = 0}^{n-1}x_i$, and can be optimized using non-negative least squares optimization (shouldn't we in such cases constrain $\sum x_i$ to be less than 1 ?)

Thanks :)

Edit: I am really sorry, I have changed the > to >= condition.

Solution 1:

The problem is given by:

$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & x \succeq 0 \\ & \quad & \boldsymbol{1}^{T} x = 1 \end{alignat*} $$

Which I solved in my answer to How to Project onto the Unit Simplex as Intersection of Two Sets (Optimizing a Convex Function)?

I tried to write code in order to extend what I did there.
So I wrote a MATLAB Code which is accessible in my StackExchange Mathematics Q2935650 GitHub Repository.

The solvers I implemented / used are as following:

1. CVX as a reference.
2. Projected Gradient Descent with Projection onto the Unit Simplex as I implemented in Orthogonal Projection onto the Unit Simplex.
3. Projected Gradient Descent with Projection onto the Unit Simplex implemented as Alternating Projections for the projection of the intersection of 2 convex sets. See Projections onto Convex Sets and How to Project onto the Unit Simplex as Intersection of Two Sets (Optimizing a Convex Function).
4. Conditional Gradient Method (Frank Wolfe Algorithm).

The results are given by:

Timing for handling your case of $ A \in \mathbb{R}^{1500 \times 500} $ is less than a second in either of the methods I implemented.

The Frank Wolfe method is simple for this case. Indeed the Set is compact hence convergence is guaranteed. Since the convex hull of the Unit Simplex is given by Standard Basis the optimization is simple:

$$ \arg \min_{s \in \Delta} \nabla f \left( x \right)^{T} s = \arg \min_{i} {\left( \nabla f \left( x \right) \right)}_{i} $$

Where $ f \left( x \right) = \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} $ and $ \Delta = \left\{ x \mid \boldsymbol{1}^{T} x = 1, \, x \succeq 0 \right\} $ is the Unit Simplex Set.
So the solution is basically the element of the gradient with the minimal value.

This method becomes really simple and very fast for your case.

All methods could be even faster by:

• Implement acceleration for the Gradient based methods (Have a look on what I did on How to Solve Linear Least Squares Problem with Box Constraints).
• Adaptive Step Size for Frank Wolfe method (Line search should work nicely).