# Convex Functions

These notes are based on Boyd and Vandenberghe. Here, I have suppressed the domains of functions everywhere for simplicity.

Definition: $f({\bf x})$ is convex if

$f(\alpha {\bf x} + \beta {\bf y}) \leq\alpha f({\bf x}) + \beta f({\bf y})$

when $\alpha,\beta \geq 0$ and $\alpha+\beta=1$.

Or, informally, a function is convex if a “chord” between two points on the function always lies above the function.

A function is convex if any only if the restriction to a line is always convex. This follows pretty easily from the definition:

$f({\bf x})$ is convex if and only if $g(t) = f({\bf x}+t{\bf v})$ is convex for any ${\bf x}$ and ${\bf v}$.

A differentiable function, it is convex if any only if a first-order approximation is a global underestimator:

$f({\bf y}) \geq f({\bf x}) + \nabla f({\bf x})^T ({\bf y} - {\bf x})$

A twice differentiable function is convex if any only if the Hessian is positive definite at all points.

$\nabla^2 f({\bf x}) \geq 0$.

(This is often the easiest way to check for convexity.)

The epigraph of $f$ is roughly the set of all points “above the function”.

$\text{epi}(f) = \{({\bf x},t) | f({\bf x}) \leq t\}$.

$f$ is convex if any only if $\text{epi}(f)$ is a convex set.

Operations that preserve convexity:

* If $f$ is convex and $\alpha \geq$, then $\alpha f$ is convex.

* If $f_1$ and $f_2$ are convex, so is $f_1+f_2$. (This also works for infinite sums or integrals.)

* If $f$ is convex, so is $f(A{\bf x}+{\bf b})$.

* If $f_1,...,f_m$ are convex, then $f({\bf x})=\max_i f_i({\bf x})$ is convex.

* If $f({\bf x},{\bf y})$ is convex in $\bf x$ (for all $\bf y$), then $g({\bf x})=\sup_{\bf y} f({\bf x},{\bf y})$ is convex.

* Suppose $f({\bf x})=h(g({\bf x}))$. (So $h$ is just a scalar function.) Then, $f$ is convex if either A) $g$ is convex and $h$ is convex and nondecreasing. or B) $g$ is concave and $h$ is convex and nonincreasing. (Be careful if h has a limited domain.)

* Suppose $f({\bf x})=h({\bf g}({\bf x}))$. (So $h$ is a function with a vector domain.) Then, $f$ is convex if either A) ${\bf g}$ is convex and $h$ is convex and nondecreasing in each argument. or B) ${\bf g}$ is concave and $h$ is convex and nonincreasing in each argument. (Be careful if h has a limited domain.)

* If $f({\bf x},{\bf y})$ is convex, and $C$ is a convex set, then $g({\bf x})=\inf_{{\bf y} \in C} f({\bf x},{\bf y})$ is convex.

* Suppose $g({\bf x},t)=t f({\bf x}/t)$. If $f$ is convex, then so is $g$ (restricted to the domain $t>0$).

### 4 Responses to Convex Functions

1. Lee Jae won says:

A function is convex if any only if the restriction to a line is always convex. This follows pretty easily from the definition:

is convex if and only if is convex for any and

Would you please explain why this definition is formed to me?

I want to know origin of this definition

2. justindomke says:

I highly recommend Boyd and Vandenberghe’s book:

http://www.stanford.edu/~boyd/cvxbook/

3. Lee Jae won says:

Also I attended the lecture.

But he had assigned proving the upper definition to their students so I coudln’t find the reason I wanted to know.

Could you please prove the upper definition again for me?

Thank you.

4. justindomke says:

Well… OK. First, assume $f$ is convex, and let’s prove $g$ is convex. We have that

$g(\alpha t + \beta s)$
$= f(x + (\alpha t + \beta s)v)$
$= f(\alpha (x + t v) + \beta (x + s v))$
$\leq \alpha f(x + t v) + \beta (x + s v)$
$= \alpha g(t) + \beta g(s)$.

Now, instead assume $g$ is convex for all choices of $x,v$. Then,
$f(\alpha x + \beta y)$
$= f(x + \beta(y-x))$
$= g(\beta)$ (where $v=y-x$ in the definition of $g$).
$\leq (1-\beta)g(0) + \beta g(1)$
$= \alpha f(x) + \beta f(y)$

In all honesty that wasn’t as trivial as I remembered it being…