Approximation in p-Norm of Univariate Concave Functions

We derive worst‐case bounds, with respect to the L ^p norm, on the error achieved by algorithms aimed at approximating a concave function of a single variable, through the evaluation of the function and its subgradient at a fixed number of points to be determined. We prove that, for p larger than 1, adaptive algorithms outperform passive ones. Next, for the uniform norm, we propose an improvement of the Sandwich algorithm, based on a dynamic programming formulation of the problem.