# 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
• When you do heuristic searches like this, you normally want to bound the interval to keep the $\mathcal{O}(\log n)$ worst-case. – Veedrac May 4 '17 at 23:22