## 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
### Abstract

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(9`D``T`/(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.