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:

    October 18, 2009 at 6:09 pm

    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

    please send e-mail to me..

  2. justindomke Says:

    October 18, 2009 at 10:39 pm

    I highly recommend Boyd and Vandenberghe’s book:

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

  3. Lee Jae won Says:

    October 19, 2009 at 12:33 am

    I read the book.

    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:

    October 19, 2009 at 9:27 pm

    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…


Leave a Reply