Convex function

From Wikipedia, the free encyclopedia

In mathematics, a real-valued function f defined on an interval (or on any convex subset of some vector space) is called convex, or concave up, if for any two points x and y in its domain C and any t in [0,1], we have

<math>f(tx+(1-t)y)\leq t f(x)+(1-t)f(y).</math>

In other words, a function is convex if and only if its epigraph (the set of points lying on or above the graph) is a convex set.

A function is called strictly convex if

<math>f(tx+(1-t)y) < t f(x)+(1-t)f(y)\,</math>

for any t in (0,1) and <math>x \neq y.</math>

A function <math>f </math> is said to be concave if <math> - f </math> is convex.

[edit] Properties

A convex function f defined on some open interval C is continuous on C and differentiable at all but at most countably many points. If C is closed, then f may fail to be continuous at the endpoints of C.

A continuous function on an interval C is convex if and only if

<math>f\left( \frac{x+y}{2} \right) \le \frac{f(x)+f(y)}{2}</math>

for all x and y in C.

A differentiable function of one variable is convex on an interval if and only if its derivative is monotonically non-decreasing on that interval.

A continuously differentiable function of one variable is convex on an interval if and only if the function lies above all of its tangents: f(y) ≥ f(x) + f '(x) (y − x) for all x and y in the interval. In particular, if f '(c) = 0, then c is a global minimum of f(x).

A twice differentiable function of one variable is convex on an interval if and only if its second derivative is non-negative there; this gives a practical test for convexity. If its second derivative is positive then it is strictly convex, but the converse does not hold, as shown by f(x) = x⁴.

More generally, a continuous, twice differentiable function of several variables is convex on a convex set if and only if its Hessian matrix is positive semidefinite on the interior of the convex set.

Any local minimum of a convex function is also a global minimum. A strictly convex function will have at most one global minimum.

For a convex function f, the sublevel sets {x | f(x) < a} and {x | f(x) ≤ a} with a ∈ R are convex sets. However, a function whose sublevel sets are convex sets may fail to be a convex function; such a function is called a quasiconvex function.

Jensen's inequality applies to all convex functions. If <math> x </math> is random, taking values in some domain <math> \mathcal{F} </math>, then <math>E f(x) \geq f(Ex). </math>

[edit] Convex function calculus

• If <math>f </math> and <math>g </math> are convex functions, then so are <math>h(x) = \max\{f(x),g(x) \} </math> and <math>h(x) = f(x) + g(x) .</math>
• If <math>f </math> and <math>g </math> are convex functions and if <math>g</math> is increasing, then <math>h(x) = g(f(x))</math> is convex.
• Convexity is invariant under affine maps: that is, if <math>f(x) </math> is convex with <math>x\in\mathbb{R}^n</math>, then so is <math>g(y) = f(Ay+b) </math>, where <math>A\in\mathbb{R}^{n \times m},\; b\in\mathbb{R}^n.</math>
• If <math>f(x,y) </math> is convex in <math>(x,y) </math> and <math>C </math> is a convex nonempty set, then <math>g(x) = \inf_{y\in C} f(x,y)</math> is convex in <math>x, </math> provided <math>g(x) > -\infty</math> for some <math>x. </math>

[edit] Examples

• The second derivative of x² is 2; it follows that x² is a convex function of x.
• The absolute value function |x| is convex, even though it does not have a derivative at x = 0.
• The function f with domain [0,1] defined by f(0)=f(1)=1, f(x)=0 for 0<x<1 is convex; it is continuous on the open interval (0,1), but not continuous at 0 and 1.
• The function x³ has second derivative 6x; thus it is convex for x ≥ 0 and concave for x ≤ 0.
• Every linear transformation to <math>\mathbb{R}</math> is convex but not strictly convex, since if f is linear, then <math>f(a + b) = f(a) + f(b).</math> This statement still holds if we replace "convex" by "concave".
• An affine function to <math>\mathbb{R}</math>, i.e. a function of the form <math>f(x) = a^T x + b </math>, is simultaneously convex and concave.
• All norms are convex by the triangle inequality.
• If <math>f </math> is convex, the perspective function <math>g(x,t) = tf(x/t) </math> is convex for <math>t > 0. </math>
• Examples of functions that are monotonically increasing but not convex include <math>\sqrt x</math> and <math>\log(x).</math>
• Examples of functions that are convex but not monotonically increasing include x² and -x.
• The function f(x) = 1/x is convex on the interval (0,+∞), but not on the interval (-∞,+∞), because of the singularity at x = 0.

[edit] See also

• Convex optimization
• Geodesic convexity
• Kachurovskii's theorem, which relates convexity to monotonicity of the derivative
• Logarithmically convex function
• Quasiconvex function
• Subderivative of a convex function

[edit] References

• Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press. 

• Luenberger, David (1984). Linear and Nonlinear Programming. Addison-Wesley. 

• Luenberger, David (1969). Optimization by Vector Space Methods. Wiley & Sons. 

• Bertsekas, Dimitri (2003). Convex Analysis and Optimization. Athena Scientific. 

• Hiriart-Urruty, Jean-Baptiste, and Lemaréchal, Claude. (2004). Fundamentals of Convex analysis. Berlin: Springer.

• Krasnosel'skii M.A., Rutickii Ya.B. (1961). Convex Functions and Orlicz Spaces. Groningen: P.Noordhoff Ltd. 

• Borwein, Jonathan, and Lewis, Adrian. (2000). Convex Analysis and Nonlinear Optimization. Springer.

[edit] External links

• Stephen Boyd and Lieven Vandenberghe, Convex Optimization (PDF)
• Jon Dattorro, Convex Optimization & Euclidean Distance Geometrycs:Konvexnost a konkávnost funkce

de:Konvexe und konkave Funktionen fr:Fonction convexe it:Funzione convessa he:פונקציה קמורה hu:Konvex függvény ja:凸関数 pl:Wypukłość funkcji pt:Função convexa ru:Выпуклая функция fi:Konveksi funktio zh:凸函数