IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v38y1991i6p911-924.html
   My bibliography  Save this article

Sandwich approximation of univariate convex functions with an application to separable convex programming

Author

Listed:
  • Rainer E. Burkard
  • Horst W. Hamacher
  • Günter Rote

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 , where D is the total increase in slope of h. As an application we discuss separable convex programs.

Suggested Citation

  • Rainer E. Burkard & Horst W. Hamacher & Günter Rote, 1991. "Sandwich approximation of univariate convex functions with an application to separable convex programming," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(6), pages 911-924, December.
    • Handle: RePEc:wly:navres:v:38:y:1991:i:6:p:911-924
    DOI: 10.1002/nav.3800380609
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.3800380609
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.3800380609?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Lakshman S. Thakur, 1986. "Successive approximation in separable programming: An improved procedure for convex separable programs," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 33(2), pages 325-358, May.
    2. Fruhwirth, B. & Bukkard, R. E. & Rote, G., 1989. "Approximation of convex curves with application to the bicriterial minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 42(3), pages 326-338, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Siem, A.Y.D. & den Hertog, D. & Hoffmann, A.L., 2005. "Multivariate Convex Approximation and Least-Norm Convex Data-Smoothing," Other publications TiSEM ad31ef2c-fc29-46c1-9b8f-6, Tilburg University, School of Economics and Management.
    2. Jalili Marand, Ata & Hoseinpour, Pooya, 2024. "A congested facility location problem with strategic customers," European Journal of Operational Research, Elsevier, vol. 318(2), pages 442-456.
    3. H. W. Hamacher & S. Nickel, 1995. "Restricted planar location problems and applications," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(6), pages 967-992, September.
    4. Siem, A.Y.D. & den Hertog, D. & Hoffmann, A.L., 2008. "The effect of transformations on the approximation of univariate (convex) functions with applications to Pareto curves," European Journal of Operational Research, Elsevier, vol. 189(2), pages 347-362, September.
    5. Siem, A.Y.D. & den Hertog, D. & Hoffmann, A.L., 2007. "A Method For Approximating Univariate Convex Functions Using Only Function Value Evaluations," Other publications TiSEM a3afe119-3957-4700-a895-4, Tilburg University, School of Economics and Management.
    6. A. Y. D. Siem & D. den Hertog & A. L. Hoffmann, 2011. "A Method for Approximating Univariate Convex Functions Using Only Function Value Evaluations," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 591-604, November.
    7. Luo, Fengqiao & Mehrotra, Sanjay, 2019. "Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models," European Journal of Operational Research, Elsevier, vol. 278(1), pages 20-35.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Siem, A.Y.D. & den Hertog, D. & Hoffmann, A.L., 2008. "The effect of transformations on the approximation of univariate (convex) functions with applications to Pareto curves," European Journal of Operational Research, Elsevier, vol. 189(2), pages 347-362, September.
    2. Xie, Chi & Travis Waller, S., 2012. "Parametric search and problem decomposition for approximating Pareto-optimal paths," Transportation Research Part B: Methodological, Elsevier, vol. 46(8), pages 1043-1067.
    3. Liu, Y. & Teo, K. L. & Yang, X. Q., 1999. "Approximation methods for non-convex curves," European Journal of Operational Research, Elsevier, vol. 117(1), pages 125-135, August.
    4. Siem, A.Y.D. & den Hertog, D. & Hoffmann, A.L., 2007. "A Method For Approximating Univariate Convex Functions Using Only Function Value Evaluations," Discussion Paper 2007-67, Tilburg University, Center for Economic Research.
    5. Dung-Ying Lin & Chi Xie, 2011. "The Pareto-optimal Solution Set of the Equilibrium Network Design Problem with Multiple Commensurate Objectives," Networks and Spatial Economics, Springer, vol. 11(4), pages 727-751, December.
    6. A. Y. D. Siem & D. den Hertog & A. L. Hoffmann, 2011. "A Method for Approximating Univariate Convex Functions Using Only Function Value Evaluations," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 591-604, November.
    7. Quariguasi Frota Neto, J. & Walther, G. & Bloemhof, J. & van Nunen, J.A.E.E. & Spengler, T., 2009. "A methodology for assessing eco-efficiency in logistics networks," European Journal of Operational Research, Elsevier, vol. 193(3), pages 670-682, March.
    8. Safer, Hershel M. & Orlin, James B., 1953-, 1995. "Fast approximation schemes for multi-criteria combinatorial optimization," Working papers 3756-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    9. Hamacher, Horst W. & Pedersen, Christian Roed & Ruzika, Stefan, 2007. "Multiple objective minimum cost flow problems: A review," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1404-1422, February.
    10. Siem, A.Y.D. & den Hertog, D. & Hoffmann, A.L., 2007. "A Method For Approximating Univariate Convex Functions Using Only Function Value Evaluations," Other publications TiSEM a3afe119-3957-4700-a895-4, Tilburg University, School of Economics and Management.
    11. Siem, A.Y.D. & den Hertog, D. & Hoffmann, A.L., 2005. "Multivariate Convex Approximation and Least-Norm Convex Data-Smoothing," Discussion Paper 2005-132, Tilburg University, Center for Economic Research.
    12. Rasmus Bokrantz & Anders Forsgren, 2013. "An Algorithm for Approximating Convex Pareto Surfaces Based on Dual Techniques," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 377-393, May.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:38:y:1991:i:6:p:911-924. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.