![]() | ||
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
Contents
- Definition and properties
- Applications
- Mathematical optimization
- Economics and partial differential equations Minimax theorems
- Operations preserving quasiconvexity
- Operations not preserving quasiconvexity
- Examples
- References
All convex functions are also quasiconvex, but not all quasiconvex functions are convex, so quasiconvexity is a generalization of convexity. Quasiconvexity and quasiconcavity extend to functions with multiple arguments the notion of unimodality of functions with a single real argument.
Definition and properties
A function
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.
An alternative way (see introduction) of defining a quasi-convex function
If furthermore
for all
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
and strictly quasiconcave if
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
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. 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. 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); however, such theoretically "efficient" methods use "divergent-series" stepsize 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.