Closest Farthest Widest

The current paper proposes and tests algorithms for finding the diameter of a compact convex set and the farthest point in the set to another point. For these two nonconvex problems, I construct Frank-Wolfe and projected gradient ascent algorithms. Although these algorithms are guaranteed to go uphill, they can become trapped by local maxima. To avoid this defect, I investigate a homotopy method that gradually deforms a ball into the target set. Motivated by the Frank-Wolfe algorithm, I also find the support function of the intersection of a convex cone and a ball centered at the origin and elaborate a known bisection algorithm for calculating the support function of a convex sublevel set. The Frank-Wolfe and projected gradient algorithms are tested on five compact convex sets: (a) the box whose coordinates range between -1 and 1, (b) the intersection of the unit ball and the non-negative orthant, (c) the probability simplex, (d) the Manhattan-norm unit ball, and (e) a sublevel set of the elastic net penalty. Frank-Wolfe and projected gradient ascent are about equally fast on these test problems. Ignoring homotopy, the Frank-Wolfe algorithm is more reliable. However, homotopy allows projected gradient ascent to recover from its failures.