Pseudoconvex function#pseudolinear function

Consider a differentiable function $f:X\; \backslash subseteq\; \backslash mathbb\{R\}^\{n\}\; \backslash rightarrow\; \backslash mathbb\{R\}$, defined on a (nonempty) convex open set $X$ of the finite-dimensional Euclidean space $\backslash mathbb\{R\}^n$. This function is said to be pseudoconvex if the following property holds:{{harvnb|Mangasarian|1965}}

{{Center| for all $x,y\; \backslash in\; X:\; \backslash quad\; \backslash nabla\; f(x)\; \backslash cdot\; (y-x)\; \backslash geq\; 0\; \backslash Rightarrow\; f(y)\; \backslash geq\; f(x)$.}}

Equivalently:

{{Center| for all . }}

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

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

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:

{{Center| convex $\backslash Rightarrow$ pseudoconvex $\backslash Rightarrow$ quasiconvex }}

File:Pseudoquasiconvex.png

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

{{Center|$f^\{\backslash prime\}(0)\; (y-0)\; =\; 0\; \backslash geq\; 0\; \backslash Rightarrow\; f(y)\; \backslash geq\; f(0),\; \backslash quad\; \backslash forall\; \backslash ,\; y\; \backslash in\; \backslash mathbb\{R\}.$}}

In particular it should be true for $y=-1$. But it is not, as: .

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: $\backslash 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:{{harvnb|Mangasarian|1965}} 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:

{{Center|$f(x)=\backslash frac\{e^\{x\}\}\{x^\{2\}+1\}\; +\; \backslash frac\{1\}\{e^\{x\}\}$.}}

This function is not pseudoconvex, but it is quasiconvex. Also, the point $x=0$ is a critical point of $f$, as $f^\{\backslash prime\}(0)=0$. However, $f$ does not have a global minimum at $x=0$ (not even a local minimum).

File:Quasiconvex optimality.png

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^\{\backslash prime\}(x)=3x^\{2\}+1>0,\; \backslash ,\; \backslash forall\; \backslash ,\; x\; \backslash in\; \backslash mathbb\{R\}$.

An example of a function that is pseudoconvex, but not convex, is: $f(x)=\backslash frac\{x^\{2\}\}\{x^\{2\}+k\},\; \backslash ,\; k\; >\; 0.$ The figure shows this function for the case where $k=0.2$. This example may be generalized to two variables as:

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

File:Pseudoconvex.png

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

{{Center|$f(x)=\backslash frac\{|x|^\{p\}\}\{|x|^\{p\}+k\},\; \backslash ,\; k\; >\; 0,\; \backslash ,\; p\; \backslash 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$.

File:Quasiconvex.png

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

{{Center|$f^\{+\}(x,u)\; =\; \backslash limsup\_\{\; h\; \backslash to\; 0^\{+\}\; \}\; \backslash 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 $\backslash partial\; f$ as follows:

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

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

A {{visible anchor|pseudoconcave function}} is a function whose negative is pseudoconvex. A {{visible anchor|pseudolinear function}} is a function that is both pseudoconvex and pseudoconcave.{{harvnb|Rapcsak|1991}} 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).

Chapter five: {{cite book| last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|location=Berlin|year=1988|pages=145|isbn=3-88538-404-3 |mr=949209}}{{cite journal | last1=Kruk | first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming |journal=SIAM Review|volume=41 |year=1999 |number=4 |pages=795–805 |mr=1723002 | jstor = 2653207 |doi=10.1137/S0036144598335259| bibcode=1999SIAMR..41..795K}}

{{cite journal | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management |journal=SIAM Review|volume=37 |year=1995 |number=2 |pages=230–234|mr=1343214 | jstor = 2132826 |doi=10.1137/1037046|s2cid=120626738 }}

Given a vector-valued function $\backslash eta$, there is a more general notion of $\backslash eta$-pseudoconvexity{{cite book |last1=Ansari |first1=Qamrul Hasan |last2=Lalitha |first2=C. S. |last3=Mehta |first3=Monika |title=Generalized Convexity, Nonsmooth Variational Inequalities, and Nonsmooth Optimization |date=2013 |publisher=CRC Press |isbn=9781439868218 |page=107 |url=https://books.google.com/books?id=3qzMBQAAQBAJ&q=pseudolinearity&pg=PA107 |access-date=15 July 2019 |language=en}}{{cite book |last1=Mishra |first1=Shashi K. |last2=Giorgi |first2=Giorgio |title=Invexity and Optimization |date=2008 |publisher=Springer Science & Business Media |isbn=9783540785613 |page=39 |url=https://books.google.com/books?id=SDbS50KIQGIC&q=pseudolinearity&pg=PA39 |access-date=15 July 2019 |language=en}} and $\backslash eta$-pseudolinearity; wherein classical pseudoconvexity and pseudolinearity pertain to the case when $\backslash eta\; (x,\; y)\; =\; y\; -\; x$.

• Pseudoconvexity
• Convex function
• Quasiconvex function
• Invex function

{{reflist}}

• {{citation|authorlink1=Christodoulos Floudas|first1=Christodoulos A.|last1=Floudas|first2=Panos M.|last2=Pardalos|title=Encyclopedia of Optimization|chapter=Generalized monotone multivalued maps|publisher=Springer|year=2001|isbn=978-0-7923-6932-5|page=227}}.
• {{cite journal|title=Pseudo-Convex Functions|journal= Journal of the Society for Industrial and Applied Mathematics, Series A: Control|volume=3|issue=2|pages=281–290 |date=January 1965|doi=10.1137/0303020|first=O. L.|last=Mangasarian|issn=0363-0129}}.
• {{cite journal|first=T.|last=Rapcsak|title=On pseudolinear functions|journal=European Journal of Operational Research|volume=50|issue=3|date=1991-02-15|pages=353–360|issn=0377-2217|doi=10.1016/0377-2217(91)90267-Y}}

{{Convex analysis and variational analysis}}

Category:Convex analysis

Category:Convex optimization

Category:Generalized convexity

Category:Types of functions