Local adaption for approximation and minimization of univariate functions

DOI10.1016/J.JCO.2016.11.005zbMATH Open1365.65032arXiv1606.02766OpenAlexW2419260028MaRDI QIDQ2396714FDOQ2396714

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)

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.

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

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

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)

Cites Work

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

Cited In (5)

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

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)