Is discrete quasiconvexity just as good as discrete convexity?

Question

(I will frame the discussion below in terms of concavity because it suits the examples I have on hand, but the same arguments apply to convexity, too.)

Consider a function $p(h)$ defined for $h$ on a finite set of integers $\{1, \dots, n\}$. We want to maximize $p$.

Discrete concavity

$p$ is called concave if the first finite differences are decreasing. That is, $p(h)$ is concave iff

$$p(h+1) - p(h) \leq p(h) - p(h-1), \quad \forall h \in \{2, \dots, n-1\}$$

An example of a discretely concave function is shown below.

In general, maximizing an arbitrary $p(h)$ is $\mathcal{O}(n)$ because you have to try all the indices. However, concavity means that it suffices to find the first index such that the subsequent finite difference is nonpositive (or take $h^* =n$ if all finite differences are positive). This reduces the maximization problem to the following search problem:

(SP) Find the first nonpositive entry of the list $S = \{ p(2) - p(1), p(3) - p(2), \dots, p(n) - p(n-1)\}$.

Since the first $h^*$ entries of the list are nonpositive and the remaining entries of the list are negative, this search can be completed in $\mathcal{O}(\log n)$ time using binary search.

(To formalize the nature of the search, define the list $T$ where

• $T_i = 0$ if both $S_i$ and $S_{i+1}$ are positive,
• $T_i = 1$ if $S_i $ is positive and $ S_{i+1}$ is nonpositive, and
• $T_i = 2$ if both $S_i$ and $S_{i+1}$ are nonpositive

for $i = 1 , \dots, n-1$. The list $T$ sorted in ascending order, so we can use binary search to find the first value $h$ for which $T_h = 1$, or take $h=n$ if all $T_i = 0$, or $h=1$ if all $T_i = 2$.)

Discrete quasiconcavity

I made up this term, but it is a natural marriage of discrete concavity and continuous quasiconcavity.

$p$ is called discretely quasiconcave if, among the two endpoints of a segment, the one with the lowest function value provides a lower bound for the value of the function on the segment (this follows the definition of quasiconvexity on Wikipedia). That is,

$$p(h) \geq \min\{p(a), p(b) \}, \quad\forall h: a\leq h \leq b$$

where $a, b, h \in \{1, \dots, n\}$.

An example of a discretely concave function is shown below.

While the property decreasing finite differences does not necessarily hold for discrete quasiconcave functions, it appears to me from the graph above that the sign of the finite differences goes from positive to nonpositive only once--at the optimum (claim 1). This means that we can still use the search problem (SP) to find the maximum of a discrete quasiconcave problem in $\mathcal{O}(\log n)$ time using the binary search procedure (claim 2).

1. Is claim 1 true? Is there an easy way to prove it?

   My intuition is that just as a discretely concave function can be associated with a continuous concave function $f(h)$ (e.g. a polynomial) that fits its points, the same should regarding associating a continuous quasiconcave function with discrete quasiconcave functions.

   Moreover, by creating an order-preserving mapping $m(h)$ between the indices $h$ of a quasiconcave function and the real numbers, we could "slide the indices around" until $f(m(h))$ is in fact concave. This "shows" that discrete quasiconcave functions are just discrete concave functions under a certain monotone transformation of the domain.

   (Actually, I guess this argument would let you turn any continuous quasiconcave function into a concave function, too, but the nature of the transformation is not obvious.)

2. Is claim 2 true? Has my manipulation of the lists $S$ and $T$ compromised the $\mathcal{O}(\log n)$ search time?

3. Has anyone pointed this out before? (I assume so.)

Answer 1

The answer is yes. The easiest way to see that claims 1 and 2 are true is to start with binary search, then apply it to the find-max operation in question.

Find-1 binary search

In the abstract, a binary search routine solves the problem of finding the first 1 in an $n$-vector $x$ of 0s and 1s when we are promised that the vector consists of some number of 0s followed by some number of 1s:

 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
                       ^

To solve this problem, we need only guess an index $i$ and check if $(x_{i-1}, x_i)$ matches the pattern $(0, 1)$. (It is easy to figure out how to handle the boundary case $i=1$.) This check can be done in $O(1)$ time.

In binary search, we start by guessing $i = \lfloor n/ 2 \rfloor$, inspect $(x_{i-1}, x_i)$, and return $i$ if it matches, or else we update the lower or upper bound to $i$ according to whether $(x_{i-1}, x_i)$ is $(0, 0)$ or $(1, 1)$, then call binary search again on this smaller slice of the vector. Since each nonterminal iteration reduces the number of candidate indexes by a factor of two, the most iterations possible is $O(\log_2 n)$.

Find-key binary search

Now, consider the usual "application" of binary search to the problem of finding a certain key $v$ in a sorted list $y$. We can reduce this to the find-1 problem by "marking" each entry $y_i$ as a $0$ if $y_i < v$ and $1$ if $y_i \geq v$. Suppose $v = 5$:

y: 0 1 1 2 3 3 3 4 4 4 4 5 5 6 6 6 6 7 7 7 7 7 7 8 9 9 9 9 9
x: 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
                         ^

I say "marking," but the important thing to note is that there is no need to actually preprocess the vector as shown above (which would cost $O(n)$ time). Instead, as we perform binary search, we can just inline the check $y_i < v$ by computing $(x_{i-1}, x_i) = (1[y_{i-1} \geq v], 1[y_{i} \geq v])$. (Here $1[\cdot]$ is the so-called "indicator function," which returns 1 if the statement is true and zero otherwise.) So the computation time for "find-key" binary search is still $O(\log n)$.

Find-max binary search

Now, consider the OP's question, which is to find the maximum key $w$ in a list $z$ that is increasing up to some point, and then decreasing thereafter. (OP's claim 1 is a direct result of this observation.) In this case, we can again reduce the problem to find-1 by "marking" each index in the correct way. We know that the target index, and all indices after it, satisfy $z_i \geq z_{i+1}$, and that all indices before the target index satisfy $z_{i-1} < z_i$. So again, we can mark the entries of $z$ as 0 or 1 according to this condition and apply binary search.

z: 0 1 1 2 3 4 4 5 6 6 6 7 7 7 5 5 5 4 4 4 4 4 4 3 2 1 0 0 0 
x: 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
                         ^

Now our "lazy evaluator" is $(x_{i-1}, x_i) = (1[z_{i-1} \geq z_i], 1[z_{i} \geq z_{i+1}])$. Now, this will require inspecting 3 indices at each iteration rather than the 2 indices from the previous two search problems. But this 3 is constant in the problem size, so (to use a bit of sloppy notation) the only effect it has on the overall computational complexity is to take us from $O(2 \log n)$ to $O( 3 \log n)$, which of course are both just $O(\log n)$ in the end. This establishes the OP's claim 2.

(Again, the way to handle the edge cases $i=1$ and $i=n$ is not hard to figure out.)

Generic binary search

If you have followed the discussion above, then it is clear that binary search is an $O(\log n)$ for any search problem in which

• the input data is a vector $z$,
• there is a transformation that converts $z$ to $x$, where $x_i = 0$ for indices before the target value and $x_i = 1$ for indices at and after the target value, and
• an arbitrary entry of $x_i$ can be computed in unit time.