SANDWICH APPROXIMATION OF UNIVARIATE CONVEX-FUNCTIONS WITH AN APPLICATION TO SEPARABLE CONVEX-PROGRAMMING

In this article an algorithm for computing upper and lower epsilon-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 epsilon the number of iterations is bounded by square-root 9DT/8-epsilon, where D is the total increase in slope of h. As an application we discuss separable convex programs.