Rainer E. Burkard, Horst W. Hamacher, and Günter Rote:
Sandwich approximation of univariate convex functions with an
to separable convex programming
Naval Research Logistics 38 (1991), 911–924, (Zbl 755.90066, MR
We develop an algorithm for computing upper and lower aproximations of
an explicitly or implicitly given convex function defined on an
of length T. The algorithm requires no differentiability assumptions;
error decreases quadratically with the number of iterations. To reach
absolute accuracy of ε, the number of iterations is bounded by
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
proofs) is given in the paper
convergence rate of the Sandwich algorithm for approximating convex
by Günter Rote.