Least squares with equality constraint

Question

Say I have the following Least Squares equation with constraints and constant parameters $a_i$:

$\min(\sum(x_{i}-a_{i})^2), \sum{x_{i}}=1,x_i>0$

Basically, I am looking for the best set of $x_i$'s to minimise this function while ensuring their sum equals 1. I am not trying to model any data, so it is not a traditional use-case.

Is there an analytical solution to this problem? Or do I have to look at quadratic programming or iterative approaches? If so, any pointers? I haven't been able to work anything out myself.

I do not need a perfect solution, so some reasonable algorithmic estimate is sufficient.

Answer 1

If your vector $x$ has $n$ components, then simply set all $x_i:=\frac{1}{n}$. Then $\bar{x}=\frac{1}{n}$, each $x_i$ is equal to this mean, your sum of squares is zero (so it is minimal, because anything else would be greater than zero), and your constraints are satisfied.

And I agree with Dave that this would be a better fit for Math.SE.

Answer 2

Without the requirement that $x_i \ge 0$, you can get a closed-form expression for the optimal solution: $$x_i = a_i + \frac{1-\sum_j a_j}{n}$$

This formula arises geometrically from finding the smallest distance from $(a_1,\dots,a_n)$ to the hyperplane $\sum_i x_i=1$ or algebraically from Lagrange multipliers.

As a check, note that $$ \sum_i \left(a_i + \frac{1-\sum_j a_j}{n}\right) = \sum_i a_i + \left(1-\sum_j a_j\right) = 1, $$ as required. Furthermore, if $\sum_j a_j = 1$, the proposed formula yields $x_i=a_i$, with objective value zero.