Closest Farthest Widest

Area of Science:

• Optimization Algorithms
• Computational Geometry
• Convex Analysis

Background:

• Determining the diameter and farthest point in compact convex sets are fundamental problems in optimization.
• Existing algorithms like Frank-Wolfe and projected gradient ascent can be trapped in local maxima for non-convex problems.

Purpose of the Study:

• To propose and test novel algorithms for computing the diameter and farthest point of compact convex sets.
• To investigate the efficacy of a homotopy method in overcoming local maxima limitations of gradient-based algorithms.

Main Methods:

• Construction and testing of Frank-Wolfe and projected gradient ascent algorithms.
• Development and application of a homotopy method to gradually deform a ball into the target set.
• Calculation of support functions for intersections of convex cones and balls, and for convex sublevel sets.

Main Results:

• Frank-Wolfe and projected gradient ascent algorithms demonstrate comparable performance on tested compact convex sets.
• The Frank-Wolfe algorithm shows greater reliability when the homotopy method is not employed.
• The homotopy method enhances the projected gradient ascent algorithm, enabling it to recover from failures.

Conclusions:

• Both Frank-Wolfe and projected gradient ascent are viable for diameter and farthest point computations.
• Homotopy methods offer a significant improvement for projected gradient ascent, increasing its robustness.
• The study contributes refined algorithmic approaches for geometric optimization problems.