Quasiconvex function

{{Short description|Mathematical function with convex lower level sets}}

{{for|the unrelated generalization of convexity used in the calculus of variations|Quasiconvexity (calculus of variations)}}

File:Quasiconvex function.png

File:Nonquasiconvex function.png

File:standard deviation diagram.svg of the normal distribution is quasiconcave but not concave.]]

File:Multivariate Gaussian.png joint density is quasiconcave.]]

In mathematics, a quasiconvex function is a real-valued function defined on an interval or on a convex subset of a real vector space such that the inverse image of any set of the form $(-\infty,a)$ is a convex set. For a function of a single variable, along any stretch of the curve the highest point is one of the endpoints. The negative of a quasiconvex function is said to be quasiconcave.

Quasiconvexity is a more general property than convexity in that all convex functions are also quasiconvex, but not all quasiconvex functions are convex. Univariate unimodal functions are quasiconvex or quasiconcave, however this is not necessarily the case for functions with multiple arguments. For example, the 2-dimensional Rosenbrock function is unimodal but not quasiconvex and functions with star-convex sublevel sets can be unimodal without being quasiconvex.

Definition and properties

A function $f:S \to \mathbb{R}$ defined on a convex subset $S$ of a real vector space is quasiconvex if for all $x, y \in S$ and $\lambda \in [0,1]$ we have

: $f(\lambda x + (1 - \lambda)y)\leq\max\big\{f(x),f(y)\big\}.$

In words, if $f$ is such that it is always true that a point directly between two other points does not give a higher value of the function than both of the other points do, then $f$ is quasiconvex. Note that the points $x$ and $y$ , and the point directly between them, can be points on a line or more generally points in n-dimensional space.

File:Monotonicity example2.png

File:Quasi-concave-function-graph.png

An alternative way (see introduction) of defining a quasi-convex function $f(x)$ is to require that each sublevel set

$S_\alpha(f) = \{x\mid f(x) \leq \alpha\}$

is a convex set.

If furthermore

: $f(\lambda x + (1 - \lambda)y)<\max\big\{f(x),f(y)\big\}$

for all $x \neq y$ and $\lambda \in (0,1)$ , then $f$ is strictly quasiconvex. That is, strict quasiconvexity requires that a point directly between two other points must give a lower value of the function than one of the other points does.

A quasiconcave function is a function whose negative is quasiconvex, and a strictly quasiconcave function is a function whose negative is strictly quasiconvex. Equivalently a function $f$ is quasiconcave if

: $f(\lambda x + (1 - \lambda)y)\geq\min\big\{f(x),f(y)\big\}.$

and strictly quasiconcave if

: $f(\lambda x + (1 - \lambda)y)>\min\big\{f(x),f(y)\big\}$

A (strictly) quasiconvex function has (strictly) convex lower contour sets, while a (strictly) quasiconcave function has (strictly) convex upper contour sets.

A function that is both quasiconvex and quasiconcave is quasilinear.

A particular case of quasi-concavity, if $S \subset \mathbb{R}$ , is unimodality, in which there is a locally maximal value.

Applications

Quasiconvex functions have applications in mathematical analysis, in mathematical optimization, and in game theory and economics.

=Mathematical optimization=

In nonlinear optimization, quasiconvex programming studies iterative methods that converge to a minimum (if one exists) for quasiconvex functions. Quasiconvex programming is a generalization of convex programming.{{harvtxt|Di Guglielmo|1977|pp=287–288}}: {{cite journal

| last=Di Guglielmo | first=F.

| title=Nonconvex duality in multiobjective optimization

| doi=10.1287/moor.2.3.285

| volume=2

| year=1977

| number=3

| pages=285–291

| journal=Mathematics of Operations Research

| mr=484418

| jstor=3689518}} Quasiconvex programming is used in the solution of "surrogate" dual problems, whose biduals provide quasiconvex closures of the primal problem, which therefore provide tighter bounds than do the convex closures provided by Lagrangian dual problems.{{cite book|last=Di Guglielmo|first=F.|chapter=Estimates of the duality gap for discrete and quasiconvex optimization problems|title=Generalized concavity in optimization and economics: Proceedings of the NATO Advanced Study Institute held at the University of British Columbia, Vancouver, B.C., August 4–15, 1980

|editor1-first=Siegfried|editor1-last=Schaible|editor2-first=William T.|editor2-last=Ziemba|publisher=Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]|location=New York|year=1981|pages=281–298|isbn=0-12-621120-5|mr=652702}} In theory, quasiconvex programming and convex programming problems can be solved in reasonable amount of time, where the number of iterations grows like a polynomial in the dimension of the problem (and in the reciprocal of the approximation error tolerated);{{cite journal|last=Kiwiel|first=Krzysztof C.|title=Convergence and efficiency of subgradient methods for quasiconvex minimization|journal=Mathematical Programming, Series A|publisher=Springer|location=Berlin, Heidelberg|issn=0025-5610|pages=1–25|volume=90|issue=1|doi=10.1007/PL00011414|year=2001|mr=1819784|s2cid=10043417 }} Kiwiel acknowledges that Yuri Nesterov first established that quasiconvex minimization problems can be solved efficiently. however, such theoretically "efficient" methods use "divergent-series" step size rules, which were first developed for classical subgradient methods. Classical subgradient methods using divergent-series rules are much slower than modern methods of convex minimization, such as subgradient projection methods, bundle methods of descent, and nonsmooth filter methods.

=Economics and partial differential equations: Minimax theorems=

In microeconomics, quasiconcave utility functions imply that consumers have convex preferences. Quasiconvex functions are important

also in game theory, industrial organization, and general equilibrium theory, particularly for applications of Sion's minimax theorem. Generalizing a minimax theorem of John von Neumann, Sion's theorem is also used in the theory of partial differential equations.

Preservation of quasiconvexity

=Operations preserving quasiconvexity=

maximum of quasiconvex functions (i.e. $f = \max \left\lbrace f_1 , \ldots , f_n \right\rbrace$ ) is quasiconvex. Similarly, maximum of strict quasiconvex functions is strict quasiconvex.{{cite thesis

| degree=MSc

| last1=Johansson | first1=Edvard

| last2=Petersson | first2=David

| title=Parameter Optimization for Equilibrium Solutions of Mass Action Systems

| date=2016

| pages=13–14

| url=https://lup.lub.lu.se/student-papers/search/publication/8892543

|access-date=26 October 2016}} Similarly, the minimum of quasiconcave functions is quasiconcave, and the minimum of strictly-quasiconcave functions is strictly-quasiconcave.

composition with a non-decreasing function : $g : \mathbb{R}^{n} \rightarrow \mathbb{R}$ quasiconvex, $h : \mathbb{R} \rightarrow \mathbb{R}$ non-decreasing, then $f = h \circ g$ is quasiconvex. Similarly, if $g : \mathbb{R}^{n} \rightarrow \mathbb{R}$ quasiconcave, $h : \mathbb{R} \rightarrow \mathbb{R}$ non-decreasing, then $f = h \circ g$ is quasiconcave.
minimization (i.e. $f(x,y)$ quasiconvex, $C$ convex set, then $h(x) = \inf_{y \in C} f(x,y)$ is quasiconvex)

=Operations not preserving quasiconvexity=

The sum of quasiconvex functions defined on the same domain need not be quasiconvex: In other words, if $f(x), g(x)$ are quasiconvex, then $(f+g)(x) = f(x) + g(x)$ need not be quasiconvex.
The sum of quasiconvex functions defined on different domains (i.e. if $f(x), g(y)$ are quasiconvex, $h(x,y) = f(x) + g(y)$ ) need not be quasiconvex. Such functions are called "additively decomposed" in economics and "separable" in mathematical optimization.

Examples

Every convex function is quasiconvex.
A concave function can be quasiconvex. For example, $x \mapsto \log(x)$ is both concave and quasiconvex.
Any monotonic function is both quasiconvex and quasiconcave. More generally, a function which decreases up to a point and increases from that point on is quasiconvex (compare unimodality).
The floor function $x\mapsto \lfloor x\rfloor$ is an example of a quasiconvex function that is neither convex nor continuous.

References

Avriel, M., Diewert, W.E., Schaible, S. and Zang, I., Generalized Concavity, Plenum Press, 1988.
{{cite book|last=Crouzeix|first=J.-P.|chapter=Quasi-concavity|title=The New Palgrave Dictionary of Economics|editor-first=Steven N.|editor-last=Durlauf|editor2-first=Lawrence E|editor2-last=Blume|publisher=Palgrave Macmillan|year=2008|edition=Second|pages=815–816|url=http://www.dictionaryofeconomics.com/article?id=pde2008_Q000008|doi=10.1057/9780230226203.1375|isbn=978-0-333-78676-5}}
Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp. {{ISBN|0-471-16015-6}}

External links

[http://projecteuclid.org/euclid.pjm/1103040253 SION, M., "On general minimax theorems", Pacific J. Math. 8 (1958), 171-176.]
[http://glossary.computing.society.informs.org/second.php Mathematical programming glossary]
[http://homepages.nyu.edu/~caw1/UMath/Handouts/ums11h22convexsetsandfunctions.pdf Concave and Quasi-Concave Functions] - by Charles Wilson, NYU Department of Economics
[http://www.economics.utoronto.ca/osborne/MathTutorial/QCC.HTM Quasiconcavity and quasiconvexity] - by Martin J. Osborne, University of Toronto Department of Economics

Category:Convex analysis

Category:Convex optimization

Category:Generalized convexity

Category:Real analysis

Category:Types of functions