1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: A function is convex if and only if

  1. Nov 23, 2012 #1
    1. The problem statement, all variables and given/known data
    Show that a differentiable function f is convex if and only if the following inequality holds for each fixed point x0 in Rn:
    f(x) ≥ f(x0) + ∇tf(x0)(x-x0) for all x in Rn, where ∇tf(x0) is the gradient vector of f at x0.

    2. Relevant equations

    3. The attempt at a solution

    by definition of a convex function we have:

    f(λx + (1-λ)x0) ≤ λf(x) + (1-λ)f(x0)

    f(λ(x-x0)+x0) ≤ λ(f(x) - f(x0)) + f(x0)

    f(λ(x-x0)+x0) - f(x0) ≤ λ(f(x) - f(x0))

    Setting Δx = λx-x0 we'll have:

    f(Δx + x0) - f(x0) ≤ λ(f(x) - f(x0))

    I'm very hesitant to use this step, because vector division is not defined, but if we were dealing with real numbers (i.e, vectors of dimension 1) I could've gone further to obtain:

    [tex] \frac{f(\Delta{x} + x_0) - f(x_0)}{\lambda} \leq f(x) - f(x_0)[/tex]
    [tex] \frac{f(\Delta{x} + x_0) - f(x_0)}{\lambda(x-x_0)}(x-x_0) \leq f(x) - f(x_0)[/tex]
    [tex] \frac{f(\Delta{x} + x_0) - f(x_0)}{\Delta{x}}(x-x_0) \leq f(x) - f(x_0)[/tex]

    taking limits from both sides as Δx goes to 0 gives us the desired result.

    I don't know how to show that the converse is true, and also I don't know how to generalize what I've written to functions of several variables since vector division is not defined. any helps would be appreciated.
  2. jcsd
  3. Nov 24, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Most of theses types of results generalize almost immediately from the 1-dimensional case to the multivariate case, because if ##x_0, \, x \in \mathbb{R}^n## and ##p = x - x_0,## then
    [tex] f \text{ convex in }\mathbb{R}^n \Rightarrow \phi(t) = f(x_0 + t p)\text{ is convex in } t \in \mathbb{R},[/tex] and conversly. So, you need to show that ##\phi(t)## is convex if and only if
    [tex] \phi(t) \leq \phi(t_0) + \phi'(t_0) \, (t - t_0) \, \forall \, t, t_0.[/tex]

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook