5
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Rather than picking at random, you could select the midpoint, test, elininate and repeat. $\endgroup$
    – Dave Clarke
    Apr 19, 2012 at 11:38
  • 2
    $\begingroup$ ... unless you know something more about $f$, then you could apply Newton's method to $f(x)-y$. $\endgroup$
    – Dave Clarke
    Apr 19, 2012 at 11:47
  • 1
    $\begingroup$ 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}$.) $\endgroup$
    – Louis
    Apr 19, 2012 at 12:02
  • 3
    $\begingroup$ If $f$ is strictly monotonic, then the maximum should be at $f(a)$ or $f(b)$... $\endgroup$
    – sdcvvc
    Apr 19, 2012 at 13:23
  • 1
    $\begingroup$ @sdcvvc yes, but I want the maximum such that f(x) < y, y is a given value. $\endgroup$
    – Ghassen Hamrouni
    Apr 19, 2012 at 13:29

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Can you analyze the performance of this method on an arbitrary monotone function? How worse is it than binary search in the worst case? $\endgroup$
    – Yuval Filmus
    Nov 29, 2012 at 16:38
  • 1
    $\begingroup$ @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)$ $\endgroup$
    – Merbs
    Nov 29, 2012 at 17:53
  • $\begingroup$ When you do heuristic searches like this, you normally want to bound the interval to keep the $\mathcal{O}(\log n)$ worst-case. $\endgroup$
    – Veedrac
    May 4, 2017 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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