Fast Computing in Global Optimization:
Sequential and Parallel
Environment
Participants and Contacts
Delft University
of Technology
Nizhny Novgorod
State University
Full list of
participants
Project Summary
The project is aimed at researching a wide class of
time-consuming scientific and engineering optimization problems in order to
formulate a uniform approach to their effective solution in the environment of
high-performance multiprocessor computers including cluster systems built from
standard computer elements. The theoretical work within the framework of the
project includes:
- Forming a class of mathematical decision making problems
which model many important scientific and engineering applications and which
can be analyzed with the use of uniform algorithmic approach.
- Development and theoretical study of a uniform scheme of
parallel computations, within the framework of which effective numerical
methods for the formulated class of problems will be offered.
- Establishing the conditions of convergence, efficiency,
reliability, non-redundancy and scalability for the methods developed.
The practical part of the project contains:
- Specifying structure of the multiprocessor system and
environment necessary for development of the application software for parallel
computations.
- Developing the software for implementation of the methods
proposed and conducting a number of computing experiments to estimate the
efficiency and reliability of the proposed schemes of computations in
multiprocessor systems.
- Solving practical optimization problems from different areas
of applications (CAD/CAM, mechanics, pattern recognition, etc.)
The project implementation includes the following principal
tasks and corresponding stages:
- Forming a class of mathematical problems to be studied
within the framework of the project;
- Elaborating efficient sequential and parallel algorithms for
solving the problems based on the fundamental method of dimensionality
reduction and multistage simulation approach;
- Theoretical substantiation of the computational methods and
schemes proposed.
- Development of a new approach to parallel computations
(without a single control center), characterized by high scalability and
reliability;
- Software development and realization of computing
experiments to estimate the efficiency of the proposed schemes of computations
on multiprocessor systems.
- Solving applied optimal decision making problems.
Keywords
Computational methods, decision making, global optimization,
multiprocessor systems, parallelism, efficiency, reliability
Content of project
- Problem definition and central hypothesis of project
The essence of the project is to develop new computational
schemes that can be used effectively in high-performance (including
multi-processor) computer systems for solving problems of global optimization.
Application of the developed method of global optimization to real-life
problems.
- Method of approach:
The approach to the development of new computation schemes
consists of applying and further developing the new fundamental method for
reduction of complexity of the problem (based on the Peano curve type mapping,
nested optimisation scheme, index method, etc.), developed by the Russian
participants of the project in the problems of numerical analysis, in
combination with multistage simulation approximation based approach developed
by the Netherlands research group. As a result of application of the
essentially new reduction schemes, the multidimensional problem with
constraints is reduced to a family of one-dimensional subproblems with no
constraints. It is important to note that each problem of this family serves
to obtain the required solution of the initial multidimensional problem; at
the same time, the process of getting the estimates can be accelerated
significantly by means of solving simultaneously (in parallel) all or some
part of the problems of the family, provided that the search information
obtained during computations is shared. As a result of such an approach, the
multiprocessor system used for organizing the computations can be
inhomogeneous; its processors can have different performance and their
quantity can change during the computations.
- Objectives of the project:
The main objectives of the project consist in the development
of an integrated system of mathematical models, effective and reliable
sequential and parallel methods and software tools for solving time-consuming
decision making problems in different application areas and the definition of
practical methods for constructing high-performance parallel computing systems
with architecture adapted to the class of optimisation problems investigated.
Adapting of the developed system to be applicable to
real-life optimization problems using the approximation concepts.
Application of the developed system to some real-life
optimization problems in mechanics and medical diagnostics.
Significance and innovative aspects of the project
Significance and innovative aspects of the project consist of:
- designing a new dynamic model of optimal choice generalizing known
statements of decision making problems;
- developing new unified computational scheme based on the
methods for efficient parallel analysis of complex models with multi-extremes
functionals that require searching global optimal solutions in complex regions
and allow to investigate new classes of models with discontinuous criteria and
partially defined constraints;
- theoretical validation of the proposed methods;
- developing inhomogeneous architecture of multiprocessor
systems adjusted to efficient solving problems under consideration;
- elaborating new software for high-performance multiprocessor
systems;
- solving applied optimisation problems in mechanics and
medical diagnostics.