# Closest Farthest Widest
## 1 Introduction
The Frank-Wolfe version of the diameter problem exploits the two supporting hyperplane minorizations  
\[\|\mathbf{x}-\mathbf{y}\|^{2} \geq \|\mathbf{x}_{n}-\mathbf{y}_{n}\|^{2}+2(\mathbf{x}_{n}-\mathbf{y}_{n})^{\top}( \mathbf{x}-\mathbf{x}_{n})\] \[\operatorname{diam}(S) = \operatorname{diam}[\operatorname{conv}(S)]\quad= \operatorname{diam}[\operatorname{ext}(S)\times\operatorname{ext}(S)].\]0Adding these and dividing by 2 yields the minorization  
\[\operatorname{diam}(S) = \operatorname{diam}[\operatorname{conv}(S)]\quad= \operatorname{diam}[\operatorname{ext}(S)\times\operatorname{ext}(S)].\]1 \[\operatorname{diam}(S) = \operatorname{diam}[\operatorname{conv}(S)]\quad= \operatorname{diam}[\operatorname{ext}(S)\times\operatorname{ext}(S)].\]2 \[\operatorname{diam}(S) = \operatorname{diam}[\operatorname{conv}(S)]\quad= \operatorname{diam}[\operatorname{ext}(S)\times\operatorname{ext}(S)].\]3  
To improve \(\|\mathbf{x}-\mathbf{y}\|^{2}\), we take  
\[(\mathbf{x}_{n+1},\mathbf{y}_{n+1}) \in \operatorname*{argmax}_{(\mathbf{x},\mathbf{y})\in\mathbb{S}\times\mathbb{ S}} \begin{pmatrix}\mathbf{x}_{n}-\mathbf{y}_{n}\\ \mathbf{y}_{n}-\mathbf{x}_{n}\end{pmatrix} ^{\top} \begin{pmatrix}\mathbf{x}\\ \mathbf{y}\end{pmatrix} \] \[= \operatorname*{argmax}_{\mathbf{x}\in\mathbb{S}}(\mathbf{x}_{n}-\mathbf{y}_ {n})^{\top}\mathbf{x}\times\operatorname*{argmax}_{\mathbf{y}\in\mathbb{S}}(\mathbf{y}_{ n}-\mathbf{x}_{n})^{\top}\mathbf{y},\]  
which is a Frank-Wolfe update for the function \(f(\mathbf{x},\mathbf{y})=\frac{1}{2}\|\mathbf{x}-\mathbf{y}\|^{2}\) on the Cartesian product \(S\times S\). For the sake of completeness, the Julia functions for our two Frank-Wolfe algorithms follow. The maximum number of iterations, 100, and the convergence tolerances, \(10^{-8}\) and \(2\times 10^{-8}\), can be reset by the user. ```
functionfarthest(Supp::Function,x,p) tol=1.0e-8 foriter=1:100 xnew=Supp(x-p) conv=norm(xnew-x) x.=xnew ifconv<tol break end end return(norm(x-p),x) end functionwidest(Supp::Function,x,y) tol=2.0e-8 foriter=1:100 (xnew,ynew)=(Supp(x-y),Supp(y-x)) conv=norm(xnew-x)+norm(ynew-y) x.=xnew y.=y ifconv<tol break end end return(norm(x-y),x,y) end
```  
Projected gradient ascent offers another avenue for solving the farthest and diameter problems. The two algorithms we later derive and apply are  
\[\mathbf{x}_{n+1} = P_{S}(2\mathbf{x}_{n}-\mathbf{p})\quad\text{for};\operatorname*{far}_{S }(\mathbf{p})\] \[ \begin{pmatrix}\mathbf{x}_{n+1}\\ \mathbf{y}_{n+1}\end{pmatrix}  = \begin{bmatrix}P_{S}(\frac{3}{2}\mathbf{x}_{n}-\frac{1}{2}\mathbf{y}_{n}) \\ P_{S}(\frac{5}{2}\mathbf{y}_{n}-\frac{1}{2}\mathbf{x}_{n})\end{bmatrix} \quad\text{for}; \operatorname*{diam}(S).\]  
As MM algorithms, these two algorithms are guaranteed to increase the objective function. Fortunately, projected gradient ascent does not require the objective function to be convex. Once again the Julia code is straightforward. function farthest(Proj::Function, x, p)  tol = 1.0e-8  for iter = 1:100  xnew = Proj(2x - p)  conv = norm(xnew - x)  x. = xnew  if conv < tol  break  end  end  return (norm(x - p), x)  end  
function widest(Proj::Function, x, y)  tol = 2.0e-8  for iter = 1:100  (xnew, ynew) = (Proj(3x / 2 - y / 2), Proj(3y / 2 - x / 2))  conv = norm(xnew - x) + norm(ynew - y)  x. = xnew  y. = ynew  if conv < tol  break  end  end  return (norm(x - y), x, y) end ```
The contributions of this article include (a) deriving and testing these algorithms, (b) investigating simplifications arising from symmetry, (c) describing a homotopy method for avoiding local maxima, (d) finding the support function of the intersection of a convex cone and a ball centered at the origin, and (e) elaborating a known bisection algorithm for calculating the support function of a convex sublevel set. The next section derives the projected gradient ascent algorithm and lays out our contributions to items (b) through (e). Section 3 briefly tackles convergence of the various algorithms.