Convex function

The function , which is defined on the convex set , is called convex , if:

for any and .
If above inequality holds as strict inequality and , then function is called strictly convex

Examples

  • The sum of the largest coordinates

Epigraph

For the function , defined on , the following set:

is called epigraph of the function

Sublevel set

For the function , defined on , the following set:

is called sublevel set or Lebesgue set of the function

Criteria of convexity

First order differential criterion of convexity

The differentiable function defined on the convex set is convex if and only if :

Let , then the criterion will become more tractable:

Second order differential criterion of convexity

Twice differentiable function defined on the convex set is convex if and only if :

In other words, :

Connection with epigraph

The function is convex if and only if its epigraph is convex set.

Connection with sublevel set

If - is a convex function defined on the convex set , then for any sublevel set is convex.

The function defined on the convex set is closed if and only if for any sublevel set is closed.

Reduction to a line

is convex if and only if is convex set and the function defined on is convex for any , which allows to check convexity of the scalar function in order to establish covexity of the vector function.

Strong convexity

, defined on the convex set , is called -strongly convex (strogly convex) on , if:

for any and for some .

Criteria of strong convexity

First order differential criterion of strong convexity

Differentiable defined on the convex set -strongly convex if and only if :

Let , then the criterion will become more tractable:

Second order differential criterion of strong convexity

Twice differentiable function defined on the convex set is called -strongly convex if and only if :

In other words:

Facts

  • is called (strictly) concave, if the function - (strictly) convex.
  • Jensen’s inequality for the convex functions:

    for (probability simplex)
    For the infinite dimension case:

    If the integrals exist and

  • If the function and the set are convex, then any local minimum will be the global one. Strong convexity guarantees the uniqueness of the solution.

Operations that preserve convexity

  • Non-negative sum of the convex functions:

  • Composition with affine function is convex, if is convex
  • Pointwise maximum (supremum): If are convex, then is convex
  • If is convex on for any : is convex
  • If is convex on , then - is convex with
  • Let and , where . If and are convex, and is increasing, then is convex on

Other forms of convexity

  • Log-convex: is convex; Log convexity implies convexity.
  • Log-concavity: concave; not closed under addition!
  • Exponentially convex: , for
  • Operator convex:
  • Quasiconvex:
  • Pseudoconvex:
  • Discrete convexity: ; “convexity + matroid theory.”

References