A method for approximating univariate convex functions using only function value evaluations

A.Y.D. Siem, D. den Hertog, A.L. Hoffmann

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

Abstract

In this paper, piecewise-linear upper and lower bounds for univariate convex functions are derived that are only based on function value information. These upper and lower bounds can be used to approximate univariate convex functions. Furthermore, new sandwich algorithms are proposed that iteratively add new input data points in a systematic way until a desired accuracy of the approximation is obtained. We show that our new algorithms that use only function value evaluations converge quadratically under certain conditions on the derivatives. Under other conditions, linear convergence can be shown. Some numerical examples that illustrate the usefulness of the algorithm, including a strategic investment model, are given.
Original languageEnglish
Pages (from-to)591-604
JournalINFORMS Journal on Computing
Volume23
Issue number4
DOIs
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'A method for approximating univariate convex functions using only function value evaluations'. Together they form a unique fingerprint.

Cite this