image: This image shows the division of hypercubes. view more
Credit: Alina Poljanina
Russian scientists from Lobachevsky State University of Nizhni Novgorod have improved the method of global optimization by offering the so-called "diagonal approach." The goal of global optimization is essentially to search for optimal solutions in various areas of human activity. The principal advantage of the diagonal approach compared to other methods is its speed.
When solving multi-parameter applied problems, one resorts to calculations that ensure finding the optimal solution. This is the solution, which will give the maximum benefit with minimum costs. The search for the mathematical tools for such calculations is of high relevance in our world where we are limited in time, resources and actions. The complexity level of the optimization task depends on the parameters and values to be calculated. Sometimes it is necessary to take into account only one factor, and the structure of the problem itself is simple (it has one minimal value to be found), and traditional mathematical methods of local optimization can easily cope with this task.
It is obvious that new methods for solving global optimization problems need to be developed, since traditional algorithms cannot cope with such problems. The computer is supplied with a procedure depending on several numerical parameters and the constraints that must be observed in the calculations. The system has to offer the most appropriate solution within the limits that have been set.
One of the new ways to solve the problem of the expensive global optimization is the diagonal approach. The idea of diagonal methods was proposed by the Hungarian mathematician Janos Pinter in 1996, and the Russian scientist Yaroslav Sergeyev, professor of the Department of Software and Supercomputer Technologies at the UNN Institute of Information Technologies, Mathematics and Mechanics (he is also Distinguished Professor at the University of Calabria, Italy), proposed and implemented a number of fundamental developments of the approach.
The results of studies over the past 20 years were published in the monograph «Deterministic global optimization: an introduction to the diagonal approach» written in collaboration with the researcher of the same institutions Dmitry Kvasov. The monograph was published by Springer with the support of the Russian Science Foundation. For his outstanding achievements in the field of mathematics, Yaroslav Sergeyev received in 2017 the Khwarizmi award, which is often called the «Asian Nobel Prize». He actually serves as President of the International Society of Global Optimization http://www.globaloptimization.org/
What is the essence of the diagonal approach? One can represent an overall set of the problem parameters as a multidimensional hypercube. Any object can be divided into many cubes, which are so small that it will be possible to assemble from them any shape, including a circle.
Imagine that we try to divide an apple into pieces. Each of these pieces can be cut into many smaller pieces many times. In our life, we are limited by the thickness of the knife and the sharpness of our eye, but there are no such limitations in mathematics. We can continue to divide our object into arbitrarily small parts until we reach the desired result. In this scheme, of fundamental importance are the rule for calculating the characteristic and the method for the best partitioning of the hypercube. In our example with an apple, this study would be aimed at finding ways to cut and select the tastiest piece.
"Our method of hypercube partitioning differs from traditional ones in that the hyperinterval is divided into a number of subintervals, which can be divided into three (when three, nine, or 27 new subintervals arise in each partitioning). Besides, the diagonals of these hypercubes rotate in the multidimensional space according to a specific rule proposed by us, in contrast to traditional methods where the diagonals are fixed and parallel to each other. This rotation allows us to obtain a larger number of subintervals thus decreasing the number of computations of the function values to be optimized", explains Yaroslav Sergeyev.
Another feature of the method developed by Yaroslav Sergeyev's group (the diagonal approach) can be described as follows: they take into account the qualitative features in the function's behavior, while in the traditional approach the worst behavior is always the expected.
The developed methods were applied to solve time-consuming real-world problems, for example, by optimizing topology and ensuring the reliability of network switching, image processing, optimal design of control systems, and signal filtering. The efficiency of devices and systems implementing these processes has been increased dramatically with the use of the new methods. Currently, Yaroslav Sergeyev and his colleagues are working to develop parallel versions of the diagonal method permitting to use powerful supercomputer systems for solving highly complex problems.
###