Continuous Piecewise Linear Delta-Approximations for Univariate Functions: Computing Minimal Breakpoint Systems

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 2, No 10, 617-643

Abstract: Abstract For univariate functions, we compute optimal breakpoint systems subject to the condition that the piecewise linear approximator, under-, and over-estimator never deviate more than a given $$\delta $$ δ -tolerance from the original function over a given finite interval. The linear approximators, under-, and over-estimators involve shift variables at the breakpoints allowing for the computation of an optimal piecewise linear, continuous approximator, under-, and over-estimator. We develop three non-convex optimization models: two yield the minimal number of breakpoints, and another in which, for a fixed number of breakpoints, the breakpoints are placed such that the maximal deviation is minimized. Alternatively, we use two heuristics which compute the breakpoints subsequently, solving small non-convex problems. We present computational results for 10 univariate functions. Our approach computes breakpoint systems with up to one order of magnitude less breakpoints compared to an equidistant approach.

Keywords: Global optimization; Nonlinear programming; Mixed-integer nonlinear programming; Non-convex optimization; 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 (13)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-014-0687-3 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:2:d:10.1007_s10957-014-0687-3

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

DOI: 10.1007/s10957-014-0687-3

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 ().