Convex Optimization 2026, 08 - Conjugate and Quasiconvex Functions

For a function f, define f*: ℝⁿ → ℝ, so that f*(y) = sup_{x ∈ dom f} (y^Tx - f(x)) as the conjugate of f. The domain of the conjugate function consists of y for which the supremum is finite. f* is convex, due to the pointwise supremum of a family of affine functions of y, regardless of f's convexity (3.3.1). It's subject to Fenchel's inequality: f(x) + f*(y) ≥ x^Ty. It extends to Young's inequality if f is differentiable (3.3.2.1). The conjugate of a conjugate is the original function, if the original function is convex and closed (3.3.2.2). For differentiable f, the conjugate supplies the Legendre Transformation. If f is convex and differentiable, with dom f = ℝⁿ, a maximizer x* of y^Tx - f(x) has y = ∇ f(x*). For y = ∇ f(x*), then f*(y) = x*^T∇f(x*) - f(x*). If z only has rational components, then the standard Legendre transformation follows (3.3.2.3). For a > 0, b ∈ ℝ, g(x) = af(x) + b yields a conjugate g*(y) = af*(y/a) - b. This scaling can be generalized to matrix coefficients (3.3.2.4). If f(u, v) = g(u) + h(v), and both components are convex with their conjugates g*, h*, then f*(w, z) = g*(w) + h*(z) (3.3.2).

A quasiconvex or unimodal function has a convex domain and all its sublevel sets S_α = { x ∈ dom f | f(x) ≤ α } are also convex. If so, -f is quasiconcave. A function is quasilinear if its both quasiconvex and quasiconcave, and then the inequality in the sublevel sets become strict equalities (3.4.1). Quasiconvexity is a generalization of convexity. It inherits a version of Jensen's inequality: f(θx + (1 - θ)y) ≤ max{f(x), f(y)}. Quasiconvex continuous functions from ℝ to ℝ, are nondecreasing or nonincreasing, or if there is a c ∈ dom f: t ≤ c then f is nonincreasing and for t ≥ c, f is nondecreasing (3.4.2). If f is differentiable, it's quasiconvex iff dom f is convex and ∀ x, y ∈ dom f: f(y) ≤ f(x) ⇒ ∇ f(x)^T(y - x) ≤ 0 (3.4.3.1). If f is twice differentiable and quasiconvex , then ∀ x ∈ dom f, y ∈ ℝⁿ: y^T∇f(x) = 0 ⇒ y^T∇²f(x)y ≥ 0. On ℝ, then f'(x) = 0 ⇒ f''(x) ≥ 0 (3.4.3.2). A nonnegative weighted maximum of quasiconvex functions with w_i ≥ 0, f_i quasiconvex is itself quasiconvex (3.4.4.1). For a quasiconvex g and nondecreasing h, f = h ○ g is quasiconvex. Similarly, for an affine or linear-fractional transformation h. If f is quasiconvex, so is g(x) = f(Ax + b) and h(x) = f((Ax + b)/(c^Tx + d)) (3.4.4.2). If f(x, y) is quasiconvex in x and y, and C a convex set, g(x) = inf_{y ∈ C} f(x, y) is quasiconvex (3.4.4.3).