Sandwich approximation of univariate convex functions with an application to separable convex programming
Rainer E. Burkard, Horst W. Hamacher, Günter Rote · Naval Research Logistics (NRL) · 1991
Abstract 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 magnified image , where D is the total increase in slope of h . As an application we discuss separable convex programs.