Premium
Sandwich approximation of univariate convex functions with an application to separable convex programming
Author(s) -
Burkard Rainer E.,
Hamacher Horst W.,
Rote Günter
Publication year - 1991
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.3800380609
Subject(s) - mathematics , quadratic growth , separable space , univariate , differentiable function , bounded function , convex analysis , regular polygon , subderivative , convex function , proper convex function , function (biology) , convex combination , logarithmically convex function , convex optimization , combinatorics , mathematical analysis , multivariate statistics , statistics , geometry , evolutionary biology , biology
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, where D is the total increase in slope of h . As an application we discuss separable convex programs.