Recently I have been working on an optimization problem which in essence is to find the minimal value ofF(x) = f(x) + max(g_1(x), g_2(x), g_3(x), ...g_n(x))under the constraints thatx >= 0,Ax <= b,where x, b vector, A matrix. f, g_1 ..., g_n are linear functions.In other words, this is a classic linear programming problem whose object function has been added with a component that is the max of a group of linear functions.In my particular project, the dimension of x is around 50 and n, the number of linear functions inside the max, is around 50 as well.What will be a good algorithm/method to tackle the problem? Its not linear but I reckon using something fminsearch of matlab will lose too much of the advantage that most of components being linear. Thank you very much!

Actually, this is a very easy problem if you introduce one auxiliary variable "alpha":min_{x, alpha} f(x) + alphas.t.x >= 0Ax <= bg_i(x) <= alpha, i = 1,...,nNow you have one additional free variable, and the resulting problem is still an LP which you can solve with any LP solver.