Pseudoconvex function

This article is about the notion in convex analysis. For the notion in several complex variables, see pseudoconvex domain.

In convex analysis and the calculus of variations, 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 \mathbb {R} ^{n}\rightarrow \mathbb {R}$, defined on a (nonempty) convex open set $X$ of the finite-dimensional Euclidean space $\mathbb {R} ^{n}$. This function is said to be pseudoconvex if the following property holds:

for all $x,y\in X:\quad \nabla f(x)\cdot (y-x)\geq 0\Rightarrow f(y)\geq f(x)$.

Equivalently:

for all $x,y\in X:\quad f(y)<f(x)\Rightarrow \nabla f(x)\cdot (y-x)<0$.

Here $\nabla f$ is the gradient of $f$, defined by: $\nabla f=\left({\frac {\partial f}{\partial x_{1}}},\dots ,{\frac {\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:

${\frac {\partial f}{\partial v}}(x)=\nabla f(x)\cdot v=\nabla f(x)\cdot (y-x).$

Properties

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:

convex $\Rightarrow$ pseudoconvex $\Rightarrow$ quasiconvex

Pseudoconvexity is primarily of interest in optimization because of the following result: $x^{*}$ is a local minimum of a pseudoconvex function $f$ if and only if it is a stationary point of $f$; which is to say that the gradient of $f$ vanishes at $x^{*}$: $\nabla f(x^{*})=0.$

Examples

An example of a function that is pseudoconvex, but not convex, is: $f(x)={\frac {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:

$f(x)={\frac {x^{2}+y^{2}}{x^{2}+y^{2}+k}},\,k>0.$

Pseudoconvex function that is not convex. Made with geogebra.

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

$f(x)={\frac {|x|^{p}}{|x|^{p}+k}},\,k>0,\,p\in (0,1).$

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$.

Quasiconvex function that is not convex, nor pseudoconvex. Made with geogebra.

Generalization to nondifferentiable functions

The notion of pseudoconvexity can be generalized to nondifferentiable functions as follows. Given any function $f:X\rightarrow \mathbb {R}$, we can define the upper Dini derivative of $f$ by:

$f^{+}(x,u)=\limsup _{h\to 0^{+}}{\frac {f(x+hu)-f(x)}{h}};$

where u is any unit vector. The function is said to be pseudoconvex if it is increasing in any direction where the upper Dini derivative is positive. More precisely, this is characterized in terms of the subdifferential $\partial f$ as follows:

For all $x,y\in X$: if $x\in \partial f(x)$ is such that $\langle x^{*},y-x\rangle \geq 0$, then $f(x)\leq f(z)$, for all $z\in [x,y]$;

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

Related notions

A pseudoconcave function is a function whose negative is pseudoconvex. A pseudolinear function 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).

Given a vector-valued function $\eta$, there is a more general notion of $\eta$-pseudoconvexity and $\eta$-pseudolinearity; wherein classical pseudoconvexity and pseudolinearity pertain to the case when $\eta (x,y)=y-x$.

See also

• Pseudoconvexity
• Convex function
• Quasiconvex function

References

• Floudas, Christodoulos A.; Pardalos, Panos M. (2001), "Generalized monotone multivalued maps", Encyclopedia of Optimization, Springer, p. 227, ISBN 978-0-7923-6932-5.
• Mangasarian, O. L. (January 1965). "Pseudo-Convex Functions". Journal of the Society for Industrial and Applied Mathematics Series A Control. 3 (2): 281–290. doi:10.1137/0303020. ISSN 0363-0129. {{cite journal}}: Invalid |ref=harv (help).
• Rapcsak, T. (1991-02-15). "On pseudolinear functions". European Journal of Operational Research. 50 (3): 353–360. doi:10.1016/0377-2217(91)90267-Y. ISSN 0377-2217. {{cite journal}}: Invalid |ref=harv (help)