Keywords

1 Introduction

The development of optimization methods that use high-performance computing systems to solve time-consuming global optimization problems is an area receiving extensive attention. The theoretical results obtained provide efficient solutions to many applied global optimization problems in various fields of scientific and technological applications. At the same time, the practical software implementation of these algorithms for multiextremal optimization is quite limited. Among the software for the global optimization, one can select the following systems: LGO (Lipschitz Global Optimization) [14], GlobSol [11], LINDO [12], IOSO (Indirect Optimization on the basis of Self-Organization) [3], MATLAB Global Optimization Toolkit [23], TOMLAB system [10], BARON (Branch-And-Reduce Optimization Navigator) [15], GAMS (General Algebraic Modeling System) [2], Global Optimization Library in R [13].

In this paper, a novel Globalizer software system is considered. The development of the system was conducted based on the information-statistical theory of multiextremal optimization aimed at developing efficient parallel algorithms for global search – see, for example, [21, 22]. The Globalizer advantage is that the system is designed to solve time-consuming multiextremal optimization problems. In order to obtain global optimized solutions within a reasonable time and cost, the system efficiently uses modern high-performance computer systems.

2 Statement of Multidimensional Global Optimization Problem

In this paper, the core class of optimization problems which can be solved by using Globalizer is examined. This involves multidimensional global optimization problems without constraints, which can be defined in the following way:

$$ {\upvarphi }\left( {\text{y}} \right) \to \inf , \; {\text{y}} \in {\text{D}} \subset {\text{R}}^{\text{N}} , $$
(1)
$$ {\text{D}} = \left\{ {{\text{y}} \in {\text{R}}^{\text{N}} { :}\; {\text{a}}_{\text{i}} \le {\text{y}}_{\text{i}} \le {\text{b}}_{\text{i}} , 1 \le {\text{i}} \le {\text{N}}} \right\}. $$
(2)

If \( {\text{y}}^{ *} \) is an exact solution of problem (1)–(2), the numerical solution of the problem is reduced to building an estimate \( {\text{y}}^{0} \) of the exact solution matching to some notion of nearness to a point (for example, \( \left\| {{\text{y}}^{ *} - {\text{y}}^{0} } \right\| \le\upvarepsilon \) where \( \upvarepsilon > 0 \) is a predefined accuracy) based on a finite number \( {\text{k}} \) of computations of the optimized function values.

Regarding to the class of problems considered, the fulfillment of the following important conditions is supposed:

  1. 1.

    The optimized function φ(y) can be defined by some algorithm for the computation of its values at the points of the domain D.

  2. 2.

    The computation of the function value at every point is a computation-costly operation.

  3. 3.

    Function φ(y) satisfy the Lipschitz condition.

3 Globalizer Architecture

The Globalizer expands the family of global optimization software systems successively developed by the authors during the past several years [1, 5].

The Globalizer architecture is presented in Fig. 1. The structural components of the systems are:

Fig. 1.
figure 1

Program architecture of Globalizer system (Blocks 1–2, 5–7 have been implemented; Blocks 3–4 and 8–11 are under development)

Full size image

  • Block 0 is an external block. It consists of the procedures for computing the function values (criteria and constraints) for the optimization problem being solved.

  • Blocks 1–4 form the optimization subsystem for solving the global optimization problems (Block 1), nonlinear programming (Block 2), multicriterial optimization (Block 3), and general decision making problems (Block 4).

  • Block 5 is a subsystem for accumulating and processing the search information.

  • Block 6 contains the dimensional reduction procedures based on the Peano evolvents; this block also provides interaction between the optimization blocks and the initial multidimensional optimization problem.

  • Block 7 organizes the choice of parallel computation schemes in the Globalizer system subject to the computing system architecture employed (the numbers of cores in the processors, the availability of shared and distributed memory, the availability of accelerators for computations, etc.) and the global optimization methods applied.

  • Block 8 is responsible for managing the parallel processes when performing the global search (determining the optimal configuration of parallel processes, distributing the processes between computing elements, etc.).

  • Block 9 is a management subsystem, which controls the computational process when solving global optimization problems.

  • Block 10 is responsible for organizing the dialog interaction with users for stating the optimization problem, adjusting system parameters (if necessary), and visualizing and presenting the global search results.

  • Block 11 is a set of tools for visualizing and presenting the global search results; the availability of tools for visually presenting the computational results enables the user to provide efficient control over the global optimization process.

4 Globalizer Approach for Solving the Global Optimization Problems

4.1 Methods of Dimension Reduction

The Globalizer implements a block multistage scheme of dimension reduction [1], which reduces the solving of initial multidimensional optimization problem (1)–(2) to the solving of a sequence of «nested» problems of less dimensionality.

Thus, initial vector \( {\text{y}} \) is represented as a vector of the «aggregated» macro-variables

$$ {\text{y}} = \left( {{\text{y}}_{1} , {\text{y}}_{2} , \ldots , {\text{y}}_{\text{N}} } \right) = ({\text{u}}_{1} , {\text{u}}_{2} , \ldots , {\text{u}}_{\text{M}} ) $$
(3)

where the i-th macro-variable \( {\text{u}}_{\text{i}} \) is a vector of the dimensionality \( {\text{N}}_{\text{i}} \) from the components of the vector \( {\text{y}} \) taken sequentially i.e.

$$ \begin{array}{*{20}c} {u_{1} = \left( {y_{1} , y_{2} , \ldots , y_{{N_{1} }} } \right),} \\ {u_{2} = \left( {y_{{N_{1} + 1}} , y_{{N_{1} + 2}} , \ldots , y_{{N_{1} + N_{2} }} } \right),} \\ {u_{i} = \left( {y_{p + 1} , \ldots , y_{{p + N_{i} }} } \right) , \ldots } \\ \end{array} \ldots $$
(4)

where \( p = \mathop\sum\nolimits_{k = 1}^{i - 1} {N_{k} } \) and \( \mathop\sum\nolimits_{{{\text{k}} = 1}}^{\text{M}} {{\text{N}}_{\text{k}} = {\text{N}}.} \)

Using the macro-variables, the main relation of the well-known multistage scheme can be rewritten in the form

$$ \mathop {\hbox{min} }\limits_{{{\text{y}} \in {\text{D}}}} {\upvarphi }\left( {\text{y}} \right) = \mathop {\hbox{min} }\limits_{{{\text{u}}_{1} \in {\text{D}}_{1} }} \mathop {\hbox{min} }\limits_{{{\text{u}}_{2} \in {\text{D}}_{2} }} \ldots \mathop {\hbox{min} }\limits_{{{\text{u}}_{\text{M}} \in {\text{D}}_{\text{M}} }} {\upvarphi }\left( {\text{y}} \right), $$
(5)

where the subdomains \( {\text{D}}_{\text{i}} , 1 \le {\text{i}} \le {\text{M}} \), are the projections of the initial search domain \( {\text{D}} \) onto the subspaces corresponding to the macro-variables \( {\text{u}}_{\text{i}} , 1 \le {\text{i}} \le {\text{M}} \).

It should be pointed that the nested subproblems

$$ {\upvarphi }_{\text{i}} \left( {{\text{u}}_{1} , \ldots , {\text{u}}_{\text{i}} } \right) = \mathop { \hbox{min} }\limits_{{{\text{u}}_{{{\text{i}} + 1}} \in {\text{D}}_{{{\text{i}} + 1}} }} {\upvarphi }_{{{\text{i}} + 1}} \left( {{\text{u}}_{1} , \ldots , {\text{u}}_{\text{i}} ,{\text{u}}_{{{\text{i}} + 1}} } \right), \; 1 \le {\text{i}} \le {\text{M}}, $$
(6)

are the multidimensional ones in the block multistage scheme and this is the key difference from the initial scheme. Thus, this approach can be combined with the reduction of the domain \( D \) (for example, with the evolvent based on Peano curve) for the possibility to use the efficient methods of solving the one-dimensional problems of the multiextremal optimization [20].

The Peano curve \( y(x) \) lets map the interval of the real axis [0, 1] onto the domain D uniquely:

$$ \left\{ {y \in {\text{D}} \subset {\text{R}}^{\text{N}} } \right\} = \left\{ {y\left( x \right){ :}\, 0 \le x \le 1} \right\}. $$
(7)

The evolvent is the approximation to the Peano curve with the accuracy of the order \( 2^{{ - {\text{m}}}} \) where \( m \) is the density of the evolvent.

Application the mappings of this kind allows reducing multidimensional problem (1)–(2) to a one-dimensional one

$$ \varphi \left( {y^{ * } } \right) = \varphi \left( {y(x^{ * } )} \right) = min\left\{ {\varphi \left( {y(x)} \right){ :}\, x \in \left[ {0,1} \right]} \right\}. $$
(8)

4.2 Method for Solving the Reduced Global Optimization Problems

The information-statistical theory of global search formulated in [22] has served as a basis for the development of a large number of efficient multiextremal optimization methods – see, for example, [6,7,8,9, 16,17,18,19], etc. Within the framework of information-statistical theory, a general approach to parallelization computations when solving global optimization problems has been proposed – the parallelism of computations is provided by means of simultaneously computing the values of the minimized function \( {\upvarphi }\left( {\text{y}} \right) \) at several different points within the search domain.

The general computation scheme of Parallel Multidimensional Algorithm of Global Search (PMAGS) that is implemented in Globalizer is fully described in [1].

4.3 Implementation of Parallel Algorithm of Global Optimization

Let us consider a parallel implementation of the block multistage dimension reduction scheme described in Subsect. 4.1.

For the description of the parallelism in the multistage scheme, let us introduce a vector of parallelization degrees

$$ \uppi = \left( {\uppi_{1} ,\uppi_{2} , \ldots ,\uppi_{\text{M}} } \right), $$
(9)

where \( \uppi_{\text{i}} , 1 \le {\text{i}} \le {\text{M}}, \) is the number of the subproblems of the \( \left( {{\text{i}} + 1} \right) \)-th nesting level being solved in parallel, arising as a result of execution of the parallel iterations at the \( i \)-th level. For the macro-variable \( {\text{u}}_{\text{i}} \), the number \( \uppi_{\text{i}} \) means the number of parallel trials in the course of minimization of the function

$$ {\upvarphi }_{\text{M}} \left( {{\text{u}}_{1} , \ldots , {\text{u}}_{\text{M}} } \right) = {\upvarphi }\left( {{\text{y}}_{1} , \ldots , {\text{y}}_{\text{N}} } \right) $$

with respect to \( {\text{u}}_{\text{i}} \) at fixed values of \( {\text{u}}_{1} , {\text{u}}_{2} , \ldots ,{\text{u}}_{{{\text{i}} - 1}} \), i.e. the number of the values of the objective function \( {\upvarphi }({\text{y}}) \) computed in parallel.

In the general case, the quantities \( \uppi_{\text{i}} , 1 \le {\text{i}} \le {\text{M}} \) can depend on various parameters and can vary in the course of optimization, but we will limit ourselves to the case when all components of the vector \( \uppi \) are constant.

At every nested multistage dimension reduction level PMAGS is used. Let us remind that the parallelization is implemented by selection not a single point for the next trial (as in the serial version) but \( {\text{p}} \) points, which are placed into \( {\text{p}} \) intervals with the highest characteristics. Therefore, if \( {\text{p}} \) processors are available, \( {\text{p}} \) trials can be executed in these points in parallel. At a result, the solving of the problem at the i-th level generates p subproblems for the \( \left( {i + 1} \right) \)-th level.

5 Numerical Results

The computational experiments were conducted using the Lobachevsky supercomputer at the State University of Nizhny Novgorod (http://hpc-education.unn.ru/en/resources). The problems generated by the GKLS-generator [4] were selected for the test problems.

The results of the numerical experiments with Globalizer on an Intel Xeon Phi are provided in Table 1. The computations were performed using the Simple and Hard function classes with the dimensions equal to 4 and 5.

Table 1. Average number of iterations
Full size table

In the first series of experiments, serial computations using MAGS were executed. The average number of iterations performed by the method for solving a series of problems for each of these classes is shown in row I. The symbol “>” reflects the situation where not all problems of a given class were solved by a given method. It means that the algorithm was stopped once the maximum allowable number of iterations Kmax was achieved. In this case, the Kmax value was used for calculating the average number of iterations corresponding to the lower estimate of this average value. The number of unsolved problems is specified in brackets.

In the second series of experiments, parallel computations were executed on a CPU. The relative “speedup” in iterations achieved is shown in row II; the speedup of parallel computations was measured in relation to the serial computations (p = 1).

The final series of experiments was executed using a Xeon Phi. The results of these computations are shown in row III; in this case, the speedup factor is calculated in relation to the PMAGS results on a CPU using eight cores (p = 8).

6 Conclusion

In this paper, the Globalizer global optimization software system was presented for implementing a general scheme for the parallel solution of globally optimized decision making. The work is devoted to the investigation of the possibility to speedup the process of searching the global optimum when solving the multidimensional multiextremal optimization problems using the approach based on the application of the parallel block multistage scheme of the dimension reduction.

This research was supported by the Russian Science Foundation, project No 16-11-10150 “Novel efficient methods and software tools for the time consuming decision making problems with using supercomputers of superior performance”.