Minimize a function

general
,
1

We are given an array A of length n
then hoe to find x which minimize the function

f(x)=|x-A1|+|x-A2|+|x-A3|+…+|x-An|

where |k| denotes the absolute value of k.

I dont find any efficient algorithm. plz help me.

2

Hi,

I don’t know how to solve this.

However, from what I feel like, there are some “good ansatz” we can have here.

I would attempt two different values for x:

The average and the median of all the values in the array.

You could even run some probability tests on the array values to see how well distributed or biased they are and then choose accordingly.

I guess this is not a bad approach for a start. But I don’t know any algorithm.

EDIT:
We can always do some maths…Right? Right.

The derivative of:

f(x) = abs(x-K) is:

x-K / abs(K-x)

So now, since the denominator can’t be 0, you need to make sure that x-K is 0 and x != K.

I believe we can take the derivative and see where its value is 0 because the function is increasing with x increasing. So the value where the derivative is 0 is a minima (???).

Following the above logic, for the N elements we need to make sure that:

x - A1 + x - A2 + x - A3 + … + x - AN = 0

So:

N*x - (sum of all array elements) = 0

x = Average of all array elements.

I’m not convinced though…

Best,

Bruno

3

It will be the median of the array.

2 Likes
4

Also look at the following for why the median minimizes the sum of absolute deviations:

1 Like