Duality in Optimization

This post provides references for a collection of duality results in optimization over general vector spaces.

For a general vector space $X$, define $\Lambda(X)$ the space of proper convex (weakly) closed functions defined on $X$ and $\Lambda^*(X^*)$ the space of proper convex weakly-$*$ closed functions defined on $X^*$. Here $f: X\longrightarrow [-\infty, +\infty]$ is convex and closed iff it is convex and weakly closed, see Theorem 2.2.1 page 60 [2]. As you will see in the following, these spaces play important role the Fenchel conjugations.

Bi-dual Space

Goldstine’s Theorem. (Theorem 8.4.7 page 238 [3]) If $X$ is a normed space then $X$ is $\sigma (X^{**},X^{*})$-dense subset of $X^{**}$.

If $X^{**}=X$ we say that $X$ is reflexive.

Remark. If $X$ is a non-topology vector space, its algebraic double dual space equals to $X$ iff $X$ is finite dimension. See wiki or Section 44 in [7].

Dual pair

The notion of dual pair is important, for example, in the general construction of Fenchel Rockerfellar duality.

Let $X$, $Y$ be general vector spaces. $\langle \cdot, \cdot\rangle: X\times Y \longrightarrow \mathbb{R}$ is a bi-linear map. The triple $(X, Y, \langle \cdot, \cdot\rangle)$ is called dual pair if it satisfies the following conditions:

1. For $x \in X\setminus \{0_X\}$ there exists $y \in Y$ such that $\langle x, y\rangle\neq 0$
2. For $y \in Y\setminus \{0_Y\}$ there exists $x \in X$ such that $\langle x, y\rangle\neq 0$

As a direct consequence, for example, if $\langle x_1, y\rangle=\langle x_2, y\rangle$ for all $y\in Y$, then $x_1=x_2$. This explains why the dual pair is also called “separated dual system”, see Section 1.2.1 in [4].

Note that, for a topological vector space $X$ and its continuous dual space $X^*$, $(X, X^*)$ with $\langle x, x^*\rangle=x^*(x)$ always satisfies the second condition. The following theorem shows that if $X$ is a locally convex Hausdorff space, then the first condition also holds.

Theorem. (Example Example 8.1.1 page 228 [3]) If $X$ is a locally convex Hausdorff space, then $(X, X^*, \langle \cdot, \cdot\rangle)$ is a dual pair.

Bipolar Theorem

Bipolar Theorem. (Theorem 1.1.9. page 7-8 [2]) Let $A$ be a non-empty set in a locally convex space $X$. $A^{\circ\circ}=A$ iff $A$ is closed, convex containing the origin.

Note that, the Theorem 8.3.8 page 235 [3] also provides the bipolar theorem but in a more general setup called dual pair.

Dual norm

Let $(X, ||\cdot||)$ be a normed space. This norm induces a topology, called normed topology on $X$. Let $X^*$ be the continuous dual space of $X$ with respect to this norm topology. Then $X^*$ is endowed with a norm, say dual norm defined by
$$||x^*||_*:=\sup\{\langle x^*, x\rangle: x\in X, ||x||\leq 1\}$$

It is well known that these norms are weakly and weakly-$*$ l.s.c

Theorem.

• If $X$ is a normed space, the prior norm $||\cdot||$ is weakly lower-semicontinuous (see Proposition 2.4.6. page 46 [1])
• If $X$ is a Banach space, then the dual norm $||\cdot||_*$ is weakly-$*$ lower-semicontinuous (see Proposition 2.4.12. (ii) c) page 60 [1])

Please note that the statements are very similar but the condition on $X$.

An interesting duality result is that $||\cdot||$ also has a similar characterization as $||\cdot||_*$:
$$||x||=\sup\{\langle x, x^*\rangle: x^*\in X^*, ||x^*||_*\leq 1\}$$

Biconjugate Theorem

Biconjugate Theorem. (Theorem 9.3.5. page 327 [1]) Let $X$a be a normed space with topological dual space $X^*$. Then the conjugation is a bijective map between $\Lambda(X)$ and $\Lambda^*(X^*)$, precisely,

• For $f\in \Lambda(X)$, we have $f^*\in \Lambda^*(X^*)$ and $f^{**}=f$;
• For $g\in \Lambda^*(X^*)$, we have $g^*\in \Lambda(X)$ and $g^{**}=g$.

Bi-adjoint operator

Bi-adjoint Theorem. (Theorem 8.10.5 page 257 [3]) Let $(X,X^*)$ and $(Y,Y^*)$ be dual pairs and let the linear map $A : X \longrightarrow Y$ be weakly continuous. Then $A^*: (Y^*, \sigma(Y^*, Y)) \longrightarrow (X^*, \sigma(X^*, X))$ is continuous—i.e., $A^*$ is weak-$*$-to-weak-$*$ continuous and $A^{**} = (A^*)^*=A$.

Some more properties of adjoint operator (defined over general vector space) can be found in our recent post.

Duality for Subdifferentials

Duality for Subdifferentials. (Proposition 2.33 page 84 [4]) Let $f \in \Lambda(X)$ and $X$ be a real Banach space. Then
$$x^*\in \partial f(x) \Longleftrightarrow x\in \partial f^*(x^*)$$

However, strictly speaking, we can only say that $\partial f$ and $\partial f^*$ are inverse of each other if $X$ is reflexive, i.e. $X^{**}=X$, otherwise, their relation is more complicated, see [5], since $\partial f^*(X^*)\subset X^{**}$ and $X^{**}$ is a proper super-set of $X$.

Duality for Uniform Convexity and Smoothness

Duality between uniform convexity and smoothness. (Proposition 3.5.3 page 205 [2]) Let $f \in \Lambda(X)$, $g\in \Lambda^*(X^*)$ have proper conjugates and $\rho, \sigma$ are functions in $\mathcal{A}=\{\varphi: [0, +\infty)\longrightarrow [0, +\infty]| \varphi(0)=0\}$.

• If $f$ and $g$ are $\rho$-convex then $f^*$ and $g^*$ are $\rho^\#$ -smooth, respectively.
• If $f$ and $g$ are $\sigma$-smooth then $f^*$ and $g^*$ are $\sigma^\#$-convex, respectively.

For definition and properties of $\mathcal{A}$, see Section 3.3 page 118 [2]. Here, for $\varphi \in \mathcal{A}$, we have $\varphi^{\#}$ is the conjugate of $\varphi$ over $[0, +\infty)$, i.e. $\varphi^{\#}(t)=\sup\{ts-\varphi(s): s\geq 0\}$ for any $t\in [0, +\infty)$. In particular, if $\varphi(s)=\frac{c}{2}s^2$, then $\varphi^{\#}(t)=\frac{1}{2c}t^2$, this is equivalent to the duality between strong convexity and strong smoothness.

Smooth and convex normed spaces. (Theorem 1.101 page 35 [4]) If $X^*$ is smooth (strictly convex), then $X$ is strictly convex (smooth).

As a consequence, every uniformly convex Banach space is reflexive. (Theorem 1.111. [4])

Fenchel-Rockerfellar Duality

Fenchel-Rockerfellar duality theorem. (Corollary 2.8.5 page 125 [2], Theorem 3.53. page 180 [4]) Let $f\in \Lambda(Y)$ and $g\in \Lambda(X)$ and $L: Y\rightarrow X$ is continuous. If there exists some $y_0\in Y$ such that

• $f$ is finite at $y_0$
• $g$ is finite and continuous at $Ly_0$
  Then
  $$\inf_{y\in Y} f(y) + g(Ly)=\max_{x^*\in X^*}-f^*(-L^*x^*)-g^*(x^*)$$

It is extremely important to notice that:

• If $f$ is assumed to be strongly convex (or equivalently, $f^*$ is assumed to be uniformly smooth), then the LHS attains its minimum with a unique minimizer, see Proposition 3.5.8 page 213 [2].
• The continuity of $g$ is extremely technical since $g$ is only assumed to be l.s.c. Fortunately, the following theorem ensures the continuity of a convex function over its interior of effective domain.

Theorem. (Corollary 2.5. page 13 [6]) Every l.s.c. convex function over a barrelled space (in particular a Banach space) is continuous over the interior of its effective domain.

In particular, we have the result: Every proper convex function on a space of finite dimension is continuous on the interior of its effective domain. (see Corollary 2.3. page 12 [6])

Note that the continuity of $g$ implies its finiteness.

Hence, the condition in above theorem can be replaced: If $X$ is a barrelled space and
$$L \text{dom} f \cap \text{int} (\text{dom} g)\neq \emptyset$$

Explicitly, the condition ensures the existence of some $y_0\in Y$ such that $f$ is finite at $y_0$ and $Ly_0$ belonging to the interior of $\text{dom} g$. Together with the barrelled space $X$, the continuity of $g$ at $Ly_0$ is ensured.

References

[1]: Attouch, Hedy, Giuseppe Buttazzo, and Gérard Michaille. Variational analysis in Sobolev and BV spaces: applications to PDEs and optimization. Society for Industrial and Applied Mathematics, 2014.
[2]: Zalinescu, Constantin. Convex analysis in general vector spaces. World scientific, 2002.
[3]: Narici, Lawrence, and Edward Beckenstein. Topological vector spaces. Chapman and Hall/CRC, 2010.
[4]: Barbu, Viorel, and Teodor Precupanu. Convexity and optimization in Banach spaces. Springer Science & Business Media, 2012.
[5]: Rockafellar, Ralph. “On the maximal monotonicity of subdifferential mappings.” Pacific Journal of Mathematics 33.1 (1970): 209-216.
[6]: Ekeland, Ivar, and Roger Temam. Convex analysis and variational problems. Society for Industrial and Applied Mathematics, 1999.
[7]: Halmos, Paul R. Finite-dimensional vector spaces. Courier Dover Publications, 2017.