A Look at the Generalized Heron Problem through the Lens of Majorization-Minimization

Area of Science:

• Convex Analysis
• Computational Geometry
• Optimization

Background:

• The generalized Heron problem involves finding a point in a convex set that minimizes the sum of distances to k other convex sets.
• Previous work explored theoretical properties and subgradient algorithms for convex cases.

Purpose of the Study:

• To develop a numerically efficient algorithm for the Euclidean version of the generalized Heron problem.
• To revisit the original generalized Heron problem from a purely computational standpoint.

Main Methods:

• Exploitation of the majorization-minimization (MM) principle from computational statistics.
• Application of basic differential calculus techniques.

Main Results:

• Construction of a very fast algorithm for solving the Euclidean generalized Heron problem.
• Demonstration of the efficacy of MM principle and calculus for this optimization task.

Conclusions:

• The MM principle and calculus provide an efficient numerical approach to the generalized Heron problem.
• This method offers a fast computational solution for finding points minimizing distances to convex sets.