Complete Global Search Methods for Geometric Optimization Problems

The project aims at the development of new methods for solving geometry-related global optimization problems. We will focus on problems where a complete search is necessary (i.e., one has to find all global optimizers and prove that they are indeed global), or, where the complete search must be also rigorous (i.e., the results should be mathematically correct even in the presence of rounding errors). The latter type of search methods are the ones that are necessary to give computer-assisted proofs for mathematical problems. First, a geometric optimization toolbox will be implemented in the open source global optimization framework called the "COCONUT Environment". The toolbox will contain the representation of the basic geometric shapes and the implementation of various algorithms on them, taking care of full mathematical rigor. The geometric toolbox will be used to tackle various global optimization problems from discrete geometry. In particular, we plan to solve previously unsolved instances of the problem of densest packings of equal circles into a square, and to tackle packing problems of unequal circles into various containers and packing problems of irregular shapes with the new methods. (To the best of our knowledge, there exist no complete search methods for solving the latter two problem classes yet, despite of their theoretical and practical importance.) In addition, various sphere packing problems will be also investigated. In particular, it is planned to review W.-Y. Hsiang`s 1993 attempt to prove the Kepler conjecture. This work appeared before the famous computer-assisted proof by T.C. Hales, but it is considered incomplete due to several unverified statements. We aim at the completion of Hsiang`s proof by formulating these statements as global optimization problems and solving them with rigorous methods. Furthermore, an attempt will be made to prove the Tammes problem for 13 spheres (also known as the strong kissing number problem), and if successful, for several further values, and to solve problems that are related to minimal energy configurations of molecular structures, such as the Fekete problems and the global optimization of molecular Lennard-Jones clusters. Solving even some smaller instances of these problems to global optimality would give a serious contribution to the ongoing research in these areas and boost research toward solving more complicated energy optimization problems. Finally, complete global optimization problems from engineering which are related to geometric structures, will be studied in the project. These would include rigidification problems, and the verification of structures designed in CAD systems.

No additional funding sources recorded.