Pseudoconvex function
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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
edit edit sourceConsider a differentiable function f:X⊆ℝn→ℝ, defined on a (nonempty) convex open set X of the finite-dimensional Euclidean space ℝn. This function is said to be pseudoconvex if the following property holds:[1]
- for all x,y∈X:∇f(x)⋅(y−x)≥0⇒f(y)≥f(x).
Equivalently:
- for all x,y∈X:f(y)<f(x)⇒∇f(x)⋅(y−x)<0.
Here ∇f is the gradient of f, defined by: ∇f=(∂f∂x1,…,∂f∂xn).
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:
- ∂f∂v(x)=∇f(x)⋅v=∇f(x)⋅(y−x).
Properties
edit edit sourceRelation to other types of "convexity"
edit edit sourceEvery convex function is pseudoconvex, but the converse is not true. For example, the function f(x)=x+x3 is pseudoconvex but not convex. Similarly, any pseudoconvex function is quasiconvex; but the converse is not true, since the function f(x)=x3 is quasiconvex but not pseudoconvex. This can be summarized schematically as:
- convex ⇒ pseudoconvex ⇒ quasiconvex
To see that f(x)=x3 is not pseudoconvex, consider its derivative at x=0: f′(0)=0. Then, if f(x)=x3 was pseudoconvex, we should have:
- f′(0)(y−0)=0≥0⇒f(y)≥f(0),∀y∈ℝ.
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
edit edit sourceFor 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: ∇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:[2] 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:
- f(x)=exx2+1+1ex.
This function is not pseudoconvex, but it is quasiconvex. Also, the point x=0 is a critical point of f, as f′(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)=x3+x, whose derivative is always positive: f′(x)=3x2+1>0,∀x∈ℝ.
Examples
edit edit sourceAn example of a function that is pseudoconvex, but not convex, is: f(x)=x2x2+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)=x2+y2x2+y2+k,k>0.
The previous example may be modified to obtain a function that is not convex, nor pseudoconvex, but is quasiconvex:
- f(x)=|x|p|x|p+k,k>0,p∈(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.
Generalization to nondifferentiable functions
edit edit sourceThe notion of pseudoconvexity can be generalized to nondifferentiable functions as follows.[3] Given any function f:X→ℝ, we can define the upper Dini derivative of f by:
- f+(x,u)=lim suph→0+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 ∂f as follows:
- For all x,y∈X: if x∗∈∂f(x) is such that ⟨x∗,y−x⟩≥0, then f(x)≤f(z), for all z∈[x,y];
where [x,y] denotes the line segment adjoining x and y.
Related notions
edit edit sourceA pseudoconcave function is a function whose negative is pseudoconvex. A pseudolinear function is a function that is both pseudoconvex and pseudoconcave.[4] 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).[5][6][7]
Given a vector-valued function η, there is a more general notion of η-pseudoconvexity[8][9] and η-pseudolinearity; wherein classical pseudoconvexity and pseudolinearity pertain to the case when η(x,y)=y−x.
See also
edit edit sourceNotes
edit edit source- ^ Mangasarian 1965
- ^ Mangasarian 1965
- ^ Floudas & Pardalos 2001
- ^ Rapcsak 1991
- ^ Chapter five: Craven, B. D. (1988). Fractional programming. Sigma Series in Applied Mathematics. Vol. 4. Berlin: Heldermann Verlag. p. 145. ISBN 3-88538-404-3. MR 0949209.
- ^ Kruk, Serge; Wolkowicz, Henry (1999). "Pseudolinear programming". SIAM Review. 41 (4): 795–805. Bibcode:1999SIAMR..41..795K. doi:10.1137/S0036144598335259. JSTOR 2653207. MR 1723002.
- ^ Mathis, Frank H.; Mathis, Lenora Jane (1995). "A nonlinear programming algorithm for hospital management". SIAM Review. 37 (2): 230–234. doi:10.1137/1037046. JSTOR 2132826. MR 1343214. S2CID 120626738.
- ^ Ansari, Qamrul Hasan; Lalitha, C. S.; Mehta, Monika (2013). Generalized Convexity, Nonsmooth Variational Inequalities, and Nonsmooth Optimization. CRC Press. p. 107. ISBN 9781439868218. Retrieved 15 July 2019.
- ^ Mishra, Shashi K.; Giorgi, Giorgio (2008). Invexity and Optimization. Springer Science & Business Media. p. 39. ISBN 9783540785613. Retrieved 15 July 2019.
References
edit edit source- 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..
- 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1318719908 under CC BY-SA 4.0; modifications have been made.