# The Tiger's Stripes

A blog on fun research and tools in computer science and game theory.

# Convex Duality

Posted: 2016-10-20.

Every convex function has a special relative (or perhaps "evil twin") called its conjugate or dual. In this post, we'll walk through the definition both formally and visually.

Don't forget to brush up on convexity first!

## Dual Spaces

A very cool concept in analysis is that of dual spaces (as opposed to the "duel spaces" originally explored by Galois). (Ouch ... too soon?)

Suppose we are given a vector space $V$. We'll focus on $V = \mathbb{R}^n$ for simplicity and concreteness, but I'll start with the more general notation to emphasize that greater generality is also possible below if you want it.

Now let $V^*$ be the set of all linear functions from $V$ back to the underlying field, in our case $\mathbb{R}$. These are all functions $g$ where $g(\alpha x + \beta x') = \alpha g(x) + \beta g(x')$. It turns out $V^*$ is also a vector space, and it is called the dual space to $V$. Note you should be thinking of linear functions $g$ as elements of this space. For example, given $g_1, g_2 \in V^*$, then $\alpha g_1 + \beta g_2$ is also in $V^*$, and it is the linear function $x \mapsto \alpha g_1(x) + \beta g_2(x)$.

Note in $\mathbb{R}^n$ this is all so easy that it's automatic: We can associate any linear function $g: \mathbb{R}^n \to \mathbb{R}$ with a vector $v_g \in \mathbb{R}^n$ with $g(x) = \langle v_g, x \rangle$. So for $V = \mathbb{R}^n$, the dual space $V^*$ is also $\mathbb{R}^n$. But I want to think of vectors $x^* \in V^*$ as being linear functions on $V$.

By the way, as this might suggest, for finite-dimensional vector spaces, the double dual is the original space -- i.e. $V^{**} = V$. This can be interpreted, if you're so inclined, as thinking of $x \in V$ as linear functions of elements $g \in V^*$, where $x: g \mapsto g(x)$.

One more prerequisite: an affine function is a linear function plus a constant. So for example we can write an affine function $g: V \to \mathbb{R}$ as $\langle x^*, x \rangle - \mu^*$ where $x^* \in V^*$ and $\mu^* \in \mathbb{R}$.

## Diving In

Suppose we are given a convex function $f: V \to \mathbb{R}$, where $V = \mathbb{R}^n$, that is also closed: its epigraph $F$ is a closed set. (An equivalent but way less elegant condition on $f$ is called "lower semicontinuity", and I hate that I even had to mention such an ugly term for something so clean.)

Here are two ways to describe $f$ in terms of sets:

• The set of points in the epigraph $F$.
• The set $F^*$ of affine functions lying below $f$, i.e. $F^* = \left\{(x^*, \mu^*) : \forall x, f(x) \geq \langle x^*, x\rangle - \mu^* \right\} .$

Now my claim is that $F^*$ is the epigraph of a convex function $f^* : V^* \to \mathbb{R}$. Meanwhile, we can interpret $F$ as a set of affine functions $g: V^* \to \mathbb{R}$ that lie below $f^*$.

Exercise 1. Prove that $F^*$ is a closed convex set.

Exercise 2. Show that there exists a function $f^*: V^* \to \mathbb{R}$ whose epigraph is $F^*$; conclude that $f^*$ is a closed, convex function. (Hint: $f^*$ had better map $x^*$ to the smallest $\mu^*$ such that $(x^*, \mu^*) \in F^*$; just show this is well-defined!)

Although I'm being a bit sloppy and omitting it, notice that the domain of $f^*$ will consist of (the convex hull of) the subgradients of $f$. Also, we haven't worried about what happens if $f$ is not closed -- feel free to investigate on your own!

## Tangents

Notice you can view $F$ and $F^*$ as "dual" sets in that, given $F$, we can define $F^* = \left\{ (x^*,\mu^*) ~:~ \forall (x,\mu) \in F, \mu + \mu^* \geq \langle x, x^* \rangle \right\} .$ (Of course, given $F^*$, you can define $F$ exactly analogously.) In a sense, $f$ and $f^*$ define the "tight" boundaries where this optimization / inequality is closest.

For any $(x^*,\mu^*) \in F^*$, we can rearrange the definition of $F^*$ to say \begin{align} \mu^* &\geq \langle x^*, x\rangle ~ - ~ f(x) \qquad (\forall x) \\ \iff \mu^* &\geq \sup_x ~ \langle x^*, x \rangle ~ - ~ f(x) . \end{align} Since $f^*(x^*)$ is defined to be the minimal $\mu^*$ for which this holds, $f^*(x^*) = \sup_x ~ \langle x^*, x \rangle ~ - ~ f(x) .$ Furthermore - and this is important - the $x$ that achieves this supremum will be a subgradient of $f^*$ at $x^*$. (See the next figure.) Similarly, $f(x) = \sup_{x^*} ~ \langle x^*, x \rangle ~ - ~ f^*(x^*)$ with this supremum achieved at $x^*$ a subgradient of $f$ at $x$.

It's worth restating / collecting these:

Summary. Suppose $f$ and $f^*$ are convex conjugates; then we have \begin{align} f(x) &= \sup_{x^*} ~ \langle x, x^* \rangle - f^*(x^*) \\ f^*(x^*) &= \sup_{x} ~ \langle x, x^* \rangle - f(x) \end{align} and furthermore, for the $x^*$ and $x^*$ solving them respectively, \begin{align} x^* &= \nabla f(x) \\ x &= \nabla f^*(x^*) \end{align} if $f$ and $f^*$ are differentiable (otherwise they are subgradients).

## Examples

Here are some examples generated by this python code.

Exercise 3.
Find the conjugate of the function $x \mapsto \frac{1}{p} \sum_i |x_i|^p$ for $p \geq 1$.

Exercise 4.
You may have noticed from the figures above that $x \mapsto \frac{1}{2}\|x\|_2^2$ is its own conjugate. Prove that it is the unique function for which this holds. (Easy mode: prove it is the unique differentiable one.)

Exercise 5.
Let $f^*$ be conjugate to $f$ and $x, x^*$ and $y, y^*$ be conjugate points. Show that $D_f(x,y) = D_{f^*}(y^*, x^*)$ where $D_f$ is the Bregman diverggence of $f$.

## References

(1997) R. Tyrrell Rockafeller. Convex analysis.

(2004) Stephen Boyd and Lieven Vandenberghe. Convex optimization.

Limits to 1000 characters. HTML does not work but LaTeX does, e.g. $\$$x^y\$$ displays as$x^y\$.