Pseudoconvex function explained

In convex analysis and the calculus of variations, both branches of mathematics, a pseudoconvex function is a function that behaves like a convex function with respect to finding its local minima, but need not actually be convex. Informally, a differentiable function is pseudoconvex if it is increasing in any direction where it has a positive directional derivative. The property must hold in all of the function domain, and not only for nearby points.

Formal definition

Consider a differentiable function

f:X \subseteq R ^{n} → R , defined on a (nonempty) convex open set X of the finite-dimensional Euclidean space R ^{n} . This function is said to be pseudoconvex if the following property holds:

Equivalently:

Here

\nabla f is the gradient of f , defined by: \nabla f = \left( (\partial f)/(, ... , \partial x _{1}) (\partial f)/(\partial x _{n}) \right).

Note that the definition may also be stated in terms of the directional derivative of

f , in the direction given by the vector v = y - x . This is because, as f is differentiable, this directional derivative is given by:

Properties

Relation to other types of "convexity"

Every convex function is pseudoconvex, but the converse is not true. For example, the function

f(x) = x + x ^{3} is pseudoconvex but not convex. Similarly, any pseudoconvex function is quasiconvex; but the converse is not true, since the function f(x) = x ^{3} is quasiconvex but not pseudoconvex. This can be summarized schematically as:

To see that

f(x) = x ^{3} is not pseudoconvex, consider its derivative at x = 0 : f ^{\prime} ( 0 ) = 0 . Then, if f(x) = x ^{3} was pseudoconvex, we should have:

In particular it should be true for

y =-1 . But it is not, as: f( -1 ) = ( -1 ) ^{3} = -1 < f( 0 ) = 0 .

Sufficient optimality condition

For any differentiable function, we have the Fermat's theorem necessary condition of optimality, which states that: if

f has a local minimum at x ^{*} in an open domain, then x ^{*} must be a stationary point of f (that is: \nabla f(x ^{*} ) = 0 ).

Pseudoconvexity is of great interest in the area of optimization, because the converse is also true for any pseudoconvex function. That is: if

x ^{*} is a stationary point of a pseudoconvex function f , then f has a global minimum at x ^{*} . Note also that the result guarantees a global minimum (not only local).

This last result is also true for a convex function, but it is not true for a quasiconvex function. Consider for example the quasiconvex function:

This function is not pseudoconvex, but it is quasiconvex. Also, the point

x =0 is a critical point of f , as f ^{\prime} ( 0 ) =0 . However, f does not have a global minimum at x =0 (not even a local minimum).

Finally, note that a pseudoconvex function may not have any critical point. Take for example the pseudoconvex function:

f(x) = x ^{3} + x , whose derivative is always positive: f ^{\prime} (x) =3 x ^{2} +1 > 0 , \forall x \in R .

Examples

An example of a function that is pseudoconvex, but not convex, is:

f(x) = (x ^{2})/(x ^{2} + k) , k > 0 . The figure shows this function for the case where k =0 . 2 . This example may be generalized to two variables as:

The previous example may be modified to obtain a function that is not convex, nor pseudoconvex, but is quasiconvex:

The figure shows this function for the case where

k =0 . 5 , p =0 . 6 . As can be seen, this function is not convex because of the concavity, and it is not pseudoconvex because it is not differentiable at x =0 .

Generalization to nondifferentiable functions

The notion of pseudoconvexity can be generalized to nondifferentiable functions as follows. Given any function

f:X → R , we can define the upper Dini derivative of f by:\partial f as follows:

where

[x,y] denotes the line segment adjoining x and y.

Related notions

A is a function whose negative is pseudoconvex. A is a function that is both pseudoconvex and pseudoconcave. For example, linear–fractional programs have pseudolinear objective functions and linear–inequality constraints. These properties allow fractional-linear problems to be solved by a variant of the simplex algorithm (of George B. Dantzig).^{[1] [2] [3]}

Given a vector-valued function

η , there is a more general notion of η -pseudoconvexity^{[4] [5]} and η -pseudolinearity; wherein classical pseudoconvexity and pseudolinearity pertain to the case when η (x, y) = y - x .

See also

• Pseudoconvexity
• Convex function
• Quasiconvex function
• Invex function

References

• .
• Pseudo-Convex Functions. Journal of the Society for Industrial and Applied Mathematics, Series A. 3. 2. 281 - 290 . January 1965. 10.1137/0303020. O. L.. Mangasarian. 0363-0129. .
• T.. Rapcsak. On pseudolinear functions. European Journal of Operational Research. 50. 3. 1991-02-15. 353 - 360. 0377-2217. 10.1016/0377-2217(91)90267-Y.

Notes and References

1. Chapter five: Book: Craven, B. D.. Fractional programming. Sigma Series in Applied Mathematics. 4. Heldermann Verlag. Berlin. 1988. 145. 3-88538-404-3 . 949209.
2. Kruk . Serge. Wolkowicz. Henry. Pseudolinear programming . SIAM Review. 41 . 1999 . 4 . 795–805 . 1723002 . 2653207 . 10.1137/S0036144598335259. 1999SIAMR..41..795K.
3. Mathis. Frank H.. Mathis. Lenora Jane. A nonlinear programming algorithm for hospital management . SIAM Review. 37 . 1995 . 2 . 230–234. 1343214 . 2132826 . 10.1137/1037046. 120626738 .
4. Book: Ansari . Qamrul Hasan . Lalitha . C. S. . Mehta . Monika . Generalized Convexity, Nonsmooth Variational Inequalities, and Nonsmooth Optimization . 2013 . CRC Press . 9781439868218 . 107 . 15 July 2019 . en.
5. Book: Mishra . Shashi K. . Giorgi . Giorgio . Invexity and Optimization . 2008 . Springer Science & Business Media . 9783540785613 . 39 . 15 July 2019 . en.