Lemma 1. Strong convexity ⇒ Strict convexity ⇒ Convexity.
(But the converse of neither implication is true.)
Proof: The fact that strict convexity implies convexity is obvious.
To see that strong convexity implies strict convexity, note that strong convexity of f implies
f(λx + (1 − λ)y) − α||λx + (1 − λ)y||
2
≤ λf(x) + (1 − λ)f(y) − λα||x||
2
− (1 − λ)α||y||
2
.
But
λα||x||
2
+ (1 − λ)α||y||
2
− α||λx + (1 − λ)y||
2
> 0, ∀x, y, x 6= y, ∀λ ∈ (0, 1),
because ||x||
2
is strictly convex (why?). The claim follows.
To see that the converse statements are not true, observe that f (x) = x is convex but not
strictly convex and f(x) = x
4
is strictly convex but not strongly convex (why?).
1.4 Examples of multivariate convex functions
• Affine functions: f (x) = a
T
x + b (for any a ∈ R
n
, b ∈ R). They are convex, but not
strictly convex; they are also concave:
∀λ ∈ [0, 1], f (λx + (1 − λ)y) = a
T
(λx + (1 − λ)y) + b
= λa
T
x + (1 − λ)a
T
y + λb + (1 − λ)b
= λf(x) + (1 − λ)f(y).
In fact, affine functions are the only functions that are both convex and concave.
• Some quadratic functions: f (x) = x
T
Qx + c
T
x + d.
– Convex if and only if Q 0.
– Strictly convex if and only if Q 0.
– Concave if and only if Q 0; strictly concave if and only if Q ≺ 0.
– The proofs are easy if we use the second order characterization of convexity (com-
ing up).
• Any norm: Recall that a norm is any function f that satisfies:
a. f(αx) = |α|f(x), ∀α ∈ R
3