3
$\begingroup$

I need to minimize the following function:

$$f(x)= \sum_{i=1}^{i=n} \sqrt{(x-a_i)^2+b_i}.$$

where $a_i>0$ and $b_i>0$ for every $i \in \{1,\ldots, n\}$.

Thank you for your help.

  • 0
    Presumably you are varying $x$ for your minimization. Where are you stuck? Can you minimize $\sqrt {(x-a)^2+b}$?2012-04-19
  • 0
    If the sum were inside the radical it would be just the average of $a_1,\ldots,a_n$. I think it's a much messier problem than that.2012-04-19
  • 0
    Yes, I vary $x$. I think that we can minimize $\sqrt{(x-a)^2+b}$ if we set $x=a$. But here I have $2n$ parameters ($a_i$ and $b_i$), so it not clear for me how I can do it.2012-04-19
  • 0
    Are all $b_i \ge 0$?2012-04-19
  • 0
    You are looking for a computation method or a closed formula? The closed formula for the general case seem hard to find, but you can use bisection on $f'(x)$, using the fact that the function is convex (or you can use trisection method, that should be numerical more stable and faster).2012-04-19
  • 0
    Aryabhata: Yes. I edited my question.2012-04-19
  • 0
    carlop: I need a closed formula. Yes, it seems to be hard to find.2012-04-19

1 Answers 1

3

If $b_i=0$, $x$ is a median of $a_1,\dots,a_n$ (minimizer of the sum of distances). If all $b_i$ are equal and $b_i$ tends to infinity, $x$ converges towards the mean of $a_1,\dots,a_n$ (minimizer of the sum of squared distances).

However I don't think there is a formula that describes the general case. You'll have to solve for the equation $$0=f'(x)=\sum_{i=1}^n \frac{x-a_i}{\sqrt{(x-a_i)^2+b_i}}$$ (when all $b_i\ne 0$, $f$ is differentiable at $x$)