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.

The project aimed at the development of novel methods for solving geometry-related global optimization problems. We targeted problems where a so-called complete global search was necessary, in order to find all global optimizers of a problem and to prove that they are indeed global, or to verify an optimization-related mathematical statement on a computer.The project resulted in many new results for various problems, both from discrete geometry and from real life applications. Regarding the first group of problems, the most important result was the solution of the previously open problems of finding the densest packing of 31, 32, and 33 equal circles in a square. We developed a set of new and sophisticated tools that have been integrated into a computer assisted proof. The mentioned problems are the highest ones solved on a computer in the half-century old history of the problem class. It is strongly believed that the developed toolbox will be suitable to tackle higher circle packing instances, and it can be generalized for other problems, such as packing problems on the sphere.Another important result for discrete geometry was a computer-assisted proof for finding the densest packing of three squares in a circular container. This was also an open problem before our solution. Although this problem class seems similar to that of circle packing, it leads to much more difficult optimization models that are very hard to solve to global optimality. We solved the problem inthe GloptLab optimization environment after building a constraint satisfaction model of it.A further significant achievement of the project was the development of new methods for finding positive invariant sets of numerical integration schemes for long term integration, using large step sizes. The importance of finding such sets and a related step size is the improvement in the solution of ordinary differential equations that model long lasting chemical or similar processes. Our method is based on the computer verification of set containment relations using complete global search.We also investigated the coverings of a square with uniform circles of minimal radius, with uncertainties in the actual locations of the circles. This model can have important practical applications, such as deploying sensor networks remotely into a dangerous location or deployments influenced by weather. We investigated different geometrical shapes of uncertainty regions, the most general ones being polygons. We designed a bi-level optimization method that combines complete global search and derivative free black-box search to solve various instances of the problem class.During the project numerous tools have been implemented that promote the solution of geometric optimization problems with complete global search. These include new algorithms and data structures in the COCONUT and GloptLab optimization environments, and a standalone software package for circle packing.