A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming.

htmlabstractWe consider maximising a concave function over a convex set by a simplerandomised algorithm. The strength of the algorithm is that it requires only approximatefunction evaluations for the concave function and a weak membership oraclefor the convex set. Under smoothness conditions on the function and the feasibleset, we show that our algorithm computes a near-optimal point in a number of operationswhich is bounded by a polynomial function of all relevant input parametersand the reciprocal of the desired precision, with high probability. As an application towhich the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron