Pseudo-convexity - Ciallo Wiki

1 Definition and Basic Properties

Pseudo-convexity is a curvature-related property for real-valued functions that weakens convexity while preserving an important “directional decrease” principle. Informally, a pseudo-convex function behaves like it has a supporting inequality in the sense that failure of a gradient-based test forces the function to decrease in the direction suggested by the gradient.

1.1 Differentiable Pseudo-convex Functions

Let \(f:\mathbb{R}^n\to\mathbb{R}\) be differentiable on a convex set \(C\subseteq \mathbb{R}^n\). The standard definition states:

\(f\) is pseudo-convex on \(C\) if for any \(x,y\in C\), \[ \nabla f(x)\cdot (y-x)\ge 0 \quad \Rightarrow \quad f(y)\ge f(x). \] Equivalently, if \(f(y)<f(x)\) then necessarily \(\nabla f(x)\cdot (y-x)<0\). Thus, whenever the gradient does not point toward a lower value (in the first-order sense), moving to \(y\) cannot reduce the function.

1.2 Comparison with Convexity and Quasi-convexity

Convexity implies pseudo-convexity for differentiable functions: if \(f\) is convex, then the condition \(\nabla f(x)\cdot (y-x)\ge 0\) prevents \(f(y)\) from being smaller than \(f(x)\), because convexity provides a global supporting hyperplane inequality. Pseudo-convexity does not require the full supporting hyperplane structure needed for convexity, so it allows more functions that may be nonconvex yet still have the “no false stationary information” behavior.

Pseudo-convexity is also distinct from quasi-convexity. Quasi-convexity constrains upper level sets to be convex, which is a geometric set-based property; pseudo-convexity constrains the relationship between function values and first-order directional derivatives. One can find examples in which a function is pseudo-convex but not quasi-convex, and vice versa.

1.3 Equivalent Characterizations (Gradient-Based Conditions)

For differentiable \(f\), several gradient-based equivalences are commonly used.

A frequently adopted contrapositive form is: \[ f(y)< f(x) \quad \Rightarrow \quad \nabla f(x)\cdot (y-x)<0. \] Another characterization uses an implication with strict inequalities. If one strengthens the definition to a strict form, then: \[ \nabla f(x)\cdot (y-x) \le 0 \Rightarrow f(y)\le f(x) \] paired with suitable strictness assumptions (depending on whether strict pseudo-convexity is intended). Under standard regularity and differentiability, these formulations encode the same underlying mechanism: the gradient-based test correctly predicts the sign of the change in \(f\).

1.4 Geometric Interpretation (Supporting-Type Behavior)

Although pseudo-convexity is weaker than convexity, it still imposes a one-sided support behavior. At each point \(x\), the hyperplane determined by the gradient at \(x\) divides the space into directions that cannot decrease \(f\) and directions that must decrease \(f\). In other words, the set of directions \(d\) for which \(\nabla f(x)\cdot d\ge 0\) corresponds to movements that cannot yield a smaller function value than at \(x\).

Geometrically, this yields a “directed” curvature effect: the function may bend in complicated ways, but it cannot produce a situation where the gradient suggests non-decrease while the function value actually drops.

2 Pseudo-convexity in Optimization

Pseudo-convexity is a central tool in optimization because it converts local stationarity information into global optimality. This can occur even when the objective is not convex, provided the pseudo-convex structure is satisfied and constraints are handled appropriately.

2.1 Unconstrained Minimization

Consider minimizing a differentiable pseudo-convex function \(f\) over an open convex domain.

2.1.1 Stationary Points and Global Optimality

Pseudo-convexity ensures that any stationary point is a global minimizer. Intuitively, if a point \(x^\*\) has gradient zero, then the pseudo-convex implication blocks the possibility of any \(y\) with \(f(y)<f(x^\*)\).

2.1.1.1 Necessary and Sufficient Conditions

For differentiable objectives, the key statement is:

If \(f\) is pseudo-convex and \(x^\*\) satisfies \(\nabla f(x^\*)=0\), then \(x^\*\) is a global minimizer of \(f\).

Conversely, for unconstrained minimization of differentiable functions, global optimality typically yields first-order stationarity under mild regularity (e.g., if the minimizer lies in the interior). In that sense, for pseudo-convex differentiable problems, the first-order condition \(\nabla f=0\) becomes both meaningful and sufficient for global optimality.

2.2 Constrained Optimization

In constrained settings, pseudo-convexity is used to secure global conclusions from KKT-like conditions, mirroring the way convexity supports these results in standard convex programming.

2.2.1 Pseudo-convexity of Objective and Constraint Functions

A common framework considers constraints described by differentiable functions, such as inequality constraints \(g_i(x)\le 0\) and equality constraints \(h_j(x)=0\). One typically assumes:

the objective \(f\) is pseudo-convex, and
each inequality constraint \(g_i\) is pseudo-convex (or related variants, depending on the exact constraint type),

along with appropriate regularity conditions (e.g., constraint qualification).

These assumptions are designed so that complementarity and the sign structure of multipliers interact correctly with the pseudo-convex implications.

2.2.2 KKT-Type Conditions Under Pseudo-convexity

With standard constraint qualifications, the Karush–Kuhn–Tucker (KKT) conditions provide necessary optimality conditions for local minima. Under pseudo-convexity assumptions on the objective and constraint functions, KKT conditions can become sufficient:

If there exist multipliers such that the KKT system holds at a feasible point \(x^\*\), and the problem data satisfy pseudo-convexity hypotheses aligned with the constraints, then \(x^\*\) is a global minimizer.

The mechanism parallels the unconstrained case: the gradient-based “directional correctness” guaranteed by pseudo-convexity prevents existence of any feasible direction that both satisfies constraint linearization and improves the objective value.

2.3 Relation to Second-Order Conditions

Pseudo-convexity is fundamentally first-order, but it can be connected to second-order information through stronger assumptions or auxiliary derivative concepts.

2.3.1 Hessian-Based Sufficient Tests

For twice differentiable functions, one may derive sufficient conditions involving the Hessian. While pseudo-convexity is not equivalent to convexity of the Hessian, certain Hessian inequalities imply pseudo-convexity. In practice, these conditions provide verifiable tests when full pseudo-convexity is difficult to check directly.

A common theme is: if directional curvature is aligned with decreasing behavior suggested by gradients, then the pseudo-convex implication holds globally on the domain.

2.3.2 Connections to Generalized Derivatives

When differentiability fails or when dealing with variational inequality formulations, generalized derivatives such as Clarke gradients or Dini/directional derivatives may be used. Corresponding generalized notions of pseudo-convexity are then formulated so that the “gradient test implies value monotonicity” concept is preserved in a nonsmooth sense.

These connections allow pseudo-convexity ideas to extend beyond classical smooth calculus, supporting analysis on broader function classes and in functional spaces.

3 Pseudo-convexity of Vector-Valued and Composite Functions

Pseudo-convexity is typically introduced for scalar objectives, but many optimization models involve vector expressions, compositions, or transformations. Extending pseudo-convexity requires careful rules to ensure the essential implication structure survives.

3.1 Scalarization and Reformulations

When a problem has vector-valued data, scalarization is often used to reduce the model to a scalar function. For example, one may minimize a scalar merit function derived from a vector map. If the scalarized objective is pseudo-convex and the scalarization is compatible with the model’s ordering, then global conclusions analogous to the scalar case can be drawn.

However, pseudo-convexity of the underlying vector components alone does not automatically imply pseudo-convexity of the scalarized function; the scalarization operator matters.

3.2 Composition Rules

Composite forms such as \(f(x)=\phi(g(x))\) appear frequently. Pseudo-convexity can be preserved under composition when \(\phi\) is monotone in a way that does not break the implication between gradient tests and function values.

3.2.1 Monotone Transformations

If \(\phi:\mathbb{R}\to\mathbb{R}\) is differentiable and strictly increasing, then pseudo-convexity of \(g\) can transfer to \(\phi\circ g\) under suitable differentiability and domain assumptions. The intuition is that strict increase preserves order: whenever \(g\) would decrease, so would \(\phi(g)\), and the gradient implication rescales by \(\phi'(g(x))\) without changing its sign.

If \(\phi\) is decreasing, the relationship changes and may convert minimization-type properties to maximization-type ones, unless the definition is adjusted accordingly.

3.2.2 Chain Rule Implications

Under standard differentiability, the gradient of a composition satisfies \[ \nabla (\phi\circ g)(x)=\phi'(g(x))\,\nabla g(x). \] Therefore, the sign of \(\nabla (\phi\circ g)(x)\cdot (y-x)\) is governed by \(\phi'(g(x))\) times \(\nabla g(x)\cdot (y-x)\). Pseudo-convexity transfers when \(\phi'(g(x))\) has a consistent sign over the relevant domain region.

3.3 Sums, Products, and Stability Under Operations

Operations on functions can preserve pseudo-convexity, but not all algebraic combinations behave well. Stability results typically depend on additional monotonicity, sign, or curvature assumptions.

3.3.1 Preservation Results

Certain preservation statements hold under restrictive circumstances. For instance, if two functions share compatible pseudo-convexity properties and are combined through operations that respect ordering (such as positive scalar multiplication, or addition under particular conditions), then the result may remain pseudo-convex.

In many cases, the preservation requires that any improvement in one term implies an improvement in the total function in a manner compatible with the pseudo-convex implication structure.

3.3.2 Counterexamples and Limitations

General sums and products do not preserve pseudo-convexity in full generality. A function may be pseudo-convex, while adding another pseudo-convex term can introduce a landscape that creates a “false” stationary behavior relative to the combined objective. Similarly, products can change sign and distort gradients in ways that break the directional implication.

These limitations are important in modeling: pseudo-convexity should not be assumed to persist under arbitrary algebraic manipulation.

4 Examples and Non-Examples

Concrete examples clarify what pseudo-convexity allows and what it forbids. They also show how checking pseudo-convexity can be more manageable than verifying convexity, while still requiring attention.

4.1 Canonical Examples from Calculus

A common class arises from functions of one variable extended to higher dimensions via norms or linear forms. For instance, differentiable functions like \(f(x)=e^{a^\top x}\) are pseudo-convex (and in fact convex), but examples often extend to functions that are not convex yet satisfy the pseudo-convex implication.

Another route is to consider functions that are “radially monotone” in a way that enforces order preservation along gradient directions.

4.2 Common Families Exhibiting Pseudo-convexity

Beyond simple exponentials, pseudo-convexity appears in families where the function’s directional derivatives behave consistently with function value changes. Typical examples include certain ratios of affine functions under domain restrictions, and functions derived from monotone transformations of quasi-linear expressions.

In optimization literature, pseudo-convexity is also used to cover fractional programming and other reformulated problems where convexity is too strict but first-order correctness still holds.

4.3 Functions That Are Pseudo-convex but Not Convex

Pseudo-convex-but-not-convex functions demonstrate the gap between these notions. Such functions can have curvature that fails to satisfy the global supporting hyperplane inequality required for convexity, yet they still cannot produce the forbidden pattern: \[ \nabla f(x)\cdot (y-x)\ge 0 \ \text{while}\ f(y)<f(x). \] Constructing explicit multidimensional examples often uses careful algebra to ensure the implication holds globally on the chosen domain while convexity fails.

4.4 Checking Pseudo-convexity in Practice

Verifying pseudo-convexity directly from the definition can be challenging because it quantifies over all pairs \((x,y)\). Practical checks therefore rely on alternative criteria, structure, or domain restrictions.

4.4.1 Verifying Gradient Inequalities

One approach is to attempt to prove that for any fixed \(x\), whenever the gradient pairing satisfies \(\nabla f(x)\cdot (y-x)\ge 0\), the function value cannot drop. This can sometimes be reduced to inequalities involving directional derivatives or to establishing that the function is monotone along certain rays dictated by the gradient.

In structured problems (e.g., where \(f\) depends on a norm, an affine form, or a separable expression), the verification can be simplified by reducing the problem to lower-dimensional inequality checks.

4.4.2 Local-to-Global Considerations

Pseudo-convexity is global in its standard definition on a domain, but in some settings it can be established by analyzing the function along relevant trajectories and showing that local behavior enforces global order. Domain convexity and connectedness often play roles in extending local monotonicity properties across the domain.

Even with such tools, numerical algorithms usually do not “verify” pseudo-convexity; instead, modeling and theoretical derivations justify the assumption.

5 Variational Analysis and Functional Spaces

Pseudo-convexity ideas extend to infinite-dimensional settings and to variational formulations. Here, the definitions are adapted to accommodate functional spaces and generalized derivatives.

5.1 Pseudo-convexity in Banach and Hilbert Spaces

In Banach or Hilbert spaces, one replaces gradients with appropriate notions of derivative compatible with the topology and dual pairing. For Hilbert spaces, inner products allow a direct analogy to \(\nabla f(x)\cdot (y-x)\). In Banach spaces, the corresponding pairing involves dual elements acting on directions.

Pseudo-convexity then becomes a property that controls how directional derivatives correlate with changes in the functional value, ensuring that stationary points are globally meaningful within the chosen constraints or feasible sets.

5.2 Generalized Notions (Dini/Directional Derivatives)

When differentiability is not available, pseudo-convexity is formulated using directional or Dini-type derivatives. A generalized definition typically requires that if certain directional derivatives at \(x\) are nonnegative, then the functional cannot decrease when moving to \(y\). These definitions preserve the logical structure of the differentiable case, but with derivatives that can exist under weaker smoothness.

5.3 Connections to Monotonicity of Operators

Many variational problems can be written in terms of operator inclusions, where one seeks \(x\) satisfying a condition involving an operator \(T\). Connections to monotonicity arise because pseudo-convexity can imply sign-consistent behavior of gradients or subgradients, which is closely related to monotone operator properties.

In these formulations, pseudo-convexity can serve as a bridge between optimization (minimizing functionals) and variational inequalities (solving inequalities involving operators).

5.4 Implications for Existence and Uniqueness of Minimizers

Pseudo-convexity alone typically guarantees global minimality of stationary points, not existence or uniqueness. Existence is influenced by coercivity, lower semicontinuity, and compactness-like conditions, while uniqueness depends on stronger properties such as strict variants or additional curvature.

Nevertheless, pseudo-convexity can simplify the optimization landscape analysis: once a candidate minimizer is identified through first-order information, the global conclusion is often immediate under suitable assumptions.

6 Further Developments

Research directions include strict versions, extensions to equilibrium and saddle-point settings, and links to algorithmic convergence. These variants tailor the pseudo-convex mechanism to different problem classes.

Strict pseudo-convexity strengthens the implication so that non-improvement corresponds to strict gradient conditions. For example, one may require that \[ \nabla f(x)\cdot (y-x)>0 \Rightarrow f(y)>f(x) \] or analogous formulations. Such strictness can improve uniqueness guarantees: if strict pseudo-convexity holds, then stationary points can become unique minimizers under standard regularity assumptions.

Related variants adapt pseudo-convexity to equality constraints, to local domains, or to derivative notions in nonsmooth analysis.

6.2 Pseudo-convexity in Saddle-Point and Equilibrium Problems

Equilibrium problems and saddle-point formulations involve two players or competing objectives, often expressed as finding \(x\) that satisfies an inequality system. Pseudo-convexity concepts are adapted to ensure that equilibrium conditions (which can look like stationarity with sign restrictions) imply global solution properties.

In these settings, “pseudo-convexity-like” assumptions may apply to merit functions, gap functions, or appropriate scalarizations of the equilibrium problem.

6.3 Links to Pseudo-monotonicity and Complementarity Systems

Complementarity systems and variational inequalities frequently rely on monotonicity concepts such as pseudo-monotonicity. Pseudo-monotonicity is closely related in spirit to pseudo-convexity: it ensures that an operator failing a certain inner-product inequality cannot correspond to an improving direction for the associated problem.

These links are valuable because they allow one to transport global existence and convergence arguments between optimization-like and equilibrium-like formulations.

6.4 Role in Algorithmic Convergence Guarantees

Pseudo-convexity is often used to justify why simple descent methods terminate at a globally optimal point rather than merely a local one.

6.4.1 Gradient Methods and Global Convergence

For unconstrained problems, a typical convergence argument goes: if an algorithm produces a limit point that is stationary, then pseudo-convexity implies that point is globally optimal. As a result, convergence analyses that stop at stationarity can be upgraded to global optimality claims.

The exact requirements vary with the algorithm (line search rules, step-size rules, and regularity), but pseudo-convexity reduces the gap between “first-order convergence” and “global solution.”

6.4.2 Constrained Descent Methods under Pseudo-convexity

In constrained optimization, constrained gradient-type methods may generate feasible iterates or manage feasibility through projection or penalty mechanisms. When pseudo-convexity assumptions align with the KKT structure, convergence to a point satisfying KKT conditions can be strengthened to global optimality of that feasible limit.

Thus, pseudo-convexity functions as a theoretical lever: it turns KKT satisfaction into a guarantee that no other feasible point can yield a lower objective value.