CONVEX FUNCTION

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
:$f(tx+(1-t)y)leq\; t\; f(x)+(1-t)f(y).$

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
:
for any ''t'' in (0,1) and $x$
eq y.
A function $f$ is said to be concave if $-\; f$ is convex.

Contents

Properties

Convex function calculus

Examples

Useful theorems

See also

References

External links

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
:
ight) le rac{f(x)+f(y)}{2}
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.
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 $x$ is random, taking values in some domain $mathcal\{F\}$, then $E\; f(x)\; geq\; f(Ex).$

Convex function calculus

★ If $f$ and $g$ are convex functions, then so are $h(x)\; =\; max\{f(x),g(x)\; \}$ and $h(x)\; =\; f(x)\; +\; g(x)\; .$

★ Convexity is invariant under affine maps: that is, if $f(x)$ is convex with $xinmathbb\{R\}^n$, then so is $g(y)\; =\; f(Ay+b)$, where $Ainmathbb\{R\}^\{n\; imes\; m\},;\; binmathbb\{R\}^n.$

★ If $f(x,y)$ is convex in $(x,y)$ and $C$ is a convex nonempty set, then $g(x)\; =\; inf\_\{yin\; C\}\; f(x,y)$ is convex in $x,$ provided $g(x)\; >\; -infty$ for some $x.$

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 6''x''; thus it is convex for ''x'' ≥ 0 and concave for ''x'' ≤ 0.

★ Every linear transformation to $mathbb\{R\}$ is convex but not strictly convex, since if ''f'' is linear, then $f(a\; +\; b)\; =\; f(a)\; +\; f(b).$ This statement still holds if we replace "convex" by "concave".

★ An affine function to $mathbb\{R\}$, i.e. a function of the form $f(x)\; =\; a^T\; x\; +\; b$, is simultaneously convex and concave.

★ All norms are convex by the triangle inequality.

★ If $f$ is convex, the ''perspective function'' $g(x,t)\; =\; tf(x/t)$ is convex for $t\; >\; 0.$

★ Examples of functions which are monotonically increasing but not convex include $sqrt\; x$ and $log(x).$

★ Examples of functions which 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.

Useful theorems

★ A differentiable function $f$ defined on an interval is convex ''if and only if'' its derivative ''f'(''x'') is monotone nondecreasing, i.e. $f^\text{'}(x)leq\; f^\text{'}(y)$ whenever $xleq\; y.$

★ If the function ''f''(''x'') is convex, ''f''(''x'') differentiable at point ''c'', and ''f'' '(''c'') = ''0'', then ''c'' is a global minimum of ''f''(''x''). Note that this theorem does not follow from the previous one because it does not require the existence of ''f'' '(''x'') except at the point ''c''.

See also

★ Convex optimization

★ Geodesic convexity

★ Logarithmically convex function

★ Quasiconvex function

★ Subderivative of a convex function

References

★ Convex analysis, , R. T., Rockafellar, Princeton University Press, ,

★ Linear and Nonlinear Programming, , David, Luenberger, Addison-Wesley, ,

★ Optimization by Vector Space Methods, , David, Luenberger, Wiley & Sons, ,

★ Convex Analysis and Optimization, , Dimitri, Bertsekas, Athena Scientific, ,

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

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

External links

★ Stephen Boyd and Lieven Vandenberghe, Convex Optimization (book in pdf)

★ Jon Dattorro, Convex Optimization & Euclidean Distance Geometry