Diagonal methods for expensive global optimization developed by Russian scientists

November 10, 2017

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.

Lobachevsky University

Related Human Activity Articles from Brightsurf:

Urban gulls adapt foraging schedule to human activity patterns
If you've ever seen a seagull snatch a pasty or felt their beady eyes on your sandwich in the park, you'd be right to suspect they know exactly when to strike to increase their chances of getting a human snack.

The National Human Genome Research Institute publishes new vision for human genomics
The National Human Genome Research Institute this week published its 'Strategic vision for improving human health at The Forefront of Genomics' in the journal Nature.

Human activity has made Murray estuary more vulnerable to drought
In drought prone Australia, it's largest river, the Murray is known to suffer acidification in its estuary in South Australia.

Study reveals impact of centuries of human activity in American tropics
The devastating effects of human activity on wildlife in the American tropics over the last 500 years are revealed in a new study published today.

Effects of nutrient pollution in marine ecosystems are compounded by human activity
Nutrient pollution in the oceans caused by human activity can significantly impact marine life.

Emerging infectious disease and challenges of social distancing in human and non-human animals
Humans are not the only social animal struggling with new infectious diseases.

Powerful human-like hands create safer human-robotics interactions
A team of engineers designed and developed a novel humanoid hand that may be able to help human-robotic interactions.

Human activity on rivers outpaces, compounds effects of climate change
The livelihoods of millions of people living along the world's biggest river systems are under threat by a range of stressors caused by the daily economic, societal and political activity of humans -- in addition to the long-term effects of climate change, researchers report.

Human activity threatens 50 billion years of vertebrate evolutionary history
A new study maps for the first time the evolutionary history of the world's terrestrial vertebrates: amphibians, birds, mammals and reptiles.

The truth lies in the soil: How human activity leaves a chemical footprint in soils
After analyzing the composition of soil samples across a large mountainous region in Southwest China, a team of scientists from the Chinese Academy of Geological Sciences and China Geological Survey explains how natural processes determine the distribution of chemical elements on Earth's surface.

Read More: Human Activity News and Human Activity Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.