0
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.