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 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. 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 defined on a convex subset S of a real vector space is quasiconvex if for all and we have 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 of defining a quasi-convex function is to require that each sublevel set is a convex set. If furthermore for all and, then 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 is quasiconcave if and strictly quasiconcave if A quasiconvex function has convex lower contour sets, while a quasiconcave function has convex upper contour sets. A function that is both quasiconvex and quasiconcave is quasilinear. A particular case of quasi-concavity, if, is unimodality, in which there is a locally maximal value.
In nonlinear optimization, quasiconvex programming studies iterative methods that converge to a minimum 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 ; 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.
maximum of quasiconvex functions is quasiconvex. Similarly, maximum of strict quasiconvex functions is strict quasiconvex. Similarly, the minimum of quasiconcave functions is quasiconcave, and the minimum of strictly-quasiconcave functions is strictly-quasiconcave.
The sum of quasiconvex functions defined on the same domain need not be quasiconvex: In other words, if are quasiconvex, then need not be quasiconvex.
The sum of quasiconvex functions defined on different domains need not be quasiconvex. Such functions are called "additively decomposed" in economics and "separable" in mathematical optimization.
A concave function can be quasiconvex function. For example is concave, and it is 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.
The floor function is an example of a quasiconvex function that is neither convex nor continuous.
