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

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

Derivatives
Evaluation
Value function
Upper bound
Lower bounds
Approximation
Information value
Usefulness
Strategic investment

Cite this

@article{d8f262003cfc45a0b95ab705e116c278,
title = "A method for approximating univariate convex functions using only function value evaluations",
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.",
author = "A.Y.D. Siem and {den Hertog}, D. and A.L. Hoffmann",
note = "Appeared earlier as CentER DP 2007-67",
year = "2011",
doi = "10.1287/ijoc.1100.0424",
language = "English",
volume = "23",
pages = "591--604",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "4",

}

A method for approximating univariate convex functions using only function value evaluations. / Siem, A.Y.D.; den Hertog, D.; Hoffmann, A.L.

In: INFORMS Journal on Computing, Vol. 23, No. 4, 2011, p. 591-604.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - Siem, A.Y.D.

AU - den Hertog, D.

AU - Hoffmann, A.L.

N1 - Appeared earlier as CentER DP 2007-67

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1287/ijoc.1100.0424

DO - 10.1287/ijoc.1100.0424

M3 - Article

VL - 23

SP - 591

EP - 604

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 4

ER -