<p>I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling range. If it has no minimum in the sampling range it is monotonic. The derivatives of the first and of the second order exist in any point in the sampling range and are continuous as well as the function itself. The algorithm <strong>must take the minimum number of points</strong> of the objective function and allow computing its derivative in any point in the sampling range with prescribed accuracy (number of precise digits of the derivative). Probably such an algorithm is already developed and well-tested. Please help me to find it. The algorithm is supposed to be implemented in the <a href="http://www.wolfram.com/mathematica/" rel="nofollow">Wolfram <em>Mathematica</em></a> system.</p>

CC BY-SA 3.0
2012-05-25T19:12:55.400Z
what sort of query complexity are you expecting for your algorithm? A function defined on $1, ... , n$ that outputs $f_k(k) = 0$ and $f_k(i) = 1$ (if $i \neq k$) would satisfy your condition. Note that knowing the derivative of this function requires solving unordered search. Or would this count as having a 'break'? If you want, we can smooth this function without changing its behavior to be continuous in the calculus sense.
Artem Kaznatcheev
CC BY-SA 3.0
2012-05-26T04:21:45.377Z
@Artem The objective function is a real-valued continuous function in the calculus sense.
Alexey Popkov
CC BY-SA 3.0
2012-05-26T23:05:32.397Z
Such problems are studied in Computable Analysis, see the book by Pour-El and Richards with the same title, or by Ker-I Ko, Computability and Complexity in Analysis. Without any further assumptions your problem is not solvable at all. There is a monotone computable $C^1$ function such that its derivative is not computable. On the other hand, every computable $C^2$ has a computable derivative. This model assumes that you have oracle access to the given function and get approximations of any desired accuracy.
Markus Bläser
CC BY-SA 3.0
2012-05-27T06:31:00.957Z
@Markus Updated the question. The derivatives of the first and of the second order exist in any point in the sampling range.
Alexey Popkov
CC BY-SA 3.0
2012-05-27T18:50:44.743Z
What does “the function has no breaks” mean?
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-28T03:59:47.113Z
@Tsuyoshi I meant that the function is continuous. I updated the question with more clear description (I hope).
Alexey Popkov
CC BY-SA 3.0
2012-05-28T18:54:00.087Z
The subbranch of computable analysis that deals with minimizing the number of function evaluation/queries is called "information-based complexity", see http://www.ibc-research.org/ for some more pointers.
Markus Bläser
<ds.algorithms><approximation-algorithms><na.numerical-analysis>
Efficiently approximating derivative of a well-behaved function
Alexey Popkov
# Efficiently approximating derivative of a well-behaved function

(Asked by: username_0 on 2012-05-24)

I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling range. If it has no minimum in the sampling range it is monotonic. The derivatives of the first and of the second order exist in any point in the sampling range and are continuous as well as the function itself. The algorithm **must take the minimum number of points** of the objective function and allow computing its derivative in any point in the sampling range with prescribed accuracy (number of precise digits of the derivative). Probably such an algorithm is already developed and well-tested. Please help me to find it. The algorithm is supposed to be implemented in the [Wolfram *Mathematica*](http://www.wolfram.com/mathematica/) system.

**Tags:** ds.algorithms, approximation-algorithms, na.numerical-analysis

> **Comments:**
> **username_1**: what sort of query complexity are you expecting for your algorithm? A function defined on $1, ... , n$ that outputs $f_k(k) = 0$ and $f_k(i) = 1$ (if $i \neq k$) would satisfy your condition. Note that knowing the derivative of this function requires solving unordered search. Or would this count as having a 'break'? If you want, we can smooth this function without changing its behavior to be continuous in the calculus sense.  
> **username_0**: @Artem The objective function is a real-valued continuous function in the calculus sense.  
> **username_2**: Such problems are studied in Computable Analysis, see the book by Pour-El and Richards with the same title, or by Ker-I Ko, Computability and Complexity in Analysis. Without any further assumptions your problem is not solvable at all. There is a monotone computable $C^1$ function such that its derivative is not computable. On the other hand, every computable $C^2$ has a computable derivative. This model assumes that you have oracle access to the given function and get approximations of any desired accuracy.  
> **username_0**: @Markus Updated the question. The derivatives of the first and of the second order exist in any point in the sampling range.  
> **username_3**: What does “the function has no breaks” mean?  
> **username_0**: @Tsuyoshi I meant that the function is continuous. I updated the question with more clear description (I hope).  
> **username_2**: The subbranch of computable analysis that deals with minimizing the number of function evaluation/queries is called "information-based complexity", see http://www.ibc-research.org/ for some more pointers.  

---

## 0 answers

