# Closest Farthest Widest
## 2 Derivations
### Supporting Points and Sublevel Sets  
The set of supporting points \(\operatorname{supp}_{S}(\mathbf{v})=\operatorname{argmax}_{x\in S}\mathbf{v}^{\top}\mathbf{x}\) determines the support function \(\sigma_{S}(\mathbf{v})\). Our numerical tests require knowing \(\operatorname{supp}_{S}(\mathbf{v})\) in some specific examples. For instance, the \(\ell_{1}\) unit ball has \(\operatorname{supp}_{S}(\mathbf{v})\) equal to the convex hull of the vertices \(\pm\mathbf{e}_{i}\) where \(|v_{i}|\) is largest. Here, \(\mathbf{e}_{i}\) is included when \(v_{i}>0\), and \(-\mathbf{e}_{i}\) is included when \(v_{i}<0\). For the unit simplex, \(\operatorname{supp}_{S}(\mathbf{v})\) equals the convex hull of the vertices \(\mathbf{e}_{i}\) where \(v_{i}\) is largest. The rectangle \([\mathbf{a},\mathbf{b}]\) is a Cartesian product. Hence, \(\operatorname{supp}_{S}(\mathbf{v})\) is also a Cartesian product. In the one-dimensional case, \(\operatorname{supp}_{S}(\mathbf{v})\) is \(a\) when \(v_{i}<0\), \(b\) when \(v_{i}>0\), and all of \([a,b]\) when \(v_{i}=0\). For a Minkowski sum \(A+B\), \(\operatorname{supp}_{A+B}(\mathbf{v})=\operatorname{supp}_{A}(\mathbf{v})+ \operatorname{supp}_{B}(\mathbf{v})\). This fact plus the identity \(\operatorname{supp}_{IA}(\mathbf{v})=t\operatorname{supp}_{A}(\mathbf{v})\) for \(t\geq 0\) makes it easy to carry out the homotopy method with our Frank-Wolfe algorithms. If \(\operatorname{supp}_{S}(\mathbf{v})\) is a singleton, then \(\sigma_{S}(\mathbf{v})\) is differentiable at \(\mathbf{v}\) by [PERSON]'s theorem [7]. Conversely, if \(\sigma_{S}(\mathbf{v})\) is differentiable, then \(\operatorname{supp}_{S}(\mathbf{v})\) is a singleton by Corollary 25.3.1 of Rockafellar [29]. Because \(\sigma_{S}(\mathbf{v})\) is convex, finite, and locally Lipschits, [PERSON]'s theorem [30; 31] implies that it is differentiable almost everywhere. Hence, \(\sigma_{S}(\mathbf{v})\) is a singleton almost everywhere. Later, we will need \(\mathrm{supp}_{A}(\mathbf{v})\) for the intersection of the non-negative orthant and the ball \(B_{r}\) of radius \(r\) around the origin. This is a special case of projection onto the intersection of an arbitrary closed convex cone \(K\) and the ball. In this general setting, \(\mathbf{w}=\mathrm{supp}_{K\cap B_{r}}(\mathbf{v})=\frac{r}{\|P_{K}(\mathbf{v})\|}P_{K}(\mathbf{v})\) when \(P_{K}(\mathbf{v})\
eq\mathbf{0}\), and \(\mathbf{w}=\mathbf{0}\), otherwise. To prove this assertion, it suffices to show that  
\[d_{\mathbf{u}-\mathbf{w}}\sigma_{S}(\mathbf{v}) = \mathbf{v}^{\top}(\mathbf{u}-\mathbf{w}) \leq 0\]  
for any point \(\mathbf{u}\in K\cap B_{r}\). When \(P_{K}(\mathbf{v})\
eq\mathbf{0}\), the Moreau decomposition and the Cauchy-Schwarz inequality imply that  
\[\mathbf{v}^{\top}(\mathbf{w}-\mathbf{u}) = [P_{K}(\mathbf{v})+P_{K^{\circ}}(\mathbf{v})]^{\top}(\mathbf{w}-\mathbf{u})\] \[= \frac{r}{\|P_{K}(\mathbf{v})\|}\|P_{K}(\mathbf{v})\|^{2}-[P_{K}(\mathbf{v})+ P_{K^{\circ}}(\mathbf{v})]^{\top}\mathbf{u}\] \[\geq \frac{r}{\|P_{K}(\mathbf{v})\|}\|P_{K}(\mathbf{v})\|^{2}-P_{K}(\mathbf{v})^{ \top}\mathbf{u}\] \[\geq r\|P_{K}(\mathbf{v})\|-r\|P_{K}(\mathbf{v})\|\] \[= 0,\]  
where \(K^{\circ}\) is the polar cone of \(K\). Otherwise, \(P_{K}(\mathbf{v})=\mathbf{0}\), and  
\[\mathbf{v}^{\top}(\mathbf{w}-\mathbf{u}) = -[P_{K}(\mathbf{v})+P_{K^{\circ}}(\mathbf{v})]^{\top}\mathbf{u} = -P_{K^{\circ}}(\mathbf{v})^{\top}\mathbf{u} \geq 0\]  
by definition. The polar cone of the non-negative orthant consists of those vectors \(\mathbf{v}\) with \(\mathbf{v}\leq\mathbf{0}\). The current intersection support map can also be deduced less directly from Proposition 2.2 of paper [32]. The corresponding problem of projecting onto the intersection of a ball and cone is treated by [PERSON] [7] and [PERSON] et al. [33]. As already mentioned, the support function of a sublevel set is generally challenging to compute. As a supplement to the brief discussion in Section 6.4.2 of the survey [12], consider the Lagrangian \(-\mathbf{v}^{\top}\mathbf{x}+\mu[g(\mathbf{x})-c]\).