Quasiconvex function
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a quasiconvex function is a real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

-valued function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 defined on an interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

 or on a convex subset
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

 of a real vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

 such that the inverse image of any set of the form is a convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

. Informally, after cutting off the top of the function and looking down at the remaining part of the domain, an observer always sees something that is convex.

All convex function
Convex function
In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...

s are also quasiconvex, but not all quasiconvex functions are convex, so quasiconvexity is a generalization of convexity. Quasiconvexity extends the notion of unimodality for 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 a value of the function than do both of the other points, 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 is to require that each sub-levelset

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 (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.

Applications

Quasiconvex functions have applications in mathematical analysis
Mathematical analysis
Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...

, in mathematical optimization, and in game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

 and economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...

.

Mathematical optimization

In nonlinear optimization
Nonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...

, quasiconvex programming studies iterative method
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...

s 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 problem
Dual problem
In constrained optimization, it is often possible to convert the primal problem to a dual form, which is termed a dual problem. Usually dual problem refers to the Lagrangian dual problem but other dual problems are used, for example, the Wolfe dual problem and the Fenchel dual problem...

s, 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
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...

, 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 method
Subgradient method
Subgradient methods are iterative methods for solving convex minimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function...

s. 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
Microeconomics
Microeconomics is a branch of economics that studies the behavior of how the individual modern household and firms make decisions to allocate limited resources. Typically, it applies to markets where goods or services are being bought and sold...

, quasiconcave utility functions imply that consumers have convex preferences
Convex preferences
In economics, convex preferences refer to a property of an individual's ordering of various outcomes which roughly corresponds to the idea that "averages are better than the extremes"...

. Quasiconvex functions are important
also in game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

, industrial organization
Industrial organization
Industrial organization is the field of economics that builds on the theory of the firm in examining the structure of, and boundaries between, firms and markets....

, and general equilibrium theory, particularly for applications of Sion's minimax theorem
Sion's minimax theorem
In mathematics, and in particular game theory, Sion's minimax theorem is a generalization of John von Neumann's minimax theorem.It states:Let X be a compact convex subset of a linear topological space and Y a convex subset of a linear topological space. If f is a real-valued function on X\times Y...

. Generalizing a minimax theorem of John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...

, Sion's theorem is also used in the theory of partial differential equation
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...

s.

Operations preserving quasiconvexity

  • non-negative weighted maximum of quasiconvex functions (i.e. with non-negative)
  • composition with a non-decreasing function (i.e. quasiconvex, non-decreasing, then is quasiconvex)
  • minimization (i.e. quasiconvex, convex set, then is quasiconvex)

Operations not preserving quasiconvexity

  • 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 (i.e. if are quasiconvex, ) need not be quasiconvex. Such functions are called "additively decomposed" in economics and "separable" in mathematical optimization.

In fact, if the sum of a finite set of (nonconstant) quasiconvex functions is quasiconvex, then all but either zero or one of the functions must be convex; this result holds for separable functions, in particular.

Examples

  • Every convex function is quasiconvex.
  • A concave function can be quasiconvex function. For example log(x) is concave, and it is quasiconvex.
  • Any monotonic function
    Monotonic function
    In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

     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
    Unimodality
    Unimodality is a term used in several contexts in mathematics. Originally, it relates to possessing a unique mode.- Unimodal probability distribution :...

    ).
  • The floor function
    Floor function
    In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively...

      is an example of a quasiconvex function that is neither convex nor continuous.
  • If f(x) and g(y) are positive convex decreasing functions, then is quasiconvex.

See also

  • Convex function
    Convex function
    In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...

  • Concave function
    Concave function
    In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...

  • Pseudoconvexity in the sense of several complex variables (not generalized convexity)
  • Pseudoconvex function
    Pseudoconvex function
    In convex analysis and the calculus of variations, 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...

  • Invex function
    Invex function
    In vector calculus, an invex function is a differentiable function ƒ from Rn to R for which there exists a vector valued function g such thatfor all x and u....


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK