On the approximation of strongly convex functions by an upper or lower operator

Abstract

The aim of this paper is to find a convenient and practical method to approximate a given real-valued function of multiple variables by linear operators, which approximate all strongly convex functions from above (or from below). Our main contribution is to use this additional knowledge to derive sharp error estimates for continuously differentiable functions with Lipschitz continuous gradients. More precisely, we show that the error estimates based on such operators are always controlled by the Lipschitz constants of the gradients, the convexity parameter of the strong convexity and the error associated with using the quadratic function, see Theorems 3.1 and 3.3. Moreover, assuming the function, we want to approximate, is also strongly convex, we establish sharp upper as well as lower refined bounds for the error estimates, see Corollaries 3.2 and 3.4. As an application, we define and study a class of linear operators on an arbitrary polytope, which approximate strongly convex functions from above. Finally, we present a numerical example illustrating the proposed method.