Rainer E. Burkard, Horst W. Hamacher, and Günter Rote:

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

Naval Research Logistics 38 (1991), 911–924, (Zbl 755.90066, MR #92h:90098), doi:10.1002/nav.3800380609


We develop an algorithm for computing upper and lower aproximations of an explicitly or implicitly given convex function defined on an interval of length T. The algorithm requires no differentiability assumptions; the error decreases quadratically with the number of iterations. To reach an absolute accuracy of ε, the number of iterations is bounded by sqrt(9DT/(8ε)), where D is the total slope increase of the function. As an application, we discuss separable convex programs.

Note: A more general treatment of the Sandwich algorithm (with different proofs) is given in the paper The convergence rate of the Sandwich algorithm for approximating convex functions by Günter Rote.

other papers about this subject