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(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.