Heuristic methods for the optimal statistic median problem

We consider the problem of finding the convex combination of vectors for which the median is maximum. The objective function of this problem is non-concave and non-differentiable, with many local optima that can trap any subgradient algorithm. So we analyzed and tested some heuristic procedures to find optimal or near-optimal solutions. First, we introduced a variant of Random Restart, in which starting solutions are the vertices of the simplex, and we proved that small size problems are solved by this procedure. Then, we analyzed two versions of Variable Neighborhood Search that are used to explore the whole space of the feasible solutions, and we show that the continuous version is more powerful than the discrete version.