Last year
research advances
Research
Advances
Perturbed
dumped Newton and SQP-IP methods for
discretized optimal control problems
Researchers.
V. Ruggiero, S. Bonettini, F. Tinti.
Advances.
A standard approach to the solution of the variational
inequalities provides the use of the Fisher’s functions;
this leads to semismooth systems, which can be effectively
solved by the semismooth inexact Newton method
[Facchinei, Fischer, Kanzow, in G. Di Pillo and F. Giannessi (eds.),
Nonlinear Optimization and Applications, 1996].
In [BT-06] we introduced
a new inexact nonmonotone mehtod which generalizes the one
proposed in [B-05] for the smooth case.
We developed the convergence analysis for the nonmonotone case,
proving the global convergence theorems under suitable hypotheses.
Furthermore, we tested the effectiveness of the nonmonotone scheme
on a set of variational inequality problems.
The solution of the linear system (Newton equation) arising at each step
of the interior point method is a crucial issue in the nonlinear
optimization context.
We focused on the different representations of the linear system which
can be obtained by applying elimination techniques in order to achieve
the symmetry of the coefficient matrix. From the literature, we devised
four different representations of the system, which, when we have
inequality constraints, lead to a different coefficient matrix.
Recently, many authors proposed the Preconditioned Conjugate Gradient (PCG)
method as iterative solver for the Newton equation.
We analyzed the PCG method applied to the four variants of the Newton equation,
with suitable symmetric indefinite preconditioners.
We revised the convergence theorems and we proved the main results
under a weaker assumptions then the ones required in
[Lukš&scheck;an and Vlcek, Num. Lin. Algebra with Appl., 1998]
and [Lukšan, Matonoha, Vlcek, Num. Lin. Algebra with Appl., 2004].
Furthermore, for the solution of the Newton equation, we considered two
different PCG algorithms known in literature and we introduced a new one.
All these algorithms are equivalent in exact arithmetic, but the finite
precision could produce a different behaviour, as the numerical
experiments in [BRT-06,
B-06] show.
We compared the effectiveness of the whole interior point algorithm with
respect to the different representations of the inner linear system on a
set of large-scale nonlinear programming problems with inequality
and both equality and inequality constraints. Furthermore, we built three
versions of the interior point algorithm implementing the different
PCG algorithms as inner solver and we compared the performances on a
set of literature nonlinear programming problems.
The numerical experience showed also the effectiveness of the BLKFCLT
package employed for the factorization of the preconditioner with respect
to tho other state-of-the-art factorization routines.
In the last years, the interior point methods have shown to be an
effective approach to the numerical solution of optimal control problems
[Mittelmann, Maurer, Computational Optimization and Applications, 1999, 2001].
Indeed, by applying a convenient discretization technique to the optimal
control problem, we can obtain a finite dimensional nonlinear
programming (NLP) problem having sparse and structured Hessian and
Jacobian matrices.
We collected 25 nonlinear programming problems known in literature arising
from literature elliptic and parabolic control problems. We focused on the
discretization techniques and for each problem we described in detail the
structure of the Hessian and Jacobian matrices. For the elliptic problems
we present also the graphs of the discrete solution and the minimum value
of the discrete functional for a given stepsize. The paper describing the
collection is downloadable from
dm.unife.it/~bonettini/ip_pcg/controllo.htm. We produced also the AMPL models of the parabolic problems, which
can be found in the same web page together with the link to the
prof. Mittelmann’s web page, where the models related to the
elliptic problems can be downloaded.
We coded the algorithm described in
[BGR-05,
BRT-06,
B-06] using the C++ language.
A binary version of the new package, called IP-PCG is downloadable from the web page
dm.unife.it/~bonettini/ip_pcg.htm
for the HP-Itanium2 platform. We build also a partial AMPL interface written
in C++ language included in the package, which allows to exploit the
AMPL generated .nl files arising from an AMPL model of
a programming problem. This interface has been very important in the
testing phase of the code on problems belonging to the standard test set;
the performances of IP-PCG, on a set of test problems can be found in
[BRT-06,
B-06].
[Top]
Variable
projection methods: a successful approach to
SVMs and large-scale simply constrained QP
Researchers.
L. Zanni, G. Zanghirati.
Advances.
The research activity in the Statistical Learning field has been mainly focussed onto
two objectives: the improvement of the PGPDT software, dedicated to the solution of
binary classification problems through Support Vector Machines (SVMs) and
the extension of the PGPDT approach also to regression problems.
The first goal has been met by continuing the successful development of the
PGPDT software (available at http://dm.unife.it/gpdt):
the new version released in July 2006 allows to exploit the power of distributed-memory
multiprocessor systems to train million samples SVMs, thus largely overcame the
limits of traditional standard-training scalar softwares
[ZSZ-06a,
ZSZ-06b].
When Statistical Learning very-large-scale problems are concerned, a novel development
has been taken through recent algorithms called "cascade algorithms": here,
particular partitioning strategies of the training set have been shown to be very effective
if they are applied together with the decomposition technique implemented by the
PGPDT approach.
The second research goal have been met by generalizing the algorithms considered for
the binary classification, so that to make them able to solve the quadratic programming
problem that arising in the SVMs training for linear and nonlinear regression problems.
The integration of this generalizations into both the GPDT (serial) and the PGPDT (parallel)
softwares already got a very advanced prototypical stage, so that the new versions
will possibly be released quite soon.
[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.
Advances.
The development, as well as both the theoretical and the
experimental study of new algorithms for the solution of constrained
Lipschitzian global optimization problems have continued in the
direction where both the objective and the constraints functions are
multiextremal Lipschitzian "black-box" functions, even
only partially defined and not necessarily differentiable.
The papers [SKK-07a,
S-06a,
KKS-06] deal with
the monodimensional case where multiextremal constraints are
considered, where the feasible region is composed by disjoint
nonconvex subregions. A new technique for the construction of the
support functions has been proposed, which belongs to the
"index scheme" class. This technique involves neither
supplementary variables nor penalty coefficients. The "local
tuning" technique has also been successfully applied to catch
the objective and the constraints functions' behaviour, as it was
shown to be very effective for unconstrained cases.
In the papers [SK-06,
KS-06] a new approach is taken to the solution
of multidimensional problems with box constraints. Based on an
effective "partition strategy" recently proposed, a new
scheme for the extension of monodimensional minimization algorithms
to multidimensional cases is applied to the development of a
minimization method which is characterized by: (1) a new way to
estimate the Lipschitz constant, (2) the new partition strategy of
the research domain and (3) a new idea for balancing the workload of
the local and global phases during the global optimum lookup.
Convergence conditions are given for this new method and its
efficiency is tested in a large number of test functions.
The considered global optimization techniques was applied to the
solution of a real-world control problem
[CPS-06]
as well as to the determination of the
minimal-root of an equation [S-06b]. The
latter was solved by the new global optimization techniques much
more efficiently then even before.
[Top]
Symbolic
calculus and parallel computing for error
propagation automatic control
Researchers.
G. Spaletta.
Advances.
The main differences between the proposed "Significant Arithmetic"
and the standard IEEE finite arithmetic have been deeply analysed.
Splitting methods as well as exponential integrators have been analysed
for the solution of ordinary differential equations by the Mathematica
software
[SS-06a,
SS-06b,
SS-06c].
Also, deconvolution and other computationally effective methods for both the
2D and the 3D image reconstruction problems have been investigated
[SC-06,
Sp-06].
[Top]
Parallel
domain decomposition techniques for
space-variant blurred images restoration
Researchers.
F. Zama, E. Loli Piccolomini, G. Landi.
Advances.
The main research activity concerned both the
study and the implementation of nonlinear regularization methods,
with applications to medical imaging. In particular, diffusion
functionals based on the Total Variation principle were studied from
a theoretical viewpoint, through the analysis of effective numerical
methods for the solution of the regularization problem generated by
these functionals, as well as from an application-oriented
viewpoint, through the implementation and tuning of algorithms for
the enhancement of Nuclear Magnetic Resonance (NMR) images and
sequences.
The numerical methods considered for the solution of the
regularization problem belong to the class of unconstrained
nonlinear optimization methods.
In more details, the research activity was focused on the study of
numerical methods for function minimization subject to equality and
inequality constraints, with applications to blurred images
reconstruction and enhancement, mainly for biomedical purposes.
The convergence conditions of the proposed methods were studied and
implementation issues were carefully considered through prototypical
codes. These research codes were tested on synthetic as well as on
real-world data, the latter being for instance Magnetic Resonance
(MR) and spectroscopic data provided by the Department of Clinic
Physiopathology at the "Careggi" Hospital in Florence (Italy).
Finally, iterative regularization methods were considered for cases
where positivity constraints are imposed to the solution;
applications giving similar cases include inverse problems connected
to image restoration and image reconstruction.
In [L-06] an active-set method is proposed to
compute the (Tikhonov) regularized solutions with positivity constraints, where
oscillations are removed. In [L-07] an effective stopping
criterion is introduces for the Lanczos method, to compute the regularized
solution of a least squares problem.
A
parallel computing approach to dynamic
magnetic resonance imaging
Researchers.
F. Zama, E. Loli Piccolomini, G. Landi.
Advances.
The paper [LL-06] introduces a new
reconstruction algorithm for Magnetic Nuclear Resonance data, where
the signal is smoothly represented by B-splines.
|
|
