Is there a more efficient way to minimize this function?

Question

I have the following function, and I need to minimize it with respect to $x$ given any constant array of positive numbers $a_0, a_1, ..., a_n$.

$$\sum_{i=0}^{n}\frac{\lvert x-a_i\rvert}{a_i}$$

I recognize that this function is composed of $n + 1$ line segments, and the minimum does lie on one of their vertices, which are fairly easy to calculate. The current method I use is just computing the function's value at each vertex, and picking the smallest one.

I am wondering if there is a way of finding the vertex with the minimum value from the constants directly without bruteforcing and computing all of the values.

@CarryonSmiling If I'm correct in thinking that my current algorithm is $\mathcal{O}(n^2)$, then sure. — AlphaModder, Aug 20 '16 at 02:52
Maybe, you can use $\texttt{amoeba}$ which is a $Numerical\ Recipes\ in\ldots$ routine. It doesn't require derivative evaluations. — Felix Marin, Aug 20 '16 at 03:53

score 0 · Accepted Answer · answered Aug 20 '16 at 03:04

The key is that your function is convex and differentiable at all points except the vertices (but differentiable on the right at all points), so we start at the leftmost vertex and keep moving right while the derivative from the right is positive at that vertex), when it becomes negative we stop, then the maximum is the value at that vertex.

Some c++ code:

#include <bits/stdc++.h>
using namespace std;

const int MAX=100010; // size of the array
double A[MAX]; // the coordinates of the vertices

double abso(double x){
    if(x>0) return(x);
    return(-x);
}

int main(){
    int n; // the number of vertices
    double d=0,res=0; // the derivative from the right
    scanf("%d",&n); // read n
    for(int i=0;i<n;i++){
        scanf("%lf",&A[i]); //read the ith point.
        d+=1/A[i]; // make sure the derivative from the right of the first point is good.
    }
    sort(A,A+n);
    int p;
    for(p=0;p<n;p++){
        if(d<=0) break; // if the derivative is no longer positive we stop
        d-=2/A[p]; //adjust the derivative from the right
    }
    for(int i=0;i<n;i++){
        res+= abso(A[i]-A[p])/A[i];
    }
    printf("%.10f\n",res); // print result with 10 digit precision
}

Is there a more efficient way to minimize this function?

1 Answers1