Estimation of fekete points

• Autores: José Manuel Gesto Beiroa
• Directores de la Tesis: Enrique Bendito Pérez (dir. tes.) , Andrés Marcos Encinas Bachiller (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2008
• Idioma: inglés
• Tribunal Calificador de la Tesis: Antonio Huerta Cerezuela (presid.) , Ramón Codina Rovira (secret.) , José Luis Fernández Pérez (voc.) , Juan Bosco García Archilla (voc.) , Jean-Baptiste Hiriart-Urruty (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • Many mathematical problems with applications en Physics, Numerical Methods and Complexity Theory are raised in terms of the minimization of a certain potential energy functional associated to an N particle system under general constraints, Usually, the involved functionals depend on the relative distances between pairs of particles. Constructing an algorithm that finds good estimations of the global minimum of the logarithmic potential energy on the 2-sphere is the centre of S. Smale's 7th 'Mathematical problem for the 21th century'. Different potential energy functionals have been also used in molecular mechanics, dynamic systems, numerical integration, polynomial interpolation, mesh generation and computer aided design. In this Dissertation we call Fekete problem that of minimizing under general constraints any potential energy functional involving the relative distances between N equal points, and we call Fekete points the configurations that give the minimum energy in this kind of problems.

    The Fekete problem is a prototype of highly non-linear optimization problem with constraints. One of its main characteristics is the massive multiextremality. Smale's 7th problem gives a new dimension to the algorithmic and numeric treatment of the problem and it focuses in its computational complexity. In this Philosophical Dissertation we carry out an exhaustive study of the computational cost of the Fekete problem in a numerical-statistic context. Both the local and global optimization problems are considered.

    In particular, we develop an algorithm, Forces' method, for the Fekete problem and we analyze the numerical effort required to obtain with this algorithm an approximate local minimum for the logarithmic energy on the 2-sphere. We study the robustness, convergence and stability properties of Forces' method and we characterize the probability distribution of the computational cost associated with the identification of an approximate local minimum. In particular, we obtain that the average cost associated to the identification of a local minimum by means of the Forces' method is of order approximately N2.77 .

    On the other hand, in this work we carry out a massive computational program for the case of the logarithmic energy on the 2-sphere with the objective of characterizing the probability distribution of the different minima in this singular case. The obtained sample information provides strong numerical and statistical evidence that the Forces' method constitutes a probabilistic positive solution to Smale's 7th problem.

    Finally, we develop strategies to extend the application of the Forces' method to more general situations, as for the constraints and for the functionals to be minimized. We consider the case of the logarithmic and Riesz's energies on what we call W-compact sets. Essentially, these sets are defined as the finite union of surfaces and curves in R3 . In general, we observe that the robustness and convergence properties of Forces' method are strongly independent of the considered geometry and potential energy.