Approximation in p-Norm of Univariate Concave Functions

J. Guérin, P. Marcotte and G. Savard ()
Additional contact information
J. Guérin: École Polytechnique de Montréal
P. Marcotte: Université de Montréal
G. Savard: École Polytechnique de Montréal

Journal of Optimization Theory and Applications, 2014, vol. 161, issue 2, No 9, 490-505

Abstract: Abstract We derive worst-case bounds, with respect to the L p norm, on the error achieved by algorithms aimed at approximating a concave function of a single variable, through the evaluation of the function and its subgradient at a fixed number of points to be determined. We prove that, for p larger than 1, adaptive algorithms outperform passive ones. Next, for the uniform norm, we propose an improvement of the Sandwich algorithm, based on a dynamic programming formulation of the problem.

Keywords: Approximation; Adaptive algorithm; Dynamic programming (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-013-0410-9 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:161:y:2014:i:2:d:10.1007_s10957-013-0410-9

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

DOI: 10.1007/s10957-013-0410-9

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