Quasi-convexity

1 Definition and Basic Properties

1.1 Quasi-convex Functions via Upper Level Sets

Let \(f:\mathbb{R}^n\to\mathbb{R}\) be a real-valued function. The function is quasi-convex if, for every real number \(\alpha\), the upper level set \[ \{x\in\mathbb{R}^n: f(x)\le \alpha\} \] is a convex set. Equivalently, for any two points \(x,y\) in the domain and any \(t\in[0,1]\), the value of \(f\) along the segment between them never exceeds the larger of the endpoint values: \[ f(tx+(1-t)y)\le \max\{f(x),f(y)\}. \] This “max rule” characterizes the geometric idea that sublevel sets bend inward but are not required to follow the stricter linear-interpolation behavior of convex functions.

1.2 Equivalent Characterizations

1.2.1 Convexity of Sublevel Sets

The most common equivalent form is the sublevel-set test: \(f\) is quasi-convex exactly when every set \(\{x: f(x)\le \alpha\}\) is convex. This formulation is often the easiest to verify in applications where constraints or objective thresholds are used, since it converts a functional property into a geometric one.

1.2.2 Jensen-Type Inequality Formulations

For quasi-convexity, a direct Jensen inequality does not hold in the same way as for convexity. Instead, quasi-convexity yields a Jensen-type inequality driven by the maximum: \[ f\Big(\sum_{i=1}^k \lambda_i x_i\Big)\le \max_i f(x_i) \quad\text{whenever }\lambda_i\ge 0,\ \sum_i\lambda_i=1. \] The essence is that mixing points cannot create a value larger than the worst value among the mixed points. This can be viewed as a multi-point extension of the “segment” property.

1.3 Relationship to Convexity

1.3.1 Convex vs. Quasi-convex Examples

Every convex function is quasi-convex: convexity implies that sublevel sets are convex, hence the quasi-convex condition holds. The converse is false. For instance, functions with “valleys” that are not bowl-shaped can still have convex sublevel sets. A classic source of examples comes from norms and monotone transformations of convex expressions (see later sections), where geometry remains favorable even if the original function does not satisfy full convexity.

A useful way to separate the notions is to compare interpolation inequalities. Convexity demands \[ f(tx+(1-t)y)\le tf(x)+(1-t)f(y), \] while quasi-convexity relaxes this to \[ f(tx+(1-t)y)\le \max\{f(x),f(y)\}. \] The latter is weaker because \(tf(x)+(1-t)f(y)\le \max\{f(x),f(y)\}\), but not vice versa.

1.3.2 Strict Quasi-convexity and Implications

A function is strictly quasi-convex if, whenever \(x\ne y\) and \(t\in(0,1)\), \[ f(tx+(1-t)y)<\max\{f(x),f(y)\} \quad\text{provided the maximum is attained at a unique endpoint}. \] More carefully, one often states: if \(f(x)\ne f(y)\), then along the open segment the function value lies strictly below the larger endpoint value. This strengthened form supports sharper conclusions about minimizers: under mild regularity, solution sets often become smaller (e.g., convex but potentially singletons), and flat regions are reduced compared with the merely quasi-convex case.

1.4 Monotone Transformations and Preservation Rules

Quasi-convexity is stable under certain monotone changes. If \(\phi:\mathbb{R}\to\mathbb{R}\) is nondecreasing, then \(f\) quasi-convex implies \(\phi\circ f\) is quasi-convex, since \[ \{x: \phi(f(x))\le \alpha\}=\{x: f(x)\le \phi^{-1}(\alpha)\} \] up to set-theoretic handling of non-strict inverse behavior. In contrast, a nonincreasing \(\phi\) generally turns quasi-convexity into quasi-concavity (a dual notion), because inequalities reverse.

This preservation principle is a major reason quasi-convexity is widely used: many expressions in optimization appear after logarithms, truncations, or scaling, and monotonicity allows the geometric core to survive.

2 Level-Set Geometry

2.1 Sublevel Set Structure

2.1.1 Convexity of Sets \(\{x : f(x) \le \alpha\}\)

Quasi-convexity is encoded entirely by the geometry of sets \(\{x: f(x)\le \alpha\}\). For each threshold \(\alpha\), the corresponding set is convex, so its interior and supporting directions behave predictably. As \(\alpha\) increases, these sets typically expand (monotonicity with respect to \(\alpha\) follows from the definition).

This structure implies that the collection of feasible points below a given objective level forms a “convex-safe” region: any mixture of two feasible points remains feasible. Such robustness supports global optimization results because local improvements cannot be hidden behind nonconvex geometric features inside a sublevel set.

2.1.2 Boundary Behavior and Level-Set Smoothness

While quasi-convexity guarantees convexity of sublevel sets, it does not force the boundaries to be smooth. Boundaries can be nonsmooth, polyhedral, or curved depending on \(f\). Nevertheless, convexity of the level sets imposes strong restrictions: the boundary cannot bend outward in a way that violates convexity. In smooth settings, one can often interpret quasi-convexity through curvature-like conditions of the level surfaces, but in nonsmooth analysis these are replaced by geometric supporting properties (see differential/subdifferential sections).

In practice, regularity assumptions such as lower semicontinuity help ensure that minimizers exist and that sublevel sets behave well under limits. Without such assumptions, the level-set picture may still be valid, but the optimizer’s existence may fail.

2.2 Quasi-convexity in Higher Dimensions

2.2.1 Geometry in \(\mathbb{R}^n\) and Affine Changes

The definition is dimension-agnostic: quasi-convexity is defined via convexity of sets in \(\mathbb{R}^n\). Under affine transformations, many quasi-convex properties persist. If \(A\) is an invertible affine map and \(g(x)=f(Ax+b)\), then sublevel sets of \(g\) are affine images of sublevel sets of \(f\). Since affine maps preserve convexity, \(g\) remains quasi-convex.

If \(A\) is not invertible, the situation can still be favorable: preimages and images of convex sets under linear maps relate to convexity depending on whether the map collapses directions. As a result, quasi-convexity may be preserved under certain linear operators, particularly when the problem is restricted to appropriate subspaces.

2.3 Practical Visualization Techniques

2.3.1 Contour Plots and Sublevel Maps

Visualization is often carried out through contour plots (level curves in two dimensions) or sublevel maps. For a quasi-convex function, each contour threshold corresponds to a convex region. In two dimensions, one can check quasi-convexity informally by verifying that the set enclosed by each contour is convex for every chosen threshold.

In higher dimensions, visualization relies on slices: fixing some coordinates reduces the problem to a lower-dimensional cross-section, where the convexity of sublevel sets can be assessed. While slicing cannot prove global quasi-convexity alone, it can reveal whether the function’s geometry is consistent with the quasi-convex definition.

3 Differential and Subdifferential Characterizations

3.1 Quasi-convexity for Differentiable Functions

3.1.1 Gradient Inequalities Along Chords

When \(f\) is differentiable, quasi-convexity can be expressed through inequalities involving the gradient. A common principle is that along directions pointing into a lower sublevel region, the directional derivative cannot increase the function beyond the sublevel’s boundary behavior. One representative condition states that if \(x\) and \(y\) satisfy \(f(y)\le f(x)\), then the directional change from \(x\) toward \(y\) is compatible with not crossing above the higher value. In differential form, this translates into gradient inner-product inequalities that constrain how \(f\) can rise when moving toward points with smaller function values.

These gradient-based tests are particularly useful because they allow checking quasi-convexity locally rather than by enumerating all sublevel sets.

3.1.2 Directional Derivatives and Shape Conditions

Directional derivatives provide another lens: quasi-convex functions admit “no inward crossing” behavior relative to their sublevel sets. Informally, if one chooses a direction that aims toward a point with smaller function value, the immediate rate of change in that direction cannot contradict the convex shape of the sublevel region.

In smooth optimization, such conditions connect quasi-convexity with monotonicity of \(f\) along rays emanating from boundary points of sublevel sets, though the exact statements depend on whether one uses strict or generalized quasi-convexity and on the notion of derivative (Fréchet, Gâteaux, or directional).

3.2 Subdifferential Criteria

3.2.1 Convex-Analytic Extensions

For nondifferentiable functions, subdifferentials replace gradients. The quasi-convexity concept remains geometric, but subgradient criteria can encode supporting behavior of sublevel sets. In convex analysis, convex functions use subgradients to produce supporting hyperplanes; quasi-convex functions have analogous but more subtle hyperplane-like statements tied to level sets.

A typical approach is to use subdifferentials of \(f\) at points on the boundary of a sublevel set to ensure that any subgradient defines a half-space that does not cut through points with strictly larger function values.

3.2.2 Supporting Hyperplane-Type Conditions

Because sublevel sets are convex, any boundary point admits supporting hyperplanes in the convex-set sense. Quasi-convexity therefore implies that there exist linear functionals that support the set \(\{x: f(x)\le \alpha\}\) at boundary points. Subdifferential formulations make this precise by relating those supporting hyperplanes to generalized derivatives of \(f\). Such criteria are central in establishing KKT-like conditions and in proving that stationary points have global optimality properties for quasi-convex objectives (under constraints described later).

3.3 Connection with KKT-Like Conditions

3.3.1 Quasi-convex Objectives in Constrained Problems

Optimization with constraints often relies on first-order stationarity principles. For quasi-convex objectives, stationary points tend to be more meaningful than in the general nonconvex case. Under appropriate regularity conditions and convexity assumptions on constraints (commonly convex feasible sets), if a candidate point satisfies suitable stationarity conditions, it can correspond to a global minimizer for the objective.

The mechanism is geometric: quasi-convexity ensures that lower objective values correspond to convex sublevel sets, so once a point cannot improve in a first-order sense, moving to any feasible direction that would reduce the objective would necessarily cross a boundary in a way disallowed by the supporting geometry.

4 Optimization Applications

4.1 Minimizers and Solution Set Properties

4.1.1 Local vs. Global Minima

A central advantage of quasi-convexity is the relationship between local and global optimality. For a quasi-convex objective over a convex feasible region, any local minimizer is often a global minimizer. The intuition is that if a local minimum existed but a better point existed elsewhere, the entire segment from the local minimizer to the better point would remain within a lower sublevel set (by quasi-convexity), contradicting local minimality.

This property is weaker than the fully convex case yet strong enough for many optimization tasks, especially when the feasible set is convex and the objective is quasi-convex.

4.1.2 Uniqueness Conditions for Minimizers

Quasi-convexity alone does not guarantee uniqueness: the sublevel sets can contain line segments, yielding multiple minimizers. Uniqueness typically requires additional structure, such as strict quasi-convexity, strict monotonicity of the objective along feasible directions, or conditions ensuring that the set of minimizers is a singleton.

When strict quasi-convexity holds on the feasible region, the minimum value cannot be achieved at two distinct points without forcing intermediate points to have strictly smaller values, which is incompatible with minimality. Consequently, minimizers may become unique under suitable feasibility and regularity.

4.2 Algorithms and Quasi-convex Programs

4.2.1 Finding Global Minima Under Quasi-convexity

Quasi-convex optimization problems can often be handled by bisection on objective thresholds or by algorithms that maintain feasibility with respect to shrinking sublevel sets. Because each sublevel set is convex, one can check whether there exists a feasible point with \(f(x)\le \alpha\). If that feasibility problem is tractable (often due to convex constraints), then a search over \(\alpha\) can locate the global minimum.

For certain classes of quasi-convex programs, interior-point or cutting-plane style methods can be adapted, exploiting convexity of sublevel sets rather than convexity of the objective function itself.

4.2.2 Feasible Region Interactions

The feasible region’s geometry interacts with quasi-convexity. When constraints define a convex feasible set, quasi-convexity of the objective aligns with convexity of the relevant portion of sublevel sets. In contrast, with nonconvex constraints, the global-local equivalence can fail because even if sublevel sets are convex, the intersection with a nonconvex feasible set may create nonconvex behavior.

Thus, global optimization results typically assume convexity (or other structured properties) of constraints, plus regularity ensuring that the feasibility-based threshold checks behave correctly.

4.3 Quasi-convex Constraints and Feasible Set Convexity

4.3.1 Sublevel Constraints as Convex Sets

Constraints of the form \[ f(x)\le \alpha \] are particularly convenient when \(f\) is quasi-convex, because the constraint set is exactly the sublevel set, which is convex by definition. Therefore, quasi-convex functions can generate convex feasible regions even if the objective itself is not convex.

This principle underpins many modeling frameworks: by choosing appropriate quasi-convex functions for constraint expressions, one can keep the overall optimization problem within tractable convex geometry.

5 Closure Properties and Function Operations

5.1 Sums, Products, and Composition Rules

5.1.1 When Operations Preserve Quasi-convexity

Quasi-convexity is preserved by several operations, though not by simple arithmetic in general. Commonly preserved patterns include:

• Nondecreasing composition: If \(f\) is quasi-convex and \(\phi\) is nondecreasing, then \(\phi\circ f\) is quasi-convex.
• Taking maximum with convex-like structure: Under suitable conditions, combining functions via operations that preserve sublevel-set convexity can keep the result quasi-convex.
• Affine transformations of the input: As noted earlier, composing with affine maps preserves quasi-convexity.

These rules are usually justified by direct inspection of sublevel sets under the operation.

5.1.2 Counterexamples and Failure Modes

Not all operations are safe. In particular:

• Sums of quasi-convex functions are not necessarily quasi-convex.
• Products and ratios can destroy the convexity of sublevel sets unless extra monotonicity or structural assumptions are imposed (such as positivity and special algebraic forms).
• Composition with decreasing functions generally changes the inequality direction and thus replaces quasi-convexity with quasi-concavity, or may lead to loss of either property.

Counterexamples typically exhibit situations where a sum smooths out a “valley” in a way that makes some sublevel set nonconvex.

5.2 Limits, Infima, and Epigraph/Sublevel Constructions

Operations involving limits require attention to semicontinuity. Quasi-convexity can be stable under certain forms of pointwise limits, provided the limiting sublevel sets behave well. Infima over auxiliary variables can also produce quasi-convex functions in settings where the sublevel-set construction commutes with projection (often related to convexity of sets in product spaces).

The geometric approach remains central: define the relevant set in an extended space so that projecting back preserves convexity under appropriate conditions.

5.3 Regularity Assumptions

5.3.1 Lower Semicontinuity Considerations

Lower semicontinuity ensures that sublevel sets \(\{x: f(x)\le \alpha\}\) are closed for real \(\alpha\), improving existence and stability of minimizers. For optimization, closedness matters because minimizing sequences may otherwise converge to points where the objective value jumps upward.

In quasi-convex settings, lower semicontinuity complements convexity of sublevel sets by providing compactness or closedness properties needed for standard existence theorems.

5.3.2 Continuity vs. Non-continuity

Continuity implies both upper and lower semicontinuity and simplifies analysis, but it is not required for much of quasi-convex theory. Non-continuous quasi-convex functions can still have convex sublevel sets yet produce unusual boundary behavior. Algorithms may need careful handling when objective values have jumps, and solution characterization may depend on whether one seeks minimizers versus infimum points.

6 Examples and Canonical Classes

6.1 Simple Scalar and Norm-Based Examples

6.1.1 Norms, Ratios, and Affine-Fractional Forms

Norms provide canonical quasi-convex examples. For any norm \(\|\cdot\|\), the function \(f(x)=\|x\|\) is convex and thus quasi-convex. More broadly, functions of the form

\[

f(x)=\|Ax+b\|

\] with affine inside the norm are convex under typical norms and remain quasi-convex.

Affine-fractional constructions also appear: when expressions can be rewritten so that their sublevel sets are convex cones or affine images thereof, the resulting function is quasi-convex. A common pattern is a positive denominator and a monotone transformation that preserves the inequality structure.

6.1.2 Norms, Ratios, and Affine-Fractional Forms

A second useful class includes ratio-like forms where the denominator is positive and the whole expression can be interpreted via level sets that are convex. For example, if a function represents the smallest scalar \(\alpha\) such that a linear inequality holds (a gauge-type formulation), then its level sets inherit convexity. Such constructions link quasi-convexity to gauges, Minkowski functionals, and related geometric measures.

6.2 Fractional and Log-Transform Examples

6.2.1 Log-Convex vs. Quasi-convex Relations

Logarithms relate convexity properties through monotone transformations. If \(f&gt;0\), then \(\log f\) being convex means \(f\) is log-convex. Log-convexity is stronger in a multiplicative sense and implies quasi-convexity of \(f\) (since convexity of \(\log f\) enforces convexity of appropriate level sets). However, quasi-convexity does not imply log-convexity; the gap reflects how multiplicative structure differs from additive interpolation.

In practice, these relationships matter when objective functions contain exponentials, products, or likelihood-like terms where logarithms are introduced for stability or analysis.

6.3 Non-Convex but Quasi-convex Constructions

Quasi-convexity allows objectives that are not convex. A typical mechanism is to start with a convex quantity \(g(x)\) and apply a transformation \(\phi\) that is nondecreasing but not convex-preserving in the additive sense. For instance, a nonconvex but nondecreasing transformation of a convex function yields a quasi-convex function because sublevel sets remain unchanged up to reparameterization.

Another route is to build functions whose geometry is governed by convex sublevel sets even though curvature along chords does not satisfy convexity’s linear inequality. The resulting function can exhibit “kinks” or plateau regions while still maintaining convex level-set interiors.

7 Further Topics

7.1 Quasi-concavity Duality

7.1.1 Sublevel vs. Superlevel Sets

The dual notion to quasi-convexity is quasi-concavity, defined via convexity of superlevel sets: \[ \{x: f(x)\ge \alpha\}\ \text{is convex for all }\alpha. \] Quasi-convexity and quasi-concavity are linked by sign reversal: \(f\) is quasi-convex if and only if \(-f\) is quasi-concave. This duality is useful in optimization, since maximizing a quasi-concave objective over a convex feasible set often parallels minimizing a quasi-convex one.

7.2 Approximation and Related Notions

7.2.1 Pseudo-convexity and Quasi-convexity Connections

Related classes include pseudo-convexity, quasiconvexity, and invexity-like generalizations. While quasi-convexity focuses on the convexity of sublevel sets, pseudo-convexity emphasizes implication relationships between stationarity and global optimality. In smooth settings, these properties can coincide or imply each other under additional differentiability and regularity conditions, but generally they capture different geometric and analytic behaviors.

Approximation methods may approximate a quasi-convex objective by sequences with additional structure (such as smoother or convex-like functions) while preserving level-set geometry sufficiently to maintain optimization guarantees.

7.3 Applications Beyond Optimization

7.3.1 Economics/Decision Models (Non-controversial Modeling Contexts)

In decision theory and economics modeling, quasi-convexity often appears when preferences or costs are evaluated through thresholds that produce convex acceptance sets. For example, risk metrics or utility-like criteria can be expressed so that sets of actions achieving at most some cost are convex, enabling optimization and equilibrium computations. The appeal is that convex feasible interpretations allow tractable analysis even when the underlying criterion is not fully convex.

7.3.2 Signal/Inference Shaping via Level Sets

In signal processing and inference, quasi-convex functions can be used to shape objective landscapes based on level sets rather than strict convex curvature. Robust penalties, uncertainty measures, and constraint-like filters may yield convex sublevel regions, which can stabilize numerical procedures and facilitate global search strategies. Even when the full objective is not convex, level-set convexity supports methods that rely on feasibility checks at candidate thresholds.