New optimization algorithm and package Extrema improvement

Starting with version 6.8.0 OCCT will have a new algorithm for solving global optimization tasks using an arbitrary objective function of several variables on a hyperparallelepiped.

The algorithm is based on a slightly modified method of searching the global extremum of a function of several variables satisfying the Lipschitz condition [1, 2].

This method looks for one of the global extrema of a function of n variables using a given Lipschitz constant and exhaustive search in an adaptive irregular grid.

First of all this algorithm will be used to replace the existing algorithms from the Extrema package that search for distances between various geometric objects. Mathematically, these problems are equivalent to finding the global minima of functions of several variables.

The existing algorithms for solving this problem work as follows: first they search for the local extrema at some discrete partition of a space of variables and then precise these local extrema with a suitable method of searching for a local extremum. Obviously, this approach theoretically guarantees to find the right solution only when the number of discrete points tends to infinity. On practice we need to use a sufficiently detailed decomposition of curves and surfaces, which adversely affects the performance of algorithms and does not guarantee their reliability: as a rule, we have several errors per year for algorithms from the Extrema package.

The new global extremum search algorithm theoretically guarantees to find an extremum with a given accuracy in a finite number of steps that allows us to hope that algorithms searching for distances between geometric objects will be faster and more reliable.

To demonstrate the capabilities of the algorithm it was applied to rewrite the algorithm used in Extrema_GenExtCC for solving the problem of finding the extrema between a pair of curves that do not allow an analytical solution.

In this regard, the algorithm behavior has slightly changed:

• the new algorithm is configured to search the minimum distance only (since finding the maxima is not needed) and generally produces several global minima, their values being equal to a certain accuracy;
• the new algorithm does not comply with the condition of perpendicularity of the vector connecting the extreme points on the curves and tangents to the curves at these points.

A performance test was conducted for the new algorithm on a pair of complex B-spline curves requiring a detailed discrete partition using the old algorithm.

The parameter boundaries of each of the curves were randomly determined so that the global extremum point could fall into the test interval on each of the curves (stress test). This problem was solved 10,000 times and the integral characteristics were calculated, such as the total time and the number of tests with the discovered global minimum.

Thus, the new algorithm shows a clear advantage in relation to the old one for the “hard” cases.

The new algorithms are already available in the Git repository (current master), classes math_GlobOptMin, Extrema_GenExtCC.

We are planning to improve the global optimization method and replace other algorithms of the Extrema package in subsequent releases.

References:

1. Yu.G.Yevtushenko, Numerical method for global extremum search functions (exhaustive search in an irregular grid). // Journal of Computational Mathematics and Mathematical Physics, 1971, vol. 11, No. 6, pages 1390-1403 (RUS)
2. Yu.G.Yevtushenko, V.A.Ratkin, Bisection method for global optimization of functions of several variables. // Technical Cybernetics, 1987, No.1, pages 119-127 (RUS)