Paper Info
Title
A Look at the Generalized Heron Problem through the Lens of Majorization-Minimization.
Abstract
In a recent issue of this MONTHLY, Mordukhovich, Nam, and Salinas pose and solve an interesting non-differentiable generalization of the Heron problem in the framework of modern convex analysis. In the generalized Heron problem, we are given k + 1 closed convex sets in R-d equipped with its Euclidean norm and asked to find the point in the last set such that the sum of the distances to the first k sets is minimal. In later work, the authors generalize the Heron problem even further, relax its convexity assumptions, study its theoretical properties, and pursue subgradient algorithms for solving the convex case. Here, we revisit the original problem solely from the numerical perspective. By exploiting the majorization-minimization (MM) principle of computational statistics and rudimentary techniques from differential calculus, we are able to construct a very fast algorithm for solving the Euclidean version of the generalized Heron problem.
Year
DOI
Venue
2014
10.4169/amer.math.monthly.121.02.095
AMERICAN MATHEMATICAL MONTHLY
Keywords
Field
DocType
bioinformatics,biomedical research
Convexity,Algebra,Subgradient method,Euclidean distance,Heron,Majorization,Differential calculus,Computational statistics,Mathematics,Convex analysis
Journal
Volume
Issue
ISSN
121
2
0002-9890
Citations 
PageRank 
References 
4
0.45
7
Authors
2
Name
Order
Citations
PageRank
Eric C. Chi1936.89
Kenneth Lange231043.08