Quasiconvex Functions

In the field of optimization, the concept of convexity provides a powerful foundation, likening functions to simple bowls where finding the lowest point is straightforward. However, the complexity of the real world often defies such elegant simplicity, presenting optimization landscapes with plateaus, steps, or unusual curves that are not convex. This discrepancy creates a knowledge gap, suggesting the need for a more flexible framework that retains computational tractability. This article addresses this gap by introducing quasiconvex functions, a broader class of functions that, while not strictly convex, possess a crucial underlying structure. We will first delve into the principles and mechanisms of quasiconvexity, exploring its definition through sublevel sets and its unique properties. Following that, we will uncover its profound impact through a survey of its applications and interdisciplinary connections, revealing how this mathematical idea provides solutions in fields from engineering to the fundamental physics of materials.

In our journey through the world of optimization, we often start with a concept that is as beautiful as it is powerful: ​​convexity​​. A convex function is the mathematician's version of a perfect bowl or a gentle, smiling valley. If you pick any two points on its graph and draw a straight line between them, that line will never dip below the graph itself. This simple geometric property has a profound consequence: any local minimum you find is automatically the global minimum. There's only one bottom to the valley, making the search for it remarkably straightforward.

But the real world is rarely so simple. What about landscapes with cliffs, plateaus, or long, winding slopes? Consider the humble ​​floor function​​, $f(x) = \lfloor x \rfloor$, which rounds a number down to the nearest integer. Its graph is a series of steps. If you pick two points on different steps and connect them with a line, parts of the line will clearly fall below the graph. So, the floor function is certainly not convex. Yet, intuitively, it doesn't feel treacherous for optimization. It always goes up; it never creates a "dip" or a false valley where an algorithm might get stuck. This suggests that our "perfect bowl" requirement might be too strict. We need a more generous, yet still useful, definition of a "well-behaved" function.

To broaden our view, we need to change our perspective. Instead of looking at the function's graph and the chords connecting points on it, let's think about the function as a landscape and look at its topographic map. Imagine slicing the landscape with a horizontal plane at some height, $\alpha$. The set of all points on the map where the altitude is less than or equal to $\alpha$ is what mathematicians call a ​​sublevel set​​.

This leads us to the elegant and powerful idea of ​​quasiconvexity​​. A function is quasiconvex if, for any height $\alpha$ you choose, the corresponding sublevel set is a ​​convex set​​. In one dimension, a convex set is just a single, unbroken interval. In higher dimensions, it's a "blob" without any holes or disconnected pieces.

Let's return to the floor function, $f(x) = \lfloor x \rfloor$. If we slice it at any height $\alpha$, say $\alpha=2.5$, the sublevel set is $\{x \mid \lfloor x \rfloor \le 2.5\}$, which is equivalent to $\{x \mid \lfloor x \rfloor \le 2\}$, or simply the interval $(-\infty, 3)$. No matter what $\alpha$ we pick, the sublevel set is always a simple interval. Therefore, the floor function is quasiconvex!

This new tool immediately helps us identify landscapes that are truly difficult. Consider the function $f(x) = x^4 - 2x^2$, which has a shape like the letter 'W'. If we slice this landscape at a height just above its two local minima but below the central peak, we get two separate, disconnected intervals. The sublevel set is not convex. This function is not quasiconvex, and our new definition correctly flags it as a tricky landscape with multiple valleys where a simple search could fail.

The definition of quasiconvexity, based on these convex sublevel "slices," opens the door to a whole zoo of functions that are far more varied and interesting than simple bowls.

A simple case is any ​​monotonic function​​, one that is always non-decreasing or non-increasing. A function like $f(x) = x^3$ is not convex; its second derivative $f''(x)=6x$ is not always non-negative. However, it's always increasing. Any horizontal slice will cut the graph at exactly one point, and the sublevel set will be a simple ray like $(-\infty, a^{1/3}]$, which is a convex interval. Thus, $f(x)=x^3$ is quasiconvex.

Things get more interesting with functions that have ​​plateaus​​, or flat regions. Consider $f(x) = \max\{0, |x|-1\}$. This function is zero on the entire interval $[-1, 1]$ and then rises linearly. It is quasiconvex because all its sublevel sets are single intervals. However, the presence of the flat bottom introduces a new feature: the minimum is not a single point but an entire set of points. This leads to the distinction between quasiconvexity and ​​strict quasiconvexity​​, where the function is forbidden from having such flat segments except, potentially, at its minimum. A strictly quasiconvex function guarantees a unique global minimizer, while a quasiconvex one may have many.

Perhaps the most surprising creature in our zoo is a function like $f(x) = \sqrt{\|x\|}$ in any number of dimensions $n$. If you look at its profile in one dimension, $f(x) = \sqrt{|x|}$, the curve bends downward, like a canopy—the opposite of a convex bowl! A function whose graph is a bowl has a convex ​​epigraph​​ (the set of points above the graph). This function's epigraph is not convex. And yet, it is quasiconvex. Why? Because its sublevel sets are perfect balls: the set $\{x \mid \sqrt{\|x\|} \le \alpha\}$ is just $\{x \mid \|x\| \le \alpha^2\}$, a ball of radius $\alpha^2$. Balls are fundamentally convex sets. This example is a beautiful illustration of how the sublevel set perspective is more fundamental to this property than the shape of the graph itself.

Now that we have this menagerie of functions, we need to understand the rules of their world. How do they interact? Do they combine to form new quasiconvex functions? Here, we find that quasiconvexity is a more delicate property than convexity.

The sum of two convex functions is always convex. Unfortunately, the same is not true for quasiconvexity. Imagine two simple quasiconvex functions: one is zero on an interval, say $[-3, -2]$, and one elsewhere; the other is zero on $[2, 3]$ and one elsewhere. Each function describes a landscape with a single, flat-bottomed valley. What happens when we add them? The new landscape has two valleys, at $[-3, -2]$ and $[2, 3]$, where the function value is 1, and is higher everywhere else. If we look for the region where the height is at most 1, we find two disconnected intervals. The sum is not quasiconvex. The algebra fails because adding functions corresponds to a complex operation on their sublevel sets (a union of intersections), which doesn't preserve the simple connectivity of convexity.

Similarly, the product of two quasiconvex functions is not, in general, quasiconvex. The functions $f(x) = \sqrt{|x|}$ and $g(x) = \sqrt{|x-1|}$ are both quasiconvex, but their product, $h(x) = \sqrt{|x(x-1)|}$, is not. The landscape for $|x(x-1)|$ has a bump between $x=0$ and $x=1$. Slicing this landscape just below the top of that bump results in two disjoint intervals, once again breaking quasiconvexity.

But it's not all bad news. While simple addition and multiplication can fail, we have powerful recipes for constructing quasiconvex functions. One of the most important is composition. If you have a collection of convex functions $g_i(x)$ (representing, for instance, the cost under different scenarios) and a set of non-decreasing functions $\phi_i$ (representing how we feel about that cost), then the "worst-case" function $f(x) = \max_i \phi_i(g_i(x))$ is guaranteed to be quasiconvex. This provides a powerful tool for modeling and solving problems in areas like robust engineering design, where we must find a single design parameter $x$ that performs well under a variety of uncertain conditions.

Another powerful way to view quasiconvexity is by examining it along every possible straight line cutting through the domain. A function is quasiconvex if and only if its restriction to any line is a unimodal function (in one dimension, this means its sublevel sets are intervals). This "line-search" characterization is not just a theoretical curiosity; it forms the basis of many optimization algorithms.

So why is this abstract property so important? The ultimate payoff of quasiconvexity lies in computation. The fact that sublevel sets are convex allows us to solve optimization problems that at first glance seem hopelessly non-convex.

The key is to rephrase the problem. Instead of asking "What is the minimum value of $f(x)$?", we can ask a series of simpler yes/no questions: "For a given value $t$, is there any point $x$ such that $f(x) \le t$?" This is equivalent to asking whether the sublevel set $S(t) = \{x \mid f(x) \le t\}$ is empty. Since we know this set is convex, this becomes a ​​convex feasibility problem​​—a class of problems that we can solve very efficiently.

This allows for a powerful ​​bisection method​​. We start with an interval $[\underline{t}, \overline{t}]$ that we know contains the minimum value. We pick the midpoint, $t_{mid}$, and ask our yes/no question.

• If the answer is yes (the set $S(t_{mid})$ is not empty), it means the true minimum is less than or equal to $t_{mid}$, so we can shrink our search to the lower half of the interval.
• If the answer is no, the minimum must be greater than $t_{mid}$, so we search the upper half.

By repeating this process, we can zero in on the true minimum value to any desired accuracy. We have transformed a potentially messy search over a complex landscape into a simple, reliable game of "higher or lower". This same logic applies not just to the objective function, but also to the constraints of an optimization problem. A feasible region defined by a set of inequalities $g_i(x) \le 0$, where each $g_i$ is quasiconvex, is an intersection of convex sets and is therefore itself a convex set.

Quasiconvexity, then, represents a brilliant trade-off. It relaxes the strict geometric demands of convexity, opening up a much richer and more flexible universe of functions. Yet, it preserves just enough structure—the convexity of sublevel sets—to keep the resulting optimization problems computationally tractable. It shows us that even when the world isn't a simple, perfect bowl, we can still find the bottom with elegance and efficiency.

Now that we have grappled with the definition of a quasiconvex function and explored its essential properties, you might be tempted to ask, "So what?" Is this just a clever generalization, a niche topic for mathematicians to ponder, or does it tell us something new and powerful about the world? It is a fair question, and the answer is what makes mathematics so thrilling. Quasiconvexity is not merely a curiosity; it is a deep and unifying principle that emerges in surprisingly diverse corners of science and engineering, from the practicalities of tuning a camera to the fundamental reasons for the existence of crystals.

In this chapter, we will embark on a journey to see this principle in action. We will discover how quasiconvexity provides the hidden structure that makes certain complex problems solvable, and ultimately, how it governs the very fabric of the physical world around us.

Let's begin with a simple, practical scenario. In many engineering problems, we are not necessarily looking for the absolute "best" of something, but rather trying to find an operating point that meets a certain performance target. Imagine you are designing the software for a digital camera. You need to set the exposure time, $x$. A shorter exposure might not capture enough light, leading to a noisy image, while a longer exposure might oversaturate the sensor or cause blurring. The quality of the image can often be described by a signal-to-noise ratio (SNR), and your goal is to find the minimum exposure time $x$ that achieves a target SNR.

This means we need to find the smallest $x$ that satisfies an inequality, like $\frac{\text{Noise}(x)}{\text{Signal}(x)} \le \gamma$, where $\gamma$ is our maximum tolerable noise-to-signal ratio. The function $f(x) = \frac{\text{Noise}(x)}{\text{Signal}(x)}$ might not be a simple line or parabola. However, in many realistic physical models, such a ratio of positive, increasing functions turns out to be monotonic—either always increasing or always decreasing. As we have learned, any monotonic function is quasiconvex.

What does this buy us? The sublevel set of "good" exposure times—all the $x$ values for which $f(x) \le \gamma$—is a simple, unbroken interval. This structure is precisely what allows for a beautifully simple and robust search algorithm: ​​bisection​​. We can start with a wide range of possible exposure times, test the midpoint, and based on whether it meets the criteria, we can confidently throw away half of the search range. We keep cutting the interval in half, rapidly zeroing in on the optimal setting. We don't need full convexity; the modest property of quasiconvexity is enough to guarantee that this simple search will not get stuck and will find the right answer.

This same idea appears everywhere. Consider a network operator routing traffic across two different links. The latency (delay) on each link increases as more traffic is sent over it. The operator's goal is to balance the flow to minimize the worst-case latency on either link. This "minimax" objective, $L(x) = \max\{\text{latency}_1(x_1), \text{latency}_2(x_2)\}$, also turns out to be quasiconvex. Why? Because the set of traffic-splitting strategies $x$ that keep the maximum latency below some threshold $t$ is a convex set. Once again, this structure allows us to use bisection, this time on the target latency $t$, to efficiently find the optimal flow balance that makes the worst-case delay as small as possible. In this simple case, the answer is intuitive: balance the load until the latencies are equal. Quasiconvexity provides the mathematical justification for this intuition.

The bisection method is powerful, but it relies on finding a solution to a simple inequality. What about true optimization problems, where we want to find the minimum value of a function that isn't convex? Convex functions are wonderful because they have only one valley; any local minimum is the global minimum. If you walk downhill, you are guaranteed to reach the bottom. But for a general, bumpy function, you can easily get stuck in a small local dip, blind to a much deeper valley just over the next hill.

Here is where quasiconvexity reveals a deeper magic. Think about a function that is quasiconvex but not convex, like the payoff of a "capped call" option in finance, which rises linearly and then flattens out, or certain power functions like $f(x) = \sqrt{|x|}$. These functions have flat regions or sections that curve the "wrong" way for convexity. Yet, they obey a remarkable rule: ​​for a quasiconvex function, any local minimum is also a global minimum.​​

The reasoning is as simple as it is profound. Suppose you are at a point $x^*$ that you believe is a local minimum, meaning every point in its immediate vicinity is "higher" or at the same level. Now, suppose there is another point $y$ somewhere far away that is truly "lower," i.e., $f(y) \lt f(x^*)$. Because the function is quasiconvex, the straight line path from $x^*$ to $y$ can never go above the higher of the two endpoints, which is $f(x^*)$. This means that as you take a tiny step from $x^*$ along the line towards $y$, you must be moving to a point that is at or below your starting level. But this contradicts the assumption that $x^*$ was a local minimum! The only way to resolve this paradox is if no such lower point $y$ exists. Your local minimum must have been the global one all along.

This single property is a game-changer. It tells us that for a vast class of non-convex problems, the daunting task of finding a global optimum is suddenly manageable. If we have an algorithm that finds a local minimum, we can trust its answer. This principle is invaluable in fields like:

• ​​Machine Learning:​​ When tuning a binary classifier, we might want to find the input features that lead to the lowest possible confidence, to understand the model's failure modes. The confidence, often modeled by a sigmoid function, is quasilinear (both quasiconvex and quasiconcave). Minimizing it over a set of resource constraints becomes a quasiconvex problem where we are guaranteed to find the true worst case.
• ​​Economics:​​ Many models of utility or production involve functions that are quasiconcave (meaning $-f$ is quasiconvex). This property is often more natural than full concavity and is enough to ensure that economic models have well-behaved, predictable equilibria.
• ​​Approximation Theory:​​ In problems like finding a single point $x$ that is "closest" to a set of lines or planes, the objective is often to minimize the maximum distance. This is a classic Chebyshev approximation problem, and the objective function is frequently convex, and therefore quasiconvex, ensuring a unique and computable optimal solution exists.

So far, we have seen quasiconvexity as a powerful tool for optimization. But its most profound role is not in the problems we design, but in the laws of the universe itself. The deepest applications of quasiconvexity are in the physics of materials, where it explains a fundamental mystery: why does matter form intricate patterns?

Consider a crystal, like a piece of metal or a mineral. At the microscopic level, its atoms are arranged in a regular lattice. This material stores energy in its deformation, described by a stored-energy function, $W$, that depends on the deformation gradient, $\nabla u$. For centuries, physicists and mathematicians assumed that for a material to be stable, its energy function $W$ must be ​​convex​​. This would mean that any uniform, homogeneous state is energetically preferred over any mixture or oscillation.

But this led to a crisis. Experiments in the 20th century on "smart" materials like shape-memory alloys revealed that their energy functions were definitively not convex. They had multiple "wells"—several different crystal lattice configurations that were equally happy to exist in. According to the old theory, such materials should be unstable and could not exist. Yet, they were sitting right there on the lab bench, forming beautiful, complex patterns of interlocking needles and plates.

The resolution to this paradox came from the realization that the correct condition for material stability is not convexity, but ​​quasiconvexity​​.

What does this mean? An energy function $W$ is quasiconvex if you cannot lower the average energy of a block of material by introducing fine-scale wiggles or oscillations in its deformation. If the energy function is not quasiconvex, it means the material has a clever trick up its sleeve. By arranging itself into an infinitely fine mixture of different low-energy states—forming what is called a ​​microstructure​​—it can achieve an average energy that is lower than what it could achieve with any uniform state.

The universe, in its relentless quest to minimize energy, will take this deal. The material will spontaneously form patterns. The "effective" energy density that governs the macroscopic behavior of the material is not the original, non-convex function $W$, but its ​​quasiconvex envelope​​, $QW$. This $QW$ is the largest quasiconvex function that fits underneath $W$. The difference between $W$ and $QW$ at any point is precisely the energy benefit the material gains by creating microstructure instead of remaining uniform.

This is a breathtakingly deep insight. The seemingly abstract mathematical condition of quasiconvexity is, in fact, the fundamental principle of stability for elastic materials. It is the dividing line between materials that prefer to be smooth and uniform, and those that find a lower energy state by creating intricate, beautiful, and functional internal structures. It explains the twinning in crystals, the phase transformations in alloys, and the complex patterns we see all around us. The world has texture, in part, because energy functions are not always quasiconvex.

From a simple search algorithm to the very fabric of matter, the journey of quasiconvexity shows us the remarkable power of a single mathematical idea. It is a testament to how abstract concepts, born from the generalization of simpler ones, can unlock new ways to solve problems and provide a deeper and more accurate language to describe our universe.