A function is convex if and only if

[Arian.D]

Homework Statement

Show that a differentiable function f is convex if and only if the following inequality holds for each fixed point x₀ in Rⁿ:
f(x) ≥ f(x₀) + ∇^tf(x₀)(x-x₀) for all x in Rⁿ, where ∇^tf(x₀) is the gradient vector of f at x₀.

Homework Equations

The Attempt at a Solution

by definition of a convex function we have:

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

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

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

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

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

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.

 

[Ray Vickson]

Homework Statement

Show that a differentiable function f is convex if and only if the following inequality holds for each fixed point x₀ in Rⁿ:
f(x) ≥ f(x₀) + ∇^tf(x₀)(x-x₀) for all x in Rⁿ, where ∇^tf(x₀) is the gradient vector of f at x₀.

Homework Equations

The Attempt at a Solution

by definition of a convex function we have:

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

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

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

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

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

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.

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]

RGV