The Optimal Statistical Median of a Convex Set of Arrays

We consider the following problem. A set r(1), r(2), ... , r(K) of vectors is given. We want to find the convex combination "z" such that the median of "z" is maximum. In the application that we have in mind, vectors are the historical return arrays of asset traded on a market, whereas the convex array contains the portfolio weights. Maximizing the median on a convex set of arrays is a continuous non-differentiable, non-concave optimization problem. The function shows many non differentiable local optima, therefore any gradient like algorithm cannot be used. Moreover it can be shown that the problem belongs to the APX-hard difficulty class. As a consequence, we are sure that no polynomial time algorithm can ever solve the model, unless P = NP. We propose a mixed integer non-linear optimization model to solve the problem, where continuous variables are the original portfolio weights and binary variables stand for the hyper-planes that must be selected to determine a local optimum. We propose an implicit enumeration algorithm, in which bounds on the objective function are calculated using continuos geometric properties of the median. Computational results are reported, which relies on the following procedure. First, we remark that local problem optima are the intersection of hyper-planes, that have to be selected from a given set. Using this property, the problem can be formulated as a mixed integer non-linear optimization model. Continuous variables are the original %portfolio weights, binary variables stand for the hyper-planes %that must be selected. Moreover, if binary variables are fixed, the problem turns out a linear programming model that can be quickly solved. We use this mixed integer formulation to develop three upper bounds to the optimal solution. Those bounds are obtained using surrogate constraints, dominating and valid inequalities, and also restricting the feasible range of the continuous variables. All bounds were implemented in a branch\&bound algorithm, that has been tested on many problem instances. We will show that the problem can be solved for K, the number of arrays, being any large number, but when T, the dimension of the arrays, is greater than some 40, then computational times are heavy.