Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Convex function"

(People! Not all functions are twice differentiable!!!)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
−
A [[function]] <math>f: I \mapsto \mathbb{R}</math> for some interval <math> \displaystyle I \subseteq \mathbb{R} </math> is ''convex'' (sometimes written ''concave up'') over <math> \displaystyle I </math> if and only if the set of all points <math> \displaystyle (x,y) </math> such that <math> \displaystyle y \ge f(x) </math> is [[convex set | convex]].  Equivalently, <math> \displaystyle f </math> is convex if for every <math> \lambda \in [0,1] </math> and every <math> x,y \in I</math>,
+
A convex function is a continuous function whose value at the midpoint of every interval in its domain does not exceed the arithmetic mean of its values at the ends of the interval.
−
<center><math> \displaystyle \lambda f(x) + (1-\lambda)f(y) \ge f\left( \lambda x + (1-\lambda) y \right) </math>.</center>  Usually, when we do not specify <math> \displaystyle I </math>, we mean <math> I = \mathbb{R} </math>.
 
  
−
We say that <math> \displaystyle f </math> is '''concave''' (or, occasionally, that it is ''concave down'') if <math> \displaystyle -f </math> is convex.
+
A [[function]] <math>f: I \mapsto \mathbb{R}</math> for some interval <math>I \subseteq \mathbb{R} </math> is ''convex'' (sometimes written ''concave up'') over <math>I </math> if and only if the set of all points <math>(x,y) </math> such that <math>y \ge f(x) </math> is [[convex set | convex]].  Equivalently, <math>f </math> is convex if for every <math> \lambda \in [0,1] </math> and every <math> x,y \in I</math>,
 +
<center><math>\lambda f(x) + (1-\lambda)f(y) \ge f\left( \lambda x + (1-\lambda) y \right) </math>.</center>
 +
We say that <math>f </math> is '''strictly convex''' if equality occurs only when <math>x=y </math> or <math> \lambda \in \{ 0,1 \} </math>.
  
−
If <math> \displaystyle f </math> is differentiable, then it is convex if and only if <math> \displaystyle f' </math> is non-decreasing.  Similarly, if <math> \displaystyle f </math> is twice differentiable, we say it is convex over an interval <math> \displaystyle I </math> if and only if <math> f(x) \ge 0 </math> for all <math> x \in I </math>.
+
Usually, when we do not specify <math>I </math>, we mean <math> I = \mathbb{R} </math>.
  
−
Note that in our previous paragraph, our requirements that <math> \displaystyle f </math> is differentiable and twice differentiable are crucial.  For a simple example, consider the function
+
We say that <math>f </math> is (strictly) '''concave''' (or, occasionally, that it is ''concave down'') if <math>-f </math> is (strictly) convex.
 +
 
 +
If <math>f </math> is differentiable on an interval <math>I </math>, then it is convex on <math>I </math> if and only if <math>f' </math> is non-decreasing on <math>I </math>.  Similarly, if <math>f </math> is twice differentiable over an interval <math>I </math>, we say it is convex over <math>I </math> if and only if <math> f''(x) \ge 0 </math> for all <math> x \in I </math>.
 +
 
 +
Note that in our previous paragraph, our requirements that <math>f </math> is differentiable and twice differentiable are crucial.  For a simple example, consider the function
 
<center>
 
<center>
 
<math>
 
<math>
Line 13: Line 18:
 
</center>
 
</center>
 
defined over the non-negative reals.
 
defined over the non-negative reals.
−
It is piecewise differentiable, but at infinitely many points (for all natural numbers <math> \displaystyle x </math>, to be exact) it is not differentiable.  Nevertheless, it is convex.  More significantly, consider the function
+
It is piecewise differentiable, but at infinitely many points (for all natural numbers <math>x </math>, to be exact) it is not differentiable.  Nevertheless, it is convex.  More significantly, consider the function
 
<center>
 
<center>
 
<math>
 
<math>
Line 19: Line 24:
 
</math>
 
</math>
 
</center>
 
</center>
−
over the interval <math> \displaystyle [-2, 2] </math>.  It is continuous, and twice differentiable at every point except <math> \displaystyle{} (0, 1) </math>.  Furthermore, its second derivative is greater than 0, wherever it is defined.  But its graph is shaped like a curvy W, and it is not convex over <math> \displaystyle [-2,2] </math>, although it is convex over <math> \displaystyle [-2,0] </math> and over <math> \displaystyle [0,2] </math>.
+
over the interval <math>[-2, 2] </math>.  It is continuous, and twice differentiable at every point except <math>{} (0, 1) </math>.  Furthermore, its second derivative is greater than 0, wherever it is defined.  But its graph is shaped like a curvy W, and it is not convex over <math>[-2,2] </math>, although it is convex over <math>[-2,0] </math> and over <math>[0,2] </math>.
  
 
{{stub}}
 
{{stub}}
 +
 +
== Resources ==
 +
 +
* [[Jensen's Inequality]]
 +
* [[Karamata's Inequality]]

Latest revision as of 23:10, 19 February 2016

A convex function is a continuous function whose value at the midpoint of every interval in its domain does not exceed the arithmetic mean of its values at the ends of the interval.

A function $f: I \mapsto \mathbb{R}$ for some interval $I \subseteq \mathbb{R}$ is convex (sometimes written concave up) over $I$ if and only if the set of all points $(x,y)$ such that $y \ge f(x)$ is convex. Equivalently, $f$ is convex if for every $\lambda \in [0,1]$ and every $x,y \in I$,

$\lambda f(x) + (1-\lambda)f(y) \ge f\left( \lambda x + (1-\lambda) y \right)$.

We say that $f$ is strictly convex if equality occurs only when $x=y$ or $\lambda \in \{ 0,1 \}$.

Usually, when we do not specify $I$, we mean $I = \mathbb{R}$.

We say that $f$ is (strictly) concave (or, occasionally, that it is concave down) if $-f$ is (strictly) convex.

If $f$ is differentiable on an interval $I$, then it is convex on $I$ if and only if $f'$ is non-decreasing on $I$. Similarly, if $f$ is twice differentiable over an interval $I$, we say it is convex over $I$ if and only if $f''(x) \ge 0$ for all $x \in I$.

Note that in our previous paragraph, our requirements that $f$ is differentiable and twice differentiable are crucial. For a simple example, consider the function

$f(x) = \lfloor x \rfloor (x - \lfloor x \rfloor ) + {\lfloor x \rfloor \choose 2}$,

defined over the non-negative reals. It is piecewise differentiable, but at infinitely many points (for all natural numbers $x$, to be exact) it is not differentiable. Nevertheless, it is convex. More significantly, consider the function

$f(x) = \left( |x| - 1 \right)^2$

over the interval $[-2, 2]$. It is continuous, and twice differentiable at every point except ${} (0, 1)$. Furthermore, its second derivative is greater than 0, wherever it is defined. But its graph is shaped like a curvy W, and it is not convex over $[-2,2]$, although it is convex over $[-2,0]$ and over $[0,2]$.

This article is a stub. Help us out by expanding it.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Convex_function&oldid=76482"