The Generalized Heron Problem: A Computational Perspective Using Line Search and Conic Reformulation

Abstract

The classical Heron problem and its numerous generalizations have long stood as a fundamental geometric optimization problem in convex analysis and optimization. In this paper, we investigate the Generalized Heron Problem (GHP) and propose two new computational strategies: (i) a projected subgradient method with exact line search (PSM-ELS), and (ii) a second-order cone programming (SOCP) reformulation. The PSM-ELS enhances the classical subgradient framework by replacing diminishing step sizes with adaptive line search along feasible rays, achieving significantly faster convergence and greater effectiveness in nonsmooth settings. The SOCP reformulation uses modern interior-point solvers to provide exact benchmark solutions whenever the feasible region and target sets admit conic representations. Extensive numerical experiments across diverse examples in , , and  demonstrate that PSM-ELS consistently attains minimum root-mean-square error (RMSE) in the fewest iterations, with rapid monotone error decay and competitive runtimes. Compared with the majorization–minimization (MM) algorithm, SM-ELS offers broader applicability; compared with the basic subgradient method, it delivers notable convergence improvement, and compared with SOCP solvers, it provides a lightweight and scalable alternative. These findings establish PSM-ELS as an efficient, stable, and versatile approach for nonsmooth convex optimization problems of distance-sum type, with potential extensions to large-scale and real-world applications.