A primal algorithm for the weighted minimum covering ball problem in \mathbb {R}^n

• P. M. Dearing ^[1] ; Pietro Belotti ^[3] ; Andrea M. Smith ^[2]
  1. [1] Clemson University

     Clemson University

     Estados Unidos

     
  2. [2] Liberty University

     Liberty University

     Estados Unidos

     
  3. [3] Xpress Optimization team, Reino Unido

  Mostrar afiliaciones +
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 24, Nº. 2, 2016, págs. 466-492
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• Resumen

  • The nonlinear programming problem of finding the minimum covering ball of a finite set of points in Rn , with a positive weight corresponding to each point, is solved by a directional search method. At each iteration, the search path is either a ray or the arc of a circle and is determined by bisectors of points. Each step size along the search path is determined explicitly. The primal algorithm is shown to search along the farthest point Voronoi diagram of the given points. We provide computational results that show the efficiency of the algorithm when compared to general convex nonlinear optimization solvers.