# Closest Farthest Widest
## 2 Derivations  
### Projected Gradient Ascent and Homotopy  
Let us first tackle the closest, farthest, and diameter problems when the projection operator \(P_{\mathrm{S}}(\boldsymbol{p})\) is available. These three problems are equivalent to minimizing the functions  
\[c(\boldsymbol{x}) = \frac{1}{2}\|\boldsymbol{x}-\boldsymbol{p}\|^{2}\] \[f(\boldsymbol{x}) = -\frac{1}{2}\|\boldsymbol{x}-\boldsymbol{p}\|^{2}\] \[w(\boldsymbol{x},\boldsymbol{y}) = -\frac{1}{2}\|\boldsymbol{x}-\boldsymbol{y}\|^{2}\]with gradients  
\[\
abla c(\mathbf{x}) = \mathbf{x}-\mathbf{p}\] \[\
abla f(\mathbf{x}) = -(\mathbf{x}-\mathbf{p})\] \[\
abla w(\mathbf{x},\mathbf{y}) = \begin{pmatrix}\mathbf{y}-\mathbf{x}\\ \mathbf{x}-\mathbf{y}\end{pmatrix} \]  
over the sets \(S\) and \(S\times S\). One possibility for this task is projected gradient descent. Because the Lipschitz constants of \(\
abla c(\mathbf{x})\) and \(\
abla f(\mathbf{x})\) are both \(1\), the projected gradient steps for the closest and farthest problems are  
abla c(\mathbf{x}_{n})]\] \[= P_{S}(\mathbf{x}_{n}-\mathbf{x}_{n}+\mathbf{p})\] \[= P_{S}(\mathbf{p})\] \[\mathbf{x}_{n+1} = P_{S}[\mathbf{x}_{n}-L^{-1}\
abla f(\mathbf{x}_{n})]\] \[= P_{S}(\mathbf{x}_{n}-\mathbf{p}+\mathbf{x}_{n})\] \[= P_{S}(2\mathbf{x}_{n}-\mathbf{p}).\]  
As expected, the closest algorithm \(\mathbf{x}_{n+1}=P_{S}(\mathbf{p})\) reduces to ordinary projection. The Lipschitz constant for \(\
abla w(\mathbf{x},\mathbf{y})\) is determined by  
\[\left\| \begin{pmatrix}\mathbf{y}-\mathbf{x}\\ \mathbf{x}-\mathbf{y}\end{pmatrix} - \begin{pmatrix}\mathbf{v}-\mathbf{u}\\ \mathbf{u}-\mathbf{v}\end{pmatrix} \right\| = \sqrt{2\|\mathbf{y}-\mathbf{x}-\mathbf{v}+\mathbf{u}\|^{2}}\] \[\leq \sqrt{2(\|\mathbf{x}-\mathbf{u}\|+\|\mathbf{y}-\mathbf{v}\|)^{2}}\] \[\leq \sqrt{4(\|\mathbf{x}-\mathbf{u}\|^{2}+\|\mathbf{y}-\mathbf{v}\|^{2})}\] \[= 2\left\| \begin{pmatrix}\mathbf{x}-\mathbf{u}\\ \mathbf{y}-\mathbf{v}\end{pmatrix} \right\|\]  
as 2. Consequently, the projected gradient step for the diameter problem is  
\[ \begin{pmatrix}\mathbf{x}_{n+1}\\ \mathbf{y}_{n+1}\end{pmatrix}  = P_{S\times S}\left[ \begin{pmatrix}\mathbf{x}_{n}\\ \mathbf{y}_{n}\end{pmatrix} -\frac{1}{2}\
abla w(\mathbf{x}_{n},\mathbf{y}_{n})\right]\] \[= P_{S\times S}\left[ \begin{pmatrix}\mathbf{x}_{n}\\ \mathbf{y}_{n}\end{pmatrix} -\frac{1}{2} \begin{pmatrix}\mathbf{y}_{n}-\mathbf{x}_{n}\\ \mathbf{x}_{n}-\mathbf{y}_{n}\end{pmatrix} \right]\] \[= \begin{bmatrix}P_{S}(\frac{3}{2}\mathbf{x}_{n}-\frac{1}{2}\mathbf{y}_{n}) \\ P_{S}(\frac{3}{2}\mathbf{y}_{n}-\frac{1}{2}\mathbf{x}_{n})\end{bmatrix} .\]  
This diameter update relies on the facts that minimization of a Euclidean distance is equivalent to minimization of a squared Euclidean distance and that the squared objective splits over the \(\mathbf{x}\) and \(\mathbf{y}\) parameters. The chief problem with all of the proposed algorithms is their propensity to veer toward local maxima. One remedy is good initialization. Given a point \(\mathbf{p}\
otin S\), a general tactic for initialization in the farthest problem is to start with the projection \(P_{S}(\mathbf{p})\). This defines the line segment \([\mathbf{p},P_{S}(\mathbf{p})]\), which can be extended until it hits the boundary of \(S\) at a second point \(\mathbf{x}_{0}\). Replacing \(P_{S}(\mathbf{p})\) by \(\mathbf{x}_{0}\) produces a more distant point of \(S\) and a better starting value in the farthest problem. If \(S\) is an even set in the sense that \(S=-S\), then as discussed in Section 2.3, the second point reduces to \(P_{S}(-\mathbf{p})\). Beyond good initialization, it is worth considering the expensive alternative of homotopy [27] for the diameter problem. The idea is to gradually deform the unit ball \(B\), where the diameter problem is trivial to solve, into the target set \(S\). Thus, we follow the solution path along the family of sets \(tS+(1-t)B\) from \(t=0\) to \(t=1\).