Abstract
The Sandwich algorithm approximates a convex function of one variable over an interval by evaluating the function and its derivative at a sequence of points. The connection of the obtained points is a piecewise linear upper approximation, and the tangents yield a piecewise linear lower approximation. Similarly, a planar convex figure can be approximated by convex polygons.
Different versions of the Sandwich algorithm use different rules for selecting the next evaluation point. We consider four natural rules (interval bisection, slope bisection, maximum error rule, and chord rule) and show that the global approximation error withn evaluation points decreases by the order ofO(1/n 2), which is optimal.
By special examples we show that the actual performance of the four rules can be very different from each other, and we report computational experiments which compare the performance of the rules for particular functions.
Zusammenfassung
Der Sandwich-Algorithmus approximiert eine konvexe Funktion einer Variablen über einem Intervall, indem er die Funktion und ihre Ableitung an einer Folge von Stützstellen ausrechnet. Die Verbindung der Punkte ergibt eine stückweise lineare obere Approximation, und die Tangenten liefern eine stückweise lineare untere Approximation. Auf ähnliche Art kann man einen konvexen Bereich der Ebene durch konvexe Polygone approximieren.
Verschiedene Versionen des Sandwich-Algorithmus unterscheiden sich durch die Regel, nach der sie die nächste Stützstelle bestimmen. Wir zeigen für vier natürliche Regeln (Intervallhalbierung, Steigungshalbierung, maximaler-Fehler-Regel und Sehnenregel), daß der globale Approximationsfehler mit der Anzahln der Stützstellen mit der bestmöglichen OrdnungO(1/n 2) abnimmt.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aneja, Y. P., Nair, K. P. K.: Bicriteria transportation problem. Management Science25, 73–78 (1979).
Archimedes: Quadratura parabolae, In: Heiberg, J. L. (ed.) Archimedis opera omnia, vol. II, Leipzig: B. G. Teubner 1913, pp. 261–315.
Vladimir Igorevič Arnol'd: Mathematical methods of classical mechanics. New York, Berlin, Heidelberg: Springer 1978.
Boyer, C. B.: A history of mathematics. New York, London, Sidney: Wiley 1968.
Burkard, R. E., Hamacher, H., Rote, G.: Sandwich approximation of univariate convex functions with an application to separable convex programming. Naval Research Logistics38, 911–924 (1992).
Cantoni, A.: Optimal curve fitting with piecewise linear functions. IEEE Transactions on ComputersC-20, 59–67 (1971).
Cole, R., Chee Keng Yap: Shape from probing. J. Algorithms8, 19–38 (1987).
Edelsbrunner, H.: Algorithms in combinatorial geometry. Berlin, Heidelberg, New York, Tokyo: Springer 1987.
Fleischer, R., Mehlhorn, K., Rote, G., Welzl, E., Yap, C.: On simultaneous inner and outer approximation of shapes. In: Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, California, June 6–8, 1990, Association for Computing Machinery, pp. 216–224.
Fleischer, R., Mehlhorn, K., Rote, G., Welzl, E., Yap, C.: Simultaneous inner and outer approximation of shapes. To appear in Algorithmica (1992).
Freeman, H., Shapiro, R.: Determining the minimum-area encasing rectangle for an arbitrary closed curve. Communications ACM18, 409–413 (1975).
Fruhwirth, B.: Approximation of convex functions and multicriteria linear programs, dissertation. Technische Universität Graz, Institut für Mathematik, August 1991.
Fruhwirth, B., Burkard, R. E., Rote, G.: Approximation of convex curves with application to the bicriteria minimum cost flow problem. European J. Operational Research42, 326–338 (1989).
Gruber, P. M.: Approximation of convex bodies. In: Gruber, P. M., Wills, J. M. (eds.) Convexity and its applications. Basel, Boston: Birkhäuser 1983, pp. 131–162.
Gruber, P. M.: Asymptotic estimates for best and stepwise approximation of convex bodies I, manuscript. Technische Universität Wien, Abteilung für Analysis, 1991.
Gruber, P. M.: Aspects of approximation of convex bodies. In: Gruber, P. M., Wills, J. M. (eds.) Handbook of convex geometry. Amsterdam, New York, Oxford, Tokio: North-Holland 1992 (to appear).
Gruber, P. M., Kenderov, P.: Approximation of convex bodies by polytopes. Rendiconti Circ. Mat. Palermo, Serie II31, 195–225 (1982).
Imai, H., Iri, M.: An optimal algorithm for approximating a piecewise linear function. J. Information Processing9, 159–162 (1986).
Imai, H., Iri, M.: Polygonal approximations of a curve—formulations and algorithms. In: Toussaint, G. T. (ed.) Computational morphology—a computational geometric approach to the analysis of form. Amsterdam, New York: North-Holland 1988, pp. 71–86.
Do Ba Khang, Okitugu Fujiwara: A new algorithm to find all vertices of a polytope. Oper. Res. Lett.8, 261–264 (1989).
Kurozumi, Y., Davis, W. A.: Polygonal approximation by the minimax method. Computer Graphics and Image Processing19, 248–264 (1982).
Lew, J. S., Quarles, D. A.: Optimal inscribed polygons in convex curves. Amer. Math. Monthly96, 886–902 (1989).
Martelli, G.: Jemmy Twitcher—A life of the fourth Earl of Sandwich, 1718–1792. London: Jonathan Cape 1962.
McClure, D. E., Vitale, R. A.: Polygonal approximation of plane convex bodies. J. Math. Anal. Appl.51, 326–358 (1975).
Müller, J.: Step by step approximation of plane convex bodies. Archiv der Mathematik57 (1991).
Arkadiî Semenovič Nemirovsky and David Borisovič Yudin: Složnost' zadač i effektivnost' metodov optimizatsii, Moscow: Nauka 1979. English translation: Problem complexity and method efficiency in optimization. Chichester, New York, Brisbane, Toronto, Singapore: Wiley 1983.
Noltemeier, H.: Sensitivitätsanalyse bei diskreten linearen Optimierungsproblemen. Berlin, Heidelberg, New York: Springer 1970 (Lecture Notes in Operations Research and Mathematical Systems 30).
Novak, E.: Deterministic and stochastic error bounds in numerical analysis. Berlin, Heidelberg, New York, London, Paris, Tokyo: Springer 1988 (Lecture Notes in Mathematics 1349).
Preparata, F. P., Shamos, M. I.: Computational geometry: an introduction. New York: Springer 1985.
Ramer U.: An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing1, 244–256 (1972).
Rockafellar, R. T.: Convex analysis. Princeton: Princeton University Press 1970.
Ruhe G.: Flüsse in Netzwerken—Komplexität und Algorithmen, Dissertation B. Technische Hochschule Leipzig, Sektion Mathematik und Informatik, 1988.
Ruhe, G.: Algorithmic aspects of flows in newtorks. Dordrecht: Kluwer 1991.
Ruhe, G., Fruhwirth, B.: ε-optimality for bicriteria problems and its application to minimum cost flows. Computing44, 21–34 (1990).
Skeina, S. S.: Problems in geometric probing. Algorithmica4, 599–605 (1989).
Sonnevend, G.: An optimal sequential algorithm for the uniform approximation of convex functions on [0, 1]2. Appl. Math. Optim.10, 127–142 (1983).
Sonnevend, G.: Sequential algorithms of optimal order global error for the uniform recovery of functions with monotone (r−1) derivatives. Analysis Mathematica10, 311–335 (1984).
Traub, J. F., Wasilkowski, G. W., Woźniakowski, H.: Information-based complexity. New York, London, Toronto, Sidney, San Francisco: Academic Press 1988.
Traub, J. F., Woźniakowski, H.: A general theory of optimal algorithms. New York, London, Toronto, Sidney, San Francisco: Academic Press 1980.
Author information
Authors and Affiliations
Additional information
This work was partially supported by the Fonds zur Förderung der wissenschaftlichen Forschung, Project P7486-Phy.
Rights and permissions
About this article
Cite this article
Rote, G. The convergence rate of the sandwich algorithm for approximating convex functions. Computing 48, 337–361 (1992). https://doi.org/10.1007/BF02238642
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02238642
AMS 1991 Mathematics Subject Classifications
CR Categories and Subject Descriptors (1987 version)
- F.2.1 [Analysis of algorithms and problem complexity]: Numerical algorithms and problems
- G.1.2. [Numerical analysis]: Approximation—spline and piecewise polynomial approximation
- I.3.5. [Computer graphics]: Computational geometry—geometric algorithms