# Convex Optimization Problem - Least Squares with Linear Equality Constraint

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

• Lagrange multipliers is a fairly standard approach. Should get you to a convenient closed form. – lulu Sep 27 '17 at 11:07

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

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