Introduction

In these note will collect various notions of duality

duality of sets,
duality of norms,
duality of cones,
duality of functions (the legendre duality)
duality of vector spaces

We are interested in comparing these notions.

Polar of a Set

Let A be a set in Euclidean space. The polar of A is the set

$A^o = \{ y \mid \langle y,x \rangle \le~ 1~ \text{ for all } x \in A \}$

Note for a closed convex set A containing the origin $(A o) o = A$

Inequality

From the definition of polar sets we have

$\langle x , y \rangle \leq 1, \quad \text{ for all } x \in A, y \in A^o$

Dual norms

Definition

Let $\| \cdot \|$ be a norm on $\mathbb{R}^n$ . The associated dual norm, denoted $\| \cdot \|_\ast$ , is defined as

$\| z \|_\ast = \sup\{ \langle z, x \rangle \mid \|x\| \leq 1\}.$

Thus for Euclidean norms squared, the conjugate is the corresponding function with the inverse matrix.

$\|x\| = \sqrt {| Ax |^2 } \qquad \|x\|_* = \sqrt { | A^{-1} x |^2 }$

where A is positive definite.

Inequality

From the definition of dual norm we have the inequality

$z^{T}x \leq \|x\| \|z\|_\ast,$

which holds for all $x$ and $z$ . This inequality is tight, in the following sense: for any $x$ there is a $z$ for which the inequality holds with equality. (Similarly, for any $z$ there is an $x$ that gives equality.)

So the unit balls in the dual norms are polar sets.

Dual Cones

A set K is called a cone if $0 \in K$ and

$0 \in K, \lambda x \in K, \text{ for all } x\in K, \lambda > 0$

The dual cone is given by

$K^* = \{ y \mid \langle y,x \rangle \ge ~0~ \text{ for all } x \in K \}$

Polyhedral Examples

Let

$A = \{ x \mid \langle c_i , x \rangle \le 1 \text{ for } i = 1,\dots, m \}$

Then

$A^o = conv(0,c_1, \dots c_m).$

Now for each face of the convex set, the normal of the face is a convex combination of the vertices. Thus, we can write

$A^o = \{ x \mid \langle d_i , x \rangle \le 1 \text{ for } i = 1,\dots, k \}$ </math>

where $d i$ are convex combinations of ${c i}$ . In two dimensions, for regular polygons, we can simply take multiples of the averages of adjacent normals, as in the examples which follow.

This result is quite useful when computing the dual norm unit balls

Specific Examples

The max norm unit ball is the square, which has $c_i = \{ \pm (1,0), \pm (0,1) \}$

the previous result gives the vertices of the L1 norm unit ball. Can do the same thing for the octagon. the stop sign unit ball has $c_i = \{ \pm (1,0), \pm (0,1), \pm \alpha (1,1), \pm \alpha(1,-1) \}$ where $\alpha = \sqrt 2 /2$

If A is a nonempty set which is self polar then A is the unit ball.
The infinity norm unit ball and the L1 norm unit ball are polars of each other.

Dual Functions: The Legendre Transform

See http://en.wikipedia.org/wiki/Legendre_transformation especially for transformation rules.

The inequality that defines the conjugate function is

$\langle x, y \rangle \le f(x) + f^*(y)$

where the conjugate function is defined by

$f^*(y) = \sup_x \{ \langle x, y \rangle - f(x) \}$

and if f is convex we also have

$f(x) = \sup_y \{ \langle x, y \rangle - f^*(y) \}$

So using Danskin's Theorem we obtain

$\nabla f^*(y) = x^*, \qquad \nabla f(x) = y^*,$

the latter holding for convex functions, f.

From the definition, and from the fact that (for a convex function) the conjugate of the conjugate is the original function, we have that

$\nabla f^*(\nabla f(x)) = x, \qquad \nabla f(\nabla f^*(y)) = y,$

so that the gradients of the conjugate functions are inverses.

Now if the function is a norm squared, then <ref name="Boyd">Boyd and Vandenberghe, Convex Optimization, page 93 </ref> the conjugate is the dual norm unit squared

$f(x) = \frac 1 2 \| x\|^2, \qquad f^*(y) = \frac 1 2 \| x\|_*^2$

Also, if $f(x) = \| x\|$ is a norm, then <ref name="Boyd">Boyd and Vandenberghe, Convex Optimization, page 93 </ref> the conjugate is the indicator function of the dual norm unit ball,

$f^*(y) = \begin{cases} 0, & \|y\|_* \leq 1 \\ \infty, & \text{ otherwise} \end{cases}$

References

Duality - Adam Oberman Math

Duality

Contents

Introduction

Polar of a Set

Inequality

Dual norms

Definition

Inequality

Dual Cones

Polyhedral Examples

Specific Examples

Dual Functions: The Legendre Transform

References