Unit 1 research program
Research
description
The
project of the research unit is concerned
with the analysis and the development of
nonlinear, local and global optimization
methods for the numerical solution of high
complexity problems in the context of
parallel computing.
Two
topics will be considered:
- local
optimization methods,
- global
optimization methods.
Three
phases are provided for each topic:
- determination
of prototypical high complexity
problems;
- development
and analysis of classical numerical
methods and new parallel methods,
with special attention devoted to
theoretical convergence and
numerical stability;
- parallel
implementation and evaluation of the
algorithms with respect to both the
multiprogramming degree and the
performance parameters in the
context of parallel computing.
A
brief description follows.
Local
Optimization
Constrained
optimization methods to solve optimal
control problems, parameters identification
and variational inequalities will be studied.
The aim is to develop computational kernels
for parallel computers. We will study
the following methods: the sequential
quadratic programming methods, the interior
point methods, the perturbed damped
Newton method and projection methods.
Discretization techniques provide
efficient methods for solving optimal
control problems with control and
state constraints. There are two different
approaches for the numerical solution of
such control problems: a direct
discretization of the whole problem leading
to a large finite-dimensional constrained
optimization problem (full discretization
approach) or the use of an iterative
method which reduces the original problem
into a sequence of infinite-dimensional
quadratic control problems, which then
still need to be discretized (SQP
approach). The literature on the latter
approach is quite extensive (see the special
issue "SQP-based direct
discretization methods for practical optimal
control problems", V.H. Schultz
ed., J. Comp. Appl. Math. 120 (2000)), while
the former one has more recently been
considered for the solution of real-life
problems, since the new progress on
the solution techniques for very large
constrained nonlinear programming problems.
A well-known full discretization method is
the Inexact Sequential Quadratic
Programming Interior Point method (see, e.g.,
[W93, LS99]). Sequential Quadratic
Programming methods reduce the nonlinear
problem into a sequence of quadratic
subproblems; then, each of the quadratic
subproblems is solved by an Interior Point
method only within a certain accuracy. As an
alternative, we propose to solve directly
the nonlinear discrete control problem with
a Perturbed-Damped Newton method. The whole
approach is suitable to parallel
implementation. It is possible to establish
a global convergence theory for this method.
However, the determination of a "good"
initial point of the whole iterative process
is strongly recommented and we will analyze
different strategies.
The
Variable Projection Methods can be used in
the solution of special constrained
minimum problems and variational
inequalities. These methods will be applied
to particular minimum problems arising in
Pattern Recognition. An interesting
application of the Variable Projection
methos is concerned with a
classification technique known as Support
Vector Machine (SVM)[CV95]. From the
computational point of view, the main effort
in the implementation of a SVM
consists in solving a quadratic programming
problem with special constraints (box
constraints and one linear equality
constraint), having size equal to the
number of points of a data set called the training
set. When this number is large, a
decomposition technique may be used. We will
analyse this technique, exploiting the
parallel features of the approach, in order
to heavely decrease the computational
complexity of the problem.
Global
optimization
Among
the techniques recently used for solving
Lipschitz global optimization problems over
hyperintervals, two promising approaches
will be studied: diagonal algorithms
[P96] and methods based on Peano-Hilbert
space-filling curves [SS00]. An
additional, unifying approach will be
studied, known as the technique of the adaptive
diagonal curves. These tools will allow
us to construct new methods for
solving non-differentiable problems by using
geometric Lipschitz ideas and a Bayesian
approach. Convergence conditions for
the new algorithms will be studied in
depth. In order to ensure an high
convergence rate of the new techniques,
adaptive estimates of the local Lipschitz
constants will be given by using the local
tuning ideas.
The proposed methods will be generalized to
the case of problems with
multiextremal partially defined constraints.
When Lipschitz constans-based mathods are
used to solve such problems, the reduction
to the unconstrained case is not obvious;
hence the index scheme [SS00] will be
applied for such a reduction. To lower
the initial problem size, Peano-Hilbert
space-filling curves will be adopted. A
special study will be devoted to the
behaviour of the new techniques while
solving reduced Holder one-dimensional
problems. Since the methods to be developed
will belong to the "Divide the
best" family, it will be possible to
construct their parallel versions by
applying the scheme introduced in [S98-2].
Convergence conditions for the
obtained parallel methods will be
established. A deep study will be dedicated
to the theoretical conditions for an
efficient parallelization. Particularly, the
problem of non-redundant parallelism will be
faced.
In
the case of differentiable global
optimization, stochastic methods using both
local searches and Lipschitz ideas
will be proposed and analyzed.
Suitable test functions will be studied,
together with the principles for their
generation. All the proposed methods
will be first tested on workstation, then
implemented on parallel computers. The
parallel codes will be evaluated by using
both ad hoc generated test functions
and test functions taken from the literature,
as well as some control problems.
References
|
[W93]
|
S.J.
Wright, Interior Point
Methods for Optimal Control of
Discrete Time Systems, JOTA 77
(1993).
|
|
[LS99]
|
F.
Leibfritz, E.W. Sachs, Inexact
SQP interior point methods
and large scale optimal control
problems, SIAM J.
Control Optim. 38 (1999).
|
|
[CV95]
|
C.
Cortes, V.N. Vapnik, Support
Vector Network,
Machine Learning 20
(1995).
|
|
[P96]
|
J.D.
Pintér, Global Optimization
in Action, Kluwer
Academic Publ. (1996).
|
|
[SS00]
|
R.G.
STRongin, Ya.D. Sergeyev, Global
Optimization with non-convex
constraints: sequential and
parallel algorithms,
Kluwer Academic Publ. (2000).
|
|
[S98-2]
|
Ya.D.
Sergeyev, On convergence of
“Divide the best”
global optimization algorithms,
Optimization 44 (1998).
|
[Top]
Research
Activities
Perturbed
dumped Newton and SQP-IP methods for
discretized optimal control problems
Researchers.
V. Ruggiero, S. Bonettini, F. Tinti.
Description.
In order to solve discretized optimal
control problems, we will consider both
"SQP-Interior Point" and "Perturbed
Dumped Newton" methods. For the
latter, there is the possibility to
adaptively modify the perturbation parameter
in the Karush-Kuhn-Tucker system and the
accuracy of the solution in the perturbed
Newton equation, when one is still far
away from the solution of the problem at an
early stage. The whole approach is suitable
to parallel implementation. It is possible
to establish a global convergence
theory for this method. However, the
determination of a "good"
initial point of the whole iterative process
is strongly recommented; we will analyze
different strategies, as penalization and
continuation methods. We will first
determine a set of test problems and then we
will compare the considered methods on
parallel architectures.
Expected
results. Study and analysis of classical
methods and new methods; analysis of the
more promising algorithms, with special
attention to the parallel architectures
and numerical experimentation. Development
of the computational kernels for some
meaningful model problems. Achievement of
benchmarks for the performance evaluation of
the methods related to the above codes.
[Top]
Variable
projection methods: a success approach for
SVMs and large-scale simply contrained QP
Researchers.
L. Zanni, G. Zanghirati.
Description.
We will continue the investigation of the
Variable Projection methods. These
methods will be applied to special minimum
problems arising in Pattern Recognition. An
interesting application of the Variable
Projection methos is concerned with the
binary classification technique, known as
Support Vector Machine (SVM). From the
computational point of view, the main effort
in the implementation of a SVM
consists in solving a quadratic programming
problem with special constraints, having
size equal to the number of points of
the training set. When this number is
large, a decomposition technique may be used.
We will develop this technique, exploiting
the parallel features of the approach,
in order to heavely decrease the
computational complexity of the problem. To
evaluate the effectiveness of the parallel
code, it will be compared with already
available codes.
Expected
results. Analysis of the Variable
Projection Methods for the implementation of
a SVM; implementation of decomposition
techniques on parallel architectures and
numerical experimentation. Achievement
of benchmarks for the performance evaluation
of the underlying methods.
[Top]
Adaptive
diagonal space-filling curves: linking
geometric Lipschitz and Bayesian
approaches for non-differentiable global
optimization
Researchers.
Ya. D. Sergeyev, D. Lera, D. Kvasov.
Description.
We will analyze global osptimization methods
based on adaptive diagonal space-filling
curves. These instruments will allow us to
construct new methods for solving
non-differentiable problems by using
geometric Lipschitz ideas and Bayesian
approach. Convergence conditions for the new
algorithms will be studied in depth. In
order to ensure a fast speed of the new
techniques, adaptive estimates of the local
Lipschitz constants will be done by using
the local tuning ideas. The methods proposed
will be generalized to the case of problems
with multiextremal partially defined
constraints. Since for such problems and
methods working with Lipschitz constans
reduction to the unconstrained case is not
obvious, the index scheme will be applied
for such a reduction. In order to reduce the
dimension of the initial problem,
Peano-Hilbert space-filling curves will be
adopted. A special study will be dedicated
to behavior of the new techniques while
solving reduced Holder one-dimensional
problems. Since the methods to be developed
will belong to the "Divide the
best" family, it will be possible to
construct their parallel versions by
applying the scheme introduced in.
Convergence conditions for the obtained
parallel methods will be established. A deep
study will be dedicated to obtaining
theoretical conditions of an efficient
parallelization. Particularly, the problem
of non-redundant parallelism will be faced,
i.e., establishing a number of parallel
processors which will not lead to generation
of redundant (in comparison with the
sequential case) calculations. In the case
of differentiable global optimization,
stochastic methods using both local searches
and Lipschitz ideas will be proposed and
studied. A study on test functions and
principles of their generation will be done.
All the methods proposed will be implemented
(after the first tests on workstation) on
parallel computers and tested o n ad hoc
generated test functions, test functions
taken from literature, and some control
problems.
Expected
results. Study and analysis of classical
methods and new methods; analysis of the
more promising algorithms, with special
attention to the parallel architectures and
numerical experimentation. Development of
the computational kernels for some
meaningful model problems. Achievement of
benchmarks for the performance evaluation of
the methods related to the above codes.
[Top]
|
|
