= Quasiconvex function
A \b[quasiconvex function] is a real-valued <function> on a <convex set> whose every <sublevel set> is convex. If the domain is $D$, this means
$$
S_\alpha=\{x\in D:f(x)\leq\alpha\}
$$
is a <convex set> for every real $\alpha$, including levels for which the set is empty. Equivalently,
$$
f((1-t)x+ty)\leq\max\{f(x),f(y)\},\qquad 0\leq t\leq1.
$$
Boyd and Vandenberghe give these level-set and segment characterizations.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§3.4.1, definition and first characterization]{ref}
To see their equivalence, set $\alpha=\max\{f(x),f(y)\}$. Convexity of that sublevel set puts every <convex combination> of $x$ and $y$ inside it, proving the inequality. Conversely, if two points lie below the same level, the inequality keeps their connecting segment below that level.
Quasiconvexity is weaker than <convexity>. An original example is $f(x)=\sqrt{|x|}$ on $\mathbb R$. For $\alpha\geq0$, its sublevel set is $[-\alpha^2,\alpha^2]$; for $\alpha<0$, it is empty. All are convex, but
$$
f(1/2)=1/\sqrt2>1/2=\tfrac12f(0)+\tfrac12f(1),
$$
which violates the convex-function inequality. Quasiconvexity limits the height along a segment by the larger endpoint value, rather than by the line joining endpoint values.
A strictly increasing transformation preserves the sublevel ordering and hence quasiconvexity. This can be useful when a complicated objective has simple level sets. <Quasiconvex optimization> exploits those sets through feasibility tests at trial objective values; it need not treat the objective itself as a convex function.
In one dimension the shape corresponds to the single-minimum convention of <unimodality>. Flat portions require care: the step function equal to0 for $x\leq0$ and1 for $x>0$ is quasiconvex. Every point strictly to the right of zero is a non-strict local minimizer on a small flat neighborhood, yet its value is not globally minimal. Quasiconvexity alone therefore does not justify replacing every local minimum by a global one.
Back to article page
