Sandwich approximation of univariate convex functions with an application to separable convex programming

In this article an algorithm for computing upper and lower approximations of a (implicitly or explicitly) given convex function h defined on an interval of length T is developed. The approximations can be obtained under weak assumptions on h (in particular, no differentiability), and the error decreases quadratically with the number of iterations. To reach an absolute accuracy of the number of iterations is bounded by , where D is the total increase in slope of h. As an application we discuss separable convex programs.