# Optimizing a strictly monotone function

I am looking for algorithms to optimize a strictly monotonic function $f$ such that $f(x) < y$

$f : [a,b] \longrightarrow [c,d] \qquad \text{where } [a,b] \subset {\mathbb N}, [c,d] \subset {\mathbb N}$
such that $\arg\max{_x} f(x) < y$

My first idea was to use a variant of binary search, pick a point $x$ in $[a,b]$ at random; if $f(x) > y$ then we eliminate $[x, b]$, and if $f(x) < y$ we eliminate $[a, x]$. We repeat this procedure until the solution is found.

Do you have any other ideas to maximize the function $f$ ?

-
Rather than picking at random, you could select the midpoint, test, elininate and repeat. –  Dave Clarke Apr 19 '12 at 11:38
... unless you know something more about $f$, then you could apply Newton's method to $f(x)-y$. –  Dave Clarke Apr 19 '12 at 11:47
Is $f$ defined on the natural numbers or on the whole interval $[a,b]$? (I can't figure out the notation $[a,b]\subset \mathbb{N}$.) –  Louis Apr 19 '12 at 12:02
If $f$ is strictly monotonic, then the maximum should be at $f(a)$ or $f(b)$... –  sdcvvc Apr 19 '12 at 13:23
@sdcvvc yes, but I want the maximum such that f(x) < y, y is a given value. –  Ghassen Hamrouni Apr 19 '12 at 13:29

Given the discrete intervals $[a,b]\subset\mathbb{N}$ and $[c,d]\subset\mathbb{N}$, we might be able to do slightly better than binary search using the midpoint without utilizing gradient descent.

Instead, we could use binary search with $x=a+\lfloor\frac{y-c}{d-c}(b-a)\rfloor$, which corresponds to the below intersection of the dotted purple line denoting $y$ and the line from $f(a)=c$ to $f(b)=d$.

The red and blue lines represent the extremes of strictly monotonic functions. When $f$ is linear, this would immediately find the closest $x$ (which is a big improvement over binary search with the midpoint). Without additional information, I think linearity is the best assumption you can make; there are as many concave functions as convex functions, as well as functions that switch.

One justification for not using gradient descent is if an array $[a,a+1,\dots,b]$ is simply mapped to another array of the same size but different range of data $[c,d]$, which is randomly chosen (and sorted).

Otherwise, you could use Newton's method as suggested by Dave Clarke or gradient descent as suggested by Raphael, which I just learned are different.

-
Can you analyze the performance of this method on an arbitrary monotone function? How worse is it than binary search in the worst case? –  Yuval Filmus Nov 29 '12 at 16:38
@YuvalFilmus, monotone functions can be quite arbitrary, so I don't know if I can analyze its average performance (other than assuming linearity), but at worst its the red line and $y=d-(b-a-1)$; I can't determine without further thought whether its still $O(\log n)$ –  Merbs Nov 29 '12 at 17:53