Find a number for minimum sum of nth power of absolute difference in an array-CodePudding

My question is similar to this, but instead if the absolute difference is raised to a power 'c' (which will be given as input) is there an algorithm to find the answer?

For example, given A = {a1, a2,...., an} and c it should find an x such that it minimises |a1 − x|^c |a2 − x|^c ··· |an − x|^c.

If c = 1 it's the median of the sorted array and if c = 2 it's the average of the array, but I can't find connection between median and average which we can extend to any value of c.

CodePudding user response：

I assume that c is a positive integer.

If it is not an integer, then the fractional powers are hard to calculate. If it is negative, then as x goes to infinity (either way) the result goes to 0, so there is no global minimum. If it is 0, then x does not matter. So a positive integer is the only thing that makes sense.

Now each term is a convex function. The sum of convex functions is itself convex. Convex functions have the following properties. Suppose that x < y < z. If f(x) = f(z) then the global minimum is between them. If f(x) = f(y) = f(z), that's a straight line segment. And finally, if f(y) < min(f(x), f(z)) then the global minimum is between x and z.

This is sufficient for a variation on binary search.

while z - x > some tolerance:
    if z-y > y-x:
        y1 = (y   z) / 2
        if f(y1) < f(y):
            (x, y, z) = (y, y1, z)
        elif f(y1) = f(y):
            (x, y, z) = (y1, (2*y1   y)/3, y)
        else:
            (x, y, z) = (y1, y, z)
    else:
        y1 = (x   y) / 2
        if f(y1) < f(y):
            (x, y, z) = (x, y1, y)
        elif f(y1) = f(y):
            (x, y, z) = (y1, (2*y1   y)/3, y)
        else:
            (x, y, z) = (y1, y, z)

As this runs, each iteration reduces the size of the interval to at most 3/4 of what it previously was. And therefore you will narrow in on the answer.

If you special case c = 1, you can do even better. The second derivative will be defined everywhere and be a non-decreasing function. This allows you to do a binary search, but guess where in the interval the minimum is expected to be. If you land close, you know which way you're wrong, and can put a much tighter bound on it.