Continuous Piecewise Linear Delta-Approximations for Bivariate and Multivariate Functions

Steffen Rebennack () and Josef Kallrath ()
Additional contact information
Steffen Rebennack: Colorado School of Mines
Josef Kallrath: University of Florida

Journal of Optimization Theory and Applications, 2015, vol. 167, issue 1, No 6, 102-117

Abstract: Abstract For functions depending on two variables, we automatically construct triangulations subject to the condition that the continuous, piecewise linear approximation, under-, or overestimation, never deviates more than a given $$\delta $$ δ -tolerance from the original function over a given domain. This tolerance is ensured by solving subproblems over each triangle to global optimality. The continuous, piecewise linear approximators, under-, and overestimators, involve shift variables at the vertices of the triangles leading to a small number of triangles while still ensuring continuity over the entire domain. For functions depending on more than two variables, we provide appropriate transformations and substitutions, which allow the use of one- or two-dimensional $$\delta $$ δ -approximators. We address the problem of error propagation when using these dimensionality reduction routines. We discuss and analyze the trade-off between one-dimensional (1D) and two-dimensional (2D) approaches, and we demonstrate the numerical behavior of our approach on nine bivariate functions for five different $$\delta $$ δ -tolerances.

Keywords: Global optimization; Nonlinear programming; Mixed-integer nonlinear programming; Nonconvex optimization; Error propagation; 90C26 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-014-0688-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:167:y:2015:i:1:d:10.1007_s10957-014-0688-2

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-014-0688-2

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().