Italian FIRB Project on
 Parallel Algorithms and Numerical Nonlinear Optimization

Last year research advances

Research activities
  1. Perturbed dumped Newton and SQP-IP methods for discretized optimal control problems  [description]
  2. Variable projection methods: a success approach for SVMs and large-scale simply contrained QP  [description]
  3. Adaptive diagonal space-filling curves: linking geometric Lipschitz and Bayesian approaches for non-differentiable global optimization.  [description]
  4. Symbolic calculus and parallel computing for error propagation automatic control  [description]
  5. Parallel domain decomposition techniques for space-variant blurred images restoration  [description]
  6. A parallel computing approach to dynamic magnetic  resonance imaging  [description]

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 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 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].


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 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.


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.


 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].


 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.



Status: completed.

 Last updated: 15/3/2007.