Convex Optimization Problem - Least Squares with Linear Equality Constraint

Question

I honestly could not think of a better title, so if anyone can come up with one, please do make a change. Thanks.

Given an array of $n$ constants {${a_1, a_2, ... , a_n}$},and another constant $m$, what is the most efficient way of choosing $x_i$s such that {$x_1 + x_2 + ... + x_n = m$} and the following expression is minimized:

$(a_1 - x_1)^2 + (a_2 - x_2)^2 + ... + (a_n - x_n)^2$

It is also known that $a_1 + a_2 + ... + a_n > m$.

Answer 1

Your problem is basically:

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

The above is a Convex Optimization Problem (Equality Constrained Least Squares).

The Lagrangian is given by:

$$ L \left( x, \mu \right) = \frac{1}{2} \left\| x - a \right\|_{2}^{2} + \mu \left( \boldsymbol{1}^{T} x - m \right) $$

Looking for a stationary point:

$$ \begin{align*} \nabla L \left( x, \mu \right) & = 0 \Rightarrow x - a + \mu \boldsymbol{1} = 0 & \text{} \\ & \Rightarrow \hat{x} = a - \mu \boldsymbol{1} \end{align*} $$

Now, all needed is to have the optimal $ \mu $.

Taking $ x - a + \mu \boldsymbol{1} = 0 $ and multiply both by $ \boldsymbol{1}^{T} $ on left yields:

$$ m - \boldsymbol{1}^{T} a + \mu n \Rightarrow \mu = \frac{\boldsymbol{1}^{T} a - m}{n} $$

Plugging that above yields:

$$ \hat{x} = a - \frac{\boldsymbol{1}^{T} a - m}{n} \boldsymbol{1} $$

The result is intuitive, as this is a least squares problem, we're trying to get close as possible to $ a $.
So we take $ a $ and move form it in a perpernicular direction to the plane $ \boldsymbol{1}^{T} x = m $ until we meet it.
It means this is the closest point on the hyper plane to $ a $.

Answer 2

$f(x) = (a_1-x_1)^2 + (a_2-x_2)^2+\cdots (a_n-x_n)^2$

$g(x) = x_1+x_2+\cdots x_n-m=0$

$\nabla f = \lambda \nabla g$

$<2(x_1-a_1),2(x_2-a_2),2(x_3-a_3),\cdots,2(x_n-a_n)> = \lambda<1,1,1,\cdots , 1>$

$x_1 = \frac{\lambda}{2} + a_1$

$x_2 = \frac{\lambda}{2} + a_2$

...

$x_n = \frac{\lambda}{2} + a_n$

Substituting the value of x's in g(x) will yield

$n\frac{\lambda}{2} = m - \sum a_i$

thus $\lambda = 2\frac{(m-\sum a_i)}{n}$

Again plugging the value of this into each x will give

$x_i = a_i + \frac{(m-\sum a_i)}{n}$

with $\lambda \lt 0$