Local adaption for approximation and minimization of univariate functions

DOI10.1016/J.JCO.2016.11.005MaRDI QIDQ2396714zbMATH OpenOpenAlexFDO

Authors Sou-Cheng T. Choi, Yuhan Ding, Fred J. Hickernell, Xin Tong

Publication date 24 May 2017

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.02766

zbMATH Keywords

computational complexitynumerical experimentsadaptive algorithmsglobal minimizationfunction recoverybest function approximation

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Nonlinear programming (90C30) Algorithms for approximation of functions (65D15)

Abstract: Most commonly used emph{adaptive} algorithms for univariate real-valued function approximation and global minimization lack theoretical guarantees. Our new locally adaptive algorithms are guaranteed to provide answers that satisfy a user-specified absolute error tolerance for a cone, $mathcalC$, of non-spiky input functions in the Sobolev space $W^{2,infty}[a,b]$. Our algorithms automatically determine where to sample the function---sampling more densely where the second derivative is larger. The computational cost of our algorithm for approximating a univariate function $f$ on a bounded interval with $L^{infty}$-error no greater than $varepsilon$ is $$ as $varepsilono0$. This is the same order as that of the best function approximation algorithm for functions in $mathcalC$. The computational cost of our global minimization algorithm is of the same order and the cost can be substantially less if $f$ significantly exceeds its minimum over much of the domain. Our Guaranteed Automatic Integration Library (GAIL) contains these new algorithms. We provide numerical experiments to illustrate their superior performance.

Recommendations

• The cost of deterministic, adaptive, automatic algorithms: cones, not balls
• An adaptive univariate global optimization algorithm and its convergence rate for twice continuously differentiable functions
• An upper bound on the asymptotic complexity of global optimization of smooth univariate functions
• Average performance of a class of adaptive algorithms for global optimization
• An adaptive univariate global optimization algorithm and its convergence rate under the Wiener measure

Cites work

• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 1440908 (Why is no real title available?)
• A survey of information-based complexity
• Adaptive Multidimensional Integration Based on Rank-1 Lattices
• Automatic integration using asymptotically optimal adaptive simpson quadrature
• Guaranteed conservative fixed width confidence intervals via Monte Carlo sampling
• Introduction to Interval Analysis
• On the power of adaption
• Optimal algorithms for global optimization in case of unknown Lipschitz constant
• Reliable adaptive cubature using digital sequences
• The cost of deterministic, adaptive, automatic algorithms: cones, not balls
• The power of adaption for approximating functions with singularities
• Verification methods: rigorous results using floating-point arithmetic

Cited in

(5)

• Asymptotically tight worst case complexity bounds for initial-value problems with nonadaptive information
• The cost of deterministic, adaptive, automatic algorithms: cones, not balls
• Adaptive mesh point selection for the efficient solution of scalar IVPs
• GAIL
• Adaptive mesh selection asymptotically guarantees a prescribed local error for systems of initial value problems

Describes a project that uses

Uses Software

• Matlab
• INTLAB
• Chebfun
• BRENT

This page was built for publication: Local adaption for approximation and minimization of univariate functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396714)