# Computation of the Hausdorff Distance between Two Compact Convex Sets
## 2 Materials and Methods
### Derivation of the Algorithms  
When \(B\) is convex, the supporting hyperplane inequality  
\[\frac{1}{2}\operatorname{dist}(\mathbf{x},B)^{2} \geq \frac{1}{2}\operatorname{dist}(\mathbf{x}_{n},B)^{2}+\mathbf{v}_{n}^{ \top}(\mathbf{x}-\mathbf{x}_{n})\]  
for \(\mathbf{v}_{n}=\mathbf{x}_{n}-P_{B}(\mathbf{x}_{n})\) generates our first algorithm. Maximizing this minorization over \(\mathbf{x}\in A\) is equivalent to calculating the support function \(\sigma_{A}(\mathbf{v}_{n})=\sup_{\mathbf{x}\in A}\mathbf{v}_{n}^{\top}\mathbf{x}\). If \(\operatorname{supp}_{A}(\mathbf{v})\) denotes the set of points in \(A\) where \(\sigma_{A}(\mathbf{v})\) is attained, then the Frank-Wolfe algorithm just described can be phrased as  
\[\mathbf{x}_{n+1} \in \operatorname{supp}_{A}(\mathbf{v}_{n}) = \operatorname{supp}_{A}[\mathbf{x}_{n}-P_{B}(\mathbf{x}_{n})].\]  
The MM principle guarantees that the next iterate \(\mathbf{x}_{n+1}\) will tend to increase the objective \(\frac{1}{2}\operatorname{dist}(\mathbf{x},B)^{2}\) unless \(\mathbf{v}_{n}=\mathbf{0}\). This exception occurs when \(\mathbf{x}_{n}\in B\). Fortunately, when the iterates begin in \(A\setminus B\), they remain in \(A\setminus B\). Indeed, if \(\mathbf{x}_{n}\in A\setminus B\) but \(\mathbf{x}_{n+1}\in B\), then the obtuse angle condition [23] requires  
\[[\mathbf{x}_{n}-P_{B}(\mathbf{x}_{n})]^{\top}\mathbf{x}_{n+1} \leq [\mathbf{x}_{n}-P_{B}(\mathbf{x}_{n})]^{\top}P_{B}(\mathbf{x}_{n})\] \[< [\mathbf{x}_{n}-P_{B}(\mathbf{x}_{n})]^{\top}\mathbf{x}_{n},\]  
contradicting the optimality of \(\mathbf{x}_{n+1}\). To achieve the requirement \(\mathbf{x}_{0}\in A\setminus B\) of the Frank-Wolfe method, we put \(\mathbf{x}_{0}=P_{A}(\mathbf{r})\) for a random vector \(\mathbf{r}\) and then check that \(\|P_{B}(\mathbf{x}_{0})-\mathbf{x}\|>0\).  
If \(B\) is closed and convex, then the gradient of the function \(\frac{1}{2}\operatorname{dist}(\mathbf{x},B)^{2}\) is Lipschitz with constant \(1\)[23]. This fact plus the outcome of completing the square entails the minorization  
\[\frac{1}{2}\operatorname{dist}(\mathbf{x},B)^{2} \geq \frac{1}{2}\operatorname{dist}(\mathbf{x}_{n},B)^{2}+\mathbf{v}_{n}^{-}( \mathbf{x}-\mathbf{x}_{n})-\frac{1}{2}\|\mathbf{x}-\mathbf{x}_{n}\|^{2}\] \[= \frac{1}{2}\operatorname{dist}(\mathbf{x}_{n},B)^{2}-\frac{1}{2}\| \mathbf{x}-\mathbf{x}_{n}-\mathbf{v}_{n}\|^{2}+\frac{1}{2}\|\mathbf{v}_{n}\|^{2}.\]  
Hence, the MM principle implies that defining  
\[\mathbf{x}_{n+1} = P_{A}(\mathbf{x}_{n}+\mathbf{v}_{n}) = P_{A}[2\mathbf{x}_{n}-P_{B}(\mathbf{x}_{n})]\]  
also increases \(\frac{1}{2}\operatorname{dist}(\mathbf{x},B)^{2}\). This second of our two algorithms is a special case of projected gradient ascent. Its flowchart (Algorithm 1) summarizes this straightforward strategy started from many random points \(\mathbf{x}_{0}\).  
```
0: Projection operators \(P_{A}(\mathbf{x})\) and \(P_{B}(\mathbf{y})\), initial point \(\mathbf{x}_{0}\), maximum iterations \(n\), and convergence criterion \(\epsilon>0\).
1:\(\mathbf{x}=\mathbf{x}_{0}\)
2:for\(iter=1:n\)do
3:\(\mathbf{x}_{\text{new}}=P_{A}[2\mathbf{x}-P_{B}(\mathbf{x})]\)
4:if\(\|\mathbf{x}_{\text{new}}-\mathbf{x}\|<\epsilon\)then
5: break
6:else
7:\(\mathbf{x}=\mathbf{x}_{\text{new}}\)
8:endif
9:endfor
10: Return \(\mathbf{x}_{\text{new}}\)
```  
**Algorithm 1** Computation of \(d(A,B)\) by Projected Gradient Ascent