Quasiconvex Functions

Optimization · Axiom Academy

Understand a broader class of functions with convex-like optimization properties 1. Definition: Convex Sublevel Sets A function f : R n → R is quasiconvex if its sublevel sets are convex for all α ∈ R. The sublevel set S α = x : f(x) ≤ α is convex for all α This means: if f(x) ≤ α and f(y) ≤ α, then f(θx + (1-θ)y) ≤ α for all θ ∈ [0,1]. 2. Convex Functions are Quasiconvex Every convex function is quasiconvex, but the converse is not true. Convexity is a stronger condition. Proof sketch: If f is convex, then for x, y ∈ S α (where f(x) ≤ α and f(y) ≤ α): f(θx + (1-θ)y) ≤ θf(x) + (1-θ)f(y) ≤ θα + (1-θ)α = α Thus θx + (1-θ)y ∈ S α , proving S α is convex. Counterexample: f(x) = x 3 is quasiconvex on R but not convex (it has inflection points). Linear Fractional Functions: Functions of the form f(x) = (a T x + b)/(c T x + d) are quasiconvex on domains where c T x + d > 0. Distance Ratios: The ratio f(x) = ||x - a|| / ||x - b|| represents the ratio of distances to two points. This is quasiconvex and arises in facility location problems. Max Functions: f(x) = max f₁(x), f₂(x), ..., f m (x) where each f i is quasiconvex. The key optimization property: Any local minimum is a global minimum. Intuition: If there were a better point y with f(y) < f(x*), then by quasiconvexity, the entire line segment from x* to y would have function values ≤ f(y) < f(x*), contradicting that x* is a local minimum.

This is the written version of the interactive lesson above. See the full Optimization course.