Optimizing Unimodal Functions

Introduction

In competitive programming, we are often asked to find the minimum or maximum value we can attain under some conditions. More specifically, we are often asked to formulate some function $f(x)$, and find the maximum or minimum value of $f(x)$.

If our function happens to be unimodal, we can use either ternary search or binary search to find the mode of our function efficiently.

Definitions

A function is unimodal if one of the following conditions holds:

1. The function strictly increases first, then reaches a maximum, then strictly decreases.
2. The function strictly decreases first, then reaches a minimum, then strictly increases.

Let's assume that we want to find the local minimum of our function. Then, a function is convex if consecutive differences are non-decreasing. In calculus terms, if the derivative of the function is non-decreasing, the function is convex.

Note that this implies that a convex function is also a unimodal function.

Ternary Search

For now, let's assume that we want to find the minimum of our function, and that our function is unimodal. This means that the second condition holds, meaning our function strictly decreases first, reaches its minimum, then strictly increases.

The idea behind ternary search is somewhat similar to binary search. At every step of our algorithm, we want to cut out some large portion of our search space from being considered.

Let's consider two points $m_1$ and $m_2$, where $l < m_1 < m_2 < r$. Here, $l$ and $r$ are the endpoints of our current search space. This ends up dividing our search space into three sections.

Now, we just do a bit of casework to see if we can eliminate any sections.

1. $f(m_1) > f(m_2)$ means that we can eliminate $[l, m_1)$
2. $f(m_1) < f(m_2)$ means that we can eliminate $(m_2, r]$
3. $f(m_1) = f(m_2)$ means that we can eliminate $[l, m_1)$ and $(m_2, r]$

Typically, we treat case 3 as being analogous to cases 1 and 2.

As a mini-proof for why the way we handle case 1 is correct, consider the following:

If $f(m_1) > f(m_2)$, then we know the following two facts:

• $f(m_1)$ is not the minimum
• $f(m_1)$ cannot be on the strictly increasing side of the function

Regarding the second point, if $f(m_1) > f(m_2)$ and $m_1$ was on the strictly increasing side of the function, that would imply $m_1 > m_2$, which is a contradiction.

Thus, we can conclude that $m_1$ remains on the strictly decreasing section of our function. Because of this, we can conclude that our minimum will not be in the range $[l, m_1)$, so we can eliminate this section from our search space.

Now that we know how to strategically remove sections of our search space, the question remains on how to choose the best values of $m_1$ and $m_2$. The optimal way is to divide our search space into thirds, so we have:

Implementation

The time complexity of ternary search takes on the following recurrence:

Per the Master theorem, this is $\mathcal{O}(\log{n})$ if we are working with integers.

If we are ternary searching with a fixed error margin $\epsilon$, the time complexity becomes $\mathcal{O}\left( \log\left( \frac{n}{\epsilon} \right) \right)$.

Copy
template <typename F> double find_min(double l, double r, double eps, const F &f) {
	while (r - l > eps) {
		double m1 = l + (r - l) / 3;
		double m2 = r - (r - l) / 3;
		f(m1) > f(m2) ? l = m1 : r = m2;
	}

	return l;
}

If our function only takes in integers, then our implementation looks a little different.

Copy
template <typename F> int find_min(int l, int r, const F &f) {
	while (r - l > 3) {
		int m1 = l + (r - l) / 3;
		int m2 = r - (r - l) / 3;
		f(m1) > f(m2) ? l = m1 : r = m2;
	}

	int res = l;
	for (int i = l + 1; i <= r; i++) {
		if (f(i) < f(res)) { res = i; }
	}

	return res;
}

Binary Search

Actually, in the case of our function only taking in integers, binary search is often a better option, as it's shorter and requires less calls to our function $f(x)$.

However, if we are working with floating points, binary search may be a bit more problematic because of loss of precision. For this reason, ternary search is still sometimes preferable.

Copy
template <typename F> int find_min(int l, int r, const F &f) {
	while (l < r) {
		int m = (l + r) / 2;
		f(m) < f(m + 1) ? r = m : l = m + 1;
	}

	return l;
}

The way the binary search approach works is that it finds the first point where the function becomes strictly increasing. This works because we assume that our function takes the form of strictly decreasing, reaching its minimum, then strictly increasing. Thus, the first point where our function becomes strictly increasing is the turning point of our function, which is the minimum.

Example - Haybale Distribution

Explanation

Let's define a function $f(y)$ that evaluates the cost of transporting all the haybales if we deliver the haybales at point $y$. Can we show that this function is either unimodal or convex?

An important fact to know when showing that a function is convex is that the sum of convex functions is convex.

Here, $f(y)$ is the sum of all the individual cost functions for each barn. The cost function for a given barn is convex, so it turns out that $f(y)$ is also convex!

Given that a convex function is unimodal, this allows us to ternary search on it. Thus, we can find the minimum in $\mathcal{O}(\log{N})$ per query.

Implementation

Time Complexity: $\mathcal{O}((N + Q) \log{N})$

Note that the implementation below uses binary search instead, as it's a bit easier to implement.

Copy
#include <bits/stdc++.h>

using ll = long long;

int main() {
	int n;
	std::cin >> n;
	std::vector<int> x(n);
	for (int &i : x) { std::cin >> i; }

Problems