3.6 Fenchel duality

Convexity and conjugate functions

We begin by reviewing two notions of convexity: for sets and for functions.

Definition 1 A subset $C\subseteq X$ is called convex if $z=\alpha x+(1-\alpha )y\in C$ for every $x,y\in C$ and $\alpha \in [0,1]$ ; $z$ is called a convex combination of $x$ and $y$ .

Definition 2 Let $C$ be a convex set. A functional $f:C\to \mathbb{R}$ is convex on $C$ if $f(\alpha x+(1-\alpha \left)y\right)\le \alpha f\left(x\right)+(1-\alpha )f\left(y\right)$ for all $x,y\in C$ and $\alpha \in [0,1]$ . If strict inequality holds the functional is set to be strictly convex . A functional $g$ is called concave (strictly concave) if $-g$ is convex (strictly convex).

We will denote the region above the function $f$ defined over a convex set $C$ as $[f,C]$ , sometimes called an epigraph , as illustrated in [link] .

Definition 3 Let $f$ be a convex functional on a convex set $C$ . The conjugate set $C^{*}$ is defined as

and the conjugate functional $f^{*}:C^{*}\to \mathbb{R}$ is defined as

There is a geometric intuition behind the definition of the conjugate functionals. Consider the illustration below where the horizontal axis represents the space $X$ and the vertical axis represents the scalar field. A hyperplane in this space contains all points $(x,r)\in X\times R$ for which $r=⟨x,x^{*}⟩-k$ for some value of $k\in R$ ; the vector $x^{*}$ determines the orientation of the hyperplane and the value $k$ determines the shift from the origin (i.e., the intersect in the axis $R$ ). The value of the functional $f^{*}\left(x^{*}\right)$ corresponds to the supremum value of $k$ for which the hyperplane intersects $[f,C]$ , and is finite only for $x^{*}\in C^{*}$ ; this is illustrated in [link] .

Note that $C^{*}$ is convex and $f^{*}$ is convex. This definition is easily extended to concave functionals.

Definition 4 Let $g$ be a concave functional on a convex set $D$ . The conjugate set $D^{*}$ is defined as

and the conjugate functional $g^{*}:D^{*}\to \mathbb{R}$ is defined as

Note that $D^{*}$ is convex and $g^{*}$ is concave.

Fenchel duality

The following theorem will allow us to convert an optimization problem with a convex objective function into a dual problem with a concave objective function.

Theorem 1 (Fenchel) Assume that $f$ and $g$ are convex and concave functions, respectively, on convex sets $C$ and $D$ in a normed space $X$ . Assume that $C\cap D$ contains points in the relative interior of $C$ and $D$ and that either $[f,C]$ or $[g,D]$ has a nonempty interior. Suppose further that

is finite. Then,

where the maximum is achieved by some $x_0^{*}\in C^{*}\cap D^{*}$ .

In this theorem, $g\left(x\right)$ is usually set to zero. From a geometrical point of view, the theorem states that there are two ways to interpret the minimum distance between the two epigraphs $[f,C]$ and $[g,D]$ shown below: one in terms of the original functions $f,g$ and one in terms of the duals $f^{*},g^{*}$ : we look for the two tangent hyperplanes for $f$ and $g$ that are maximally separated from one another, as illustrated in [link] .

If the infimum on the left is achieved by $x_0$ , then

Example 1 (Allocation) Assume that we have a capital $x_0$ available for investment with $n$ different funds. There is a predicted gain $g_i\left(x_i\right)$ to having stock worth $x_i$ at fund $i$ , where the functions $g_i$ are concave. We aim to find the optimal allocation of the capital $x=(x_1,...,x_n)$ that maximizes the total gain $g\left(x\right)={\sum }_{i=1}^n{g}_i\left(x_i\right)$ .

To appeal to duality, we have the concave function $g\left(x\right)$ and must define a convex function, e.g., $f\left(x\right)=0$ . The constraint set can be written as the intersection $C\cap D$ with

Therefore, we can write our optimization problem as

We consider the conjugate sets. First, we have

We want to define $C^{*}$ more explicitly. Let $x^{*}\in C^{*}$ be written as $x^{*}=\lambda \mathbf{1}+w$ , where $w\perp \mathbf{1}$ . Then,

which can be arbitrarily large. Now let $x=\frac{x_0}{n}\mathbf{1}+\lambda w$ ; it is easy to check that $x\in C$ for all $\lambda \in \mathbb{R}$ . If $w\ne 0$ then $⟨x,x^{*}⟩=\lambda x_0+\lambda {\parallel w\parallel }^2$ , which again can be arbitrarily large. Since $x^{*}\in C^{*}$ must hold that ${sup}_{x\in C}⟨x,x^{*}⟩<\infty$ , we must have that $w=0$ and so $x^{*}\in \mathrm{span}\left(\left\{\mathbf{1}\right\}\right)$ . Since $x^{*}\in C^{*}$ was arbitrary, then $C^{*}\subseteq \mathrm{span}\left(\left\{\mathbf{1}\right\}\right)$ .

It is also easy to see that $\mathrm{span}\left(\left\{\mathbf{1}\right\}\right)\subseteq C^{*}$ , therefore implying that $C^{*}=\mathrm{span}\left(\left\{\mathbf{1}\right\}\right)$ .

For $D$ , we have a conjugate set

since $g\left(x\right)\le x_0$ . Now $D\subseteq D^{*}$ since all vectors in $D$ have nonnegative entries. Fix $y\in D^{*}$ ; if $y\notin D$ then there is some negative entry $y_i<0$ among $i=1,...,n$ . For such $i$ let $x_{\lambda }=\lambda e_i\in D$ for some $\lambda >0$ ; then we get $⟨x_{\lambda },y⟩=\lambda y_i$ which can be arbitrarily close to $\infty$ (i.e., as $\lambda \to \infty$ we have $⟨x_{\lambda },y⟩\to -\infty$ . Thus $y\notin D^{*}$ , a contradiction. Therefore, if $y\in D^{*}$ then $y\in D$ and so $D^{*}\subseteq D$ . We have therefore shown that $D^{*}=D$ .

The conjugate functionals can be written as

since each $x^{*}\in C^{*}$ can be written as $x^{*}=\lambda \mathbf{1}$ . Therefore, $f^{*}$ can be written as a function of a single variable. Similarly,

where we write

For $x^{*}\in C^{*}\cap D^{*}$ we can write $x_i=\lambda >0$ for all $i=1,...,n$ and so

Therefore, the original problem can be reformulated as the following single-variable problem:

This is due to $x^{*}=\lambda \mathbf{1}\in C^{*}\cap D^{*}$ if and only if $\lambda =0$ . Once ${\lambda }^{*}$ is found, we can find each $x_i$ as the minimizer in $g_i^{*}\left({\lambda }^{*}\right)$ , cf. [link] .