Sandwich approximation of univariate convex functions with an application to separable convex programming
Authors:
- 1 December 1991
- journal article
- research article
- Published by Wiley in Naval Research Logistics (NRL)
- Vol. 38 (6) , 911-924
Abstract
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 magnified image , where D is the total increase in slope of h. As an application we discuss separable convex programs.Keywords
This publication has 18 references indexed in Scilit:
- Approximation of convex curves with application to the bicriterial minimum cost flow problemEuropean Journal of Operational Research, 1989
- Successive approximation in separable programming: An improved procedure for convex separable programsNaval Research Logistics Quarterly, 1986
- Sequential algorithms of optimal order global error for the uniform recovery of functions with monotone (r-1) derivativesAnalysis Mathematica, 1984
- Optimal linear approximation in project compressionIIE Transactions, 1984
- Multipoint methods for separable nonlinear networks1984
- Polygonal approximation by the minimax methodComputer Graphics and Image Processing, 1982
- A scaled reduced gradient algorithm for network flow problems with convex separable costs1981
- Secant approximation methods for convex optimization1981
- Error analysis for convex separable programs: Bounds on optimal and dual optimal solutionsJournal of Mathematical Analysis and Applications, 1980
- An algorithm for approximating convex functions by means by first degree splinesThe Computer Journal, 1971