Description

Optimization for Machine Learning
(Convex conjugate)
EPFL
Martin Jaggi & Nicolas Flammarion github.com/epfml/OptML course

For a function f : Rd → R∪{+∞} (which is not necessarily convex !), we consider its convex conjugate which for y ∈ Rd is defined as
f∗(y) = sup (hx,yi− f(x)) ∈ R∪{+∞}
x∈Rd Prove the following properties.
1. Show that f∗ is convex.
2. Show that for x,y ∈ Rd, f(x) + f∗(y) ≥ hx,yi. This is known as Fenchel’s inequality.
3. Show that the biconjugate f∗∗ (the conjugate of the conjugate) is such that f∗∗ ≤ f.
The Fenchel-Moreau theorem (which we will not prove here) states that f = f∗∗ if and only if f is convex and closed. It will turn out to be useful to show the following property.
4. Assume that f is closed and convex. Then show that for any x,y ∈ Rd,
y ∈ ∂f(x) ⇔ x ∈ ∂f∗(y)
⇔ f(x) + f∗(y) = hx,yi