Symmetries in Global Optimization

This project aims at the development of a theoretical framework accompanied by algorithmic realizations for handling symmetries in global optimization problems. The newly researched algorithms will be inte-grated in the open source global optimization software "COCONUT Environment". For continuous symme-tries, a generalized interval analysis on Lie groups and their representations will be developed. This will be used to solve symmetric global optimization problems on a lower dimensional orbifold. Global optimization is the task of finding the absolutely best set(s) of admissible conditions to achieve an objective under given constraints, assuming that both are formulated in mathematical terms. A special case is the constraint satisfaction problem, where one just wants to find one or all solutions of a given set of constraints. Both problems are much more difficult than convex programming, finding local minimizers of nonlinear programs, or solving algebraic systems of equations when a good starting point is available. Many scientific and industrial applications (e. g., shape optimization in structural mechanics, robot design and analysis, analysis of phase equilibria, protein folding, traveling salesman) lead to difficult global prob-lems in the range from fewer than ten to many thousands of variables. During the last decade, the interest in global optimization has increased substantially, partly because there are more and more applications, and partly because the development of algorithms has already moved the field to the point where many small but already industrial- size applications can be solved reliably. Meeting the challenge of real applications often involves the creation and utilization of new theoretical tools that enable one to exploit the special features of the application. As in many areas with difficult computational problems, success is more often due to theoretical advances rather than to increases in raw computer power or more clever use of existing software packages. Global optimization problems and constraint satisfaction problems tend to get especially difficult if they contain intrinsic symmetries, for instance, most of the above mentioned problems contain a lot of symme-tries in their natural formulation. The reason for that difficulty is that complete algorithms for solving global optimization and constraint satisfaction problems are not allowed to lose any solutions. In the presence of continuous symmetries this leads to a submanifold (an orbit) of equivalent solutions, in the presence of discrete symmetries to a large number of isolated solutions. Most problem classes in global optimization are NP-hard. The best complete algorithms avoid the exponential effort for most problem classes by careful selection of the splitting procedure and strong pruning methods. In the presence of a huge number of equivalent solutions the pruning methods usually lose their power and force the algorithm to rely mostly on splitting, which leads to exponential effort for solving the problem. For dealing with discrete symmetries (e.g., permutation symmetry) in discrete optimization problems there exist many approaches in the literature. However, transferring these methods to continuous problems is not straightforward. Continuous symmetries (e.g., rotational symmetry) are even more difficult to handle, since there exists only very few ideas in the literature to cope with them. In this project, we plan to develop a generalization of interval analysis to matrix Lie algebras and Lie groups and their linear representations in order to do rigorous Lie group numerics including explicit error analysis. We intend to apply the developed rigorous methods for reducing symmetric optimization problems to the orbifold, which is generated by factoring out the Lie group action of the feasible set. We will calculate proper optimality conditions for the problem on the orbifold, hereby eliminating the degeneracy caused by the continuous symmetry. We will research adapted splitting strategies for the branch and bound scheme, and, if necessary, adaptations of local optimization (like search path generation on the orbifold) to increase the performance of the local optimizer. Implications to constraint propagation will also be considered. These new techniques for verified computing on Lie groups will allow the application of computer assisted proof techniques to differential geometry, representation theory, differential equations on manifolds, and other areas of mathematics where Lie groups play a prominent role.

Global optimization is the task of finding the absolutely best set(s) of admissible conditions to achieve an objective under given constraints, assuming that both are formulated in mathematical terms. A special case is the constraint satisfaction problem, where one just wants to find one or all solutions of a given set of constraints. Both problems are much more difficult than convex programming, finding local minimizers of nonlinear programs, or solving algebraic systems of equations when a good starting point is available.Many scientific and industrial applications (e. g., shape optimization in structural mechanics, robot design and analysis, disaster preparation, etc.) lead to difficult global problems in the range from fewer than ten to many thousands of variables. If an optimization problem possesses continuous symmetries then it has an infinite number of equivalent solutions, and this degeneracy makes it very difficult to identify all solutions and to prove the existence of a globally optimal solution close to a given approximate solution.In this project we have developed a new method for handling such symmetries in global optimization problems by generalizing interval analysis a method for verified computation to Lie groups a mathematical structure for describing symmetries. Furthermore, we have developed an algorithm for solving specially structured nonsmooth optimization problems, as they arise as sub-problems in global optimization. This algorithm is the first step towards a general purpose solver for nonsmooth optimization problems, another difficult class of problems relevant in industrial applications. We have implemented the theoretically researched algorithms in a public domain software package called Vienna Matrix Template Library (VMTL) that also forms the new basis for the COCONUT Environment, a software platform for global optimization.We have advanced the field of global optimization by several additional developments: We developed a new class of certificates of infeasibility for nonlinear constraint satisfaction problems (CSPs). Those are computer supported proofs that certain mathematical problems are unsolvable. We constructed a new class of convex quadratic relaxations, i.e., simplified versions of the original problem that can be solved efficiently and provide valuable information for the original problem. We devised a method for aggregating several constraints into one constraint that helps in reducing the search area.We used discrete symmetry breaking and nonlinear optimization methods to effectively close a known benchmark in disaster preparation. This problem is concerned with the optimal investment strategy for the highway network of Istanbul in order to keep evacuation routes as short as possible in the event of an earthquake. Our new solution method computes the optimal investment within milliseconds, which is several orders of magnitudes faster than the former fastest algorithm. In addition, our new method does not require that the failure probabilities for the single highway links are independent. We have also shown in our experiments that the new algorithm makes it possible to compute the optimal investment for evacuation along highway network of the San Francisco bay area in case of an earthquake. This problem can be solved depending on its assumed complexity in a few seconds or a few minutes. To test the limits of our method we have performed experiments and successfully solved problems with 200 decision variables to global optimality. The heuristic first phase of the algorithm (usually within 15% of the global optimum) can be used to approximately solve even bigger problems with up to 900 possible investment decisions in less than an hour.