Quasiconvex function

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, the objective f is quasiconvex if and only if the maximum of f along a straight line between any two end points is never greater than the value at the higher endpoint. Note that the points x and y may be points in n-dimensional space. If the inequality is strict, i.e. : f(\lambda x + (1 - \lambda)y) 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. 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. It follows that for every strictly quasiconvex function, there exist a strictly monotone increasing coordinate transformation m:\mathbb{R}\to\mathbb{R} such that m(f(x)) is strictly convex. 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 and only if : f(\lambda x + (1 - \lambda)y)\geq\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. Unimodal probability distributions like the Gaussian distribution are common examples of quasi-concave functions that are not concave. A function that is both quasiconvex and quasiconcave is quasilinear, and satisfies : \min\big\{f(x),f(y)\big\} \leq f(\lambda x + (1 - \lambda)y)\leq\max\big\{f(x),f(y)\big\} For a quasilinear function defined on a plane, the level sets are always lines. More generally, the level sets of a quasilinear function over \mathbb{R}^n are n-1-dimensional planes. ==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.: {{cite journal 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 • 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. For example, \pm \operatorname{sign}(x \pm 1) are quasiconvex (in fact, quasilinear) functions whose sum is not 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. For example, f(x) = -x^2 defined for positive x > 0 is quasiconvex, but h(x, y) = f(x) + f(y) is not quasiconvex on the positive orthant. ==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. ==See also==