Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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$ ?

share|improve this question
1  
Rather than picking at random, you could select the midpoint, test, elininate and repeat. –  Dave Clarke Apr 19 '12 at 11:38
2  
... 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
1  
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
3  
If $f$ is strictly monotonic, then the maximum should be at $f(a)$ or $f(b)$... –  sdcvvc Apr 19 '12 at 13:23
1  
@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
show 4 more comments

1 Answer

up vote 4 down vote accepted

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$.

possible monotonic functions

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.

share|improve this answer
1  
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.