Duality of faces in polar sets

31 August 2024

Also published on the UBC Optimization Group blog.

In this blog post we introduce a notion of duality between faces of polar convex sets. Our purpose is to show through the simplicity of this introduction that this notion of duality between faces of convex sets is a natural one. To achieve this we employ a narrative tone and focus on intuitions. We begin by defining an abstract notion of duality between sets which is a generalization of polar sets. Then we show how the notion of dual faces of convex sets is just another instance of this notion of dual sets. Along the way we will also discuss weak and strong duality in this setting.

Consider two sets $\mathcal{A}, \mathcal{B}$, and define a relation $\sim$ such that any two elements $a \in \mathcal{A}, b \in \mathcal{B}$ may relate to each other ($a \sim b$), or may not ($a \not \sim b$). Let $A \subseteq \mathcal{A}$ and $B \subseteq \mathcal{B}$. We say that $A \sim B$ when any pair $(a,b) \in A \times B$ satisfies $a \sim b$. Such a relation between sets can be framed in different ways. We can say that every element $a \in A$ induces a constraint in the space $\mathcal{B}$ that is satisfied by all the elements of $B$. Conversely, each element in $B$ corresponds to a constraing in $\mathcal{A}$. If we think of $A$ as a set of constraints in $\mathcal{B}$, the dual $A^p$ of $A$ is the solution set of $A$ in $\mathcal{B}$. Another equivalent definition is that the dual set $A^p$ is the largest set $B \subseteq \mathcal{B}$ that satisfies $A \sim B$.

We discuss the concept of strong duality, which is the statement that $A^{p p}=A$. Starting from a set $A \subseteq \mathcal{A}$, let us think of $\mathcal{B}$ as a set of constraints in $\mathcal{A}$. Let $B \subseteq \mathcal{B}$ be all the constraints $b$ that $A$ uniformly satisfies ($A \sim b$). Then $B = A^p$. Indeed, from the way we defined $B$, the set $B$ is the largest subset of $\mathcal{B}$ such that $A \sim B$. We view $B$ as a mold around $A$. Indeed, we did our best to contour $A$ with all the valid constraints that we could find in $\mathcal{B}$. $B = A^p$ is then the tightest mold around $A$ that we could make from the constraints in $\mathcal{B}$.

We argue that strong duality between sets (that $A^{p p} = A$) occurs when the mold is tight, meaning that $\forall a \not \in A$, $a \not \sim B$. Indeed, the statement that $A^{p p} = A$ can be understood as follows. We start with some model set $A \subseteq \mathcal{A}$, and find that the mold $B= A^{\circ}$ corresponds to the tightest possible mold we could make around our model $A$ by using exclusively mold-building-blocks $b$ found in $\mathcal{B}$. Then as is the purpose of any mold, we forget about the model $A$ that we used to create the mold, and only keep the mold described by $B$ in order to produce copies of $A$. When the mold $B$ is tight around the model $A$, we may pour some liquid iron into the mold to get a statue with the original shape of $A$. The action of "pouring into the mold" is to take all elements in $\mathcal{A}$ that satisfy all constraints in $B$, i.e. the largest set $A' \subseteq \mathcal{A}$ such that $A' \sim B$, which is $A' = B^p$ and is therefore $A^{p p}$. From this analogy the idea of weak duality, that $A \subseteq A^{p p}$, becomes evident. By taking an object, making a mold around that object, removing the object from the mold and then filling that mold completely, the resulting statue will be strictly larger than the original. Moreover, if the mold described by $B$ captures the model $A$ perfectly, then the result of the pour is as good as the original, and $A^{p p}= A$, which is the case where strong duality occurs. If, on the other hand, for some reason the set $\mathcal{B}$ did not have the sufficient expressive power to make a tight mold around $A$, then the best possible mold $B$ will leave some space around $A$, and this additional space will be filled by the subsequent pour. In this case, the pour will be strictly larger than the model, so $A^{p p} \supset A$, and only weak duality holds.

We focus on the concept of polar sets, which is a particular case of dual sets. Let $\mathcal{A} = \mathcal{B} = \mathbb{E}$, where $\mathbb{E}$ is a euclidian space. Furthermore, define the relation $a \overset{ \le }{\sim} b$ to be satisfied iff $a \cdot b \le 1$. Then the polar set of some set $A \subseteq \mathcal{A}$ is the dual set of $A$ (that is, $A^p$ under the relation $\overset{ \le }{\sim}$). If we restrict $A$ to be a closed convex set containing the origin, it can then be characterized as an intersection of a collection of half-spaces corresponding to its supporting hyperplanes (this is a fundamental result in convex analysis.) Notice that this family of constraints (those half-spaces corresponding to supporting hyperplanes of $A$) are a subset of the constraints corresponding to our underlying set of available constraints $\mathcal{B}$ (which in this case are the constraints with solution sets $\{a \in \mathcal{A} | a \cdot b \le 1\}$, where each $b \in \mathcal{B}$ yields a constraint). We name the sets $\mathcal{A}$, $\mathcal{B}$ to illustrate the purpose of the sets, although we are still in a regime where $\mathcal{A} = \mathcal{B} = \mathbb{E}$. So in this case our set of mold-forming atoms $\mathcal{B}$ is sufficiently expressive to form a tight mold around $A$. This means that we have strong duality.

Now if we instead take a more restrictive relation; that $a \overset{=}{\sim} b$ when $a \cdot b=1$, we obtain a more restricted kind of dual set: duality of affine subspaces. Under this equivalence relation, we call the dual set $A^p$ the dual face of $A$. To avoid confusion, we denote $A^f$ to mean the dual set under the equality relation $\overset{ = }{\sim}$, and reserve the notation $A^\circ$ for polar sets, the dual set under the relation $\overset{ \le }{\sim}$. If we require that $A \subseteq \mathbb{E}$ be an affine subspace, then under this new relation $\overset{ = }{\sim}$ strong duality holds. Indeed, the set of constraints embodied by $\mathcal{B}$ is that of all affine hyperplanes. We can form a tight mold around any subspace $A$ with the intersection of finitely many affine hyperplanes, and therefore strong duality holds in this case as well.

We introduce an interesting instance of duality between sets: for a closed convex set $A$ containing the origin in its interior, and its polar set $B= A^\circ$, define the underlying set $\mathcal{A}$ in our "duality of sets" framework to be none other than $A$, and similarly let $\mathcal{B}$ be $B$. Within these underlying sets, take the equality relation $\overset{ = }{\sim}$ and consider the duality of sets that arises from it. That is, for a set $\bar{A} \subseteq A$, what is its dual set $\bar{A}^f$?

To answer this question, we first need an additional concept. Define an (exposed) face of a closed convex set $A$ to be of the form $\bar{A} = \mathrm{arg sup}_{a \in A} \{a \cdot d\}$ for some vector $d\in \mathbb{E}$. Also define a gauge function of a set $S \subseteq \mathbb{E}$ to be $\gamma_S(x) = \inf\{\lambda \in \mathbb{R}_+ \mid x \in \lambda S\}$. We say that $\bar{A}$ is exposed by $d$. We argue that with the underlying sets $A, B$ and with the relation $\overset{ = }{\sim}$, we have strong duality on the exposed faces of $A$. Indeed, the mold formed by $\bar{A}^f$ includes the constraint specified by the vector $\tilde{d} \in \mathbb{E}$ which we define to be $d$ re-scaled by a positive scalar so as to lie on the boundary of $B$ (specifically, $\tilde{d} := \frac{d}{\gamma_B(d)}$ for the gauge function $\gamma_B$.) That $\tilde{d} \subseteq \bar{A}^f$ follows from the fact that $$\forall a \in \bar{A},\, \tilde{d} \cdot a = \frac{d}{\sup_{a' \in \bar{A}} a' \cdot d} \cdot a = 1,$$ which means that $\tilde{d} \sim \bar{A}$, and therefore that $\tilde{d} \in A^f$. Moreover, the restriction induced by $\tilde{d}$ in $\mathcal{A}$ is by itself sufficient to form a tight mold around $\bar{A}$ because the fact that $\bar{A}$ is the largest set satisfying the restriction imposed by $\tilde{d}$ is in fact the definition of $\bar{A}$, since it is a face exposed by $\tilde{d}$. Therefore, it follows that strong duality holds for any exposed face $\bar{A}$.

The fact that strong duality holds in this setting means that there is indeed a well-defined dual face $\bar{A}^f$ in $A^\circ$for any given face $\bar{A}$ of $A$. Since this is just another instance of a duality of sets under the simple relation $\overset{ = }{\sim}$, I hope that you are now convinced that this notion is indeed a natural one.