Quasiconvex Functions

Every sublevel set an interval — weak enough to include and x , strong enough for bisection.

The idea

A quasiconvex function is one whose sublevel sets are all convex.

Definition (Quasiconvex function).

A function $f$ is quasiconvex when its domain is convex and, for every level $\alpha$, the sublevel set $S_{\alpha} = \{x \in \operatorname{dom} f : f(x) \le \alpha\}$ is a convex set.

For a function on the real line this says that each $S_{\alpha}$ is a single interval — in the figure, the interval between the two points $a$ and $b$ where the horizontal line at height $\alpha$ crosses the graph.

The condition is genuinely weaker than convexity. Every convex function is quasiconvex, because a convex function has convex sublevel sets; but a function that descends, flattens into a shoulder, and descends again fails the chord condition and is still quasiconvex — it has no local dip to trap a minimization in.

Quasiconvexity supports minimization by bisection. Minimizing $f$ is not itself a convex problem, but deciding whether any point satisfies $f(x) \le \alpha$ is a convex feasibility problem, because $S_{\alpha}$ is convex. Bisect on $\alpha$: each answer halves the interval in which the optimal value can lie, so the sequence of feasibility problems converges to the optimal value of $f$, to any accuracy required.

Ways to work on it

• Walkthrough. Define quasiconvexity through sublevel sets and see why bisection can still minimize such functions.
• Proof. Convex sublevel sets and the maximum inequality are the same condition — and convexity implies both, but not conversely.
• Practice. Compute a sublevel set, then classify the function as convex, quasiconvex only, or neither.
• Hardest. Prove a ratio of functions is quasiconvex, and identify one of its sublevel sets exactly.

Not sure where to start? Take the ten-question placement test.