SECTION 03 / 8

Convex conjugates: definition, optimization and geometry

On this page 2 headings

For a function f, its convex conjugate is

f^*(t)=\sup_{u}\{tu-f(u)\}

with the supremum taken over the domain of f. We fix t, vary u, and take the largest possible objective value. The conjugate is a new function of t. It is convex, even when f is not convex.

Worked example

Conjugate of a quadratic

Start with
$f(u)=\frac{u^2}{2}$
for all real u. Then
$f^*(t)=\sup_u\left(tu-\frac{u^2}{2}\right)$
Differentiate with respect to u:
$\frac{d}{du}\left(tu-\frac{u^2}{2}\right)=t-u$
The stationary point is $u=t$ .
The second derivative is $-1$ , so this is the unique maximum.
Substitute $u=t$ :
$f^*(t)=t^2-\frac{t^2}{2}=\frac{t^2}{2}$
For $t=2$ , the maximizing input is $u=2$ and the maximum value is
$f^*(2)=2$

Geometric interpretation: for convex differentiable f, a supporting line of slope t has the form

y=tu-f^*(t)

when the supremum is attained. Its vertical intercept is $-f^*(t)$ .

Worked example

The conjugate used for KL divergence

Use
$f(u)=u\ln u$
for $u>0$ , extended continuously by
$f(0)=0$
the optimization domain is $u\geq0$ .
Form $tu-u\ln u$ . Its derivative for $u>0$ is $t-(\ln u+1)$ .
Set it to zero:
$\ln u=t-1$
hence $u=e^{t-1}$ .
The objective is strictly concave on $u>0$ (second derivative $-\frac1u$ ).
Substitution gives
$f^*(t)=e^{t-1}$

Note the distinction between

f(u)=u\ln u

used in the KL f-divergence, and

f^*(t)=e^{t-1}

its convex conjugate. They are different functions.

YOUR STUDY PROGRESS

Finished this section? Save your progress.

Convex conjugates: definition, optimization and geometry

Conjugate of a quadratic #

The conjugate used for KL divergence #

Conjugate of a quadratic

The conjugate used for KL divergence