|
1st
PN2O meeting
About
Methods for Local and Global Optimization
Department
of Mathematics - University of Bologna
December 6, 2002
Program
|
|
11:30 -
|
Fabiana
Zama:
Inverse problems with
parallel architectures
|
|
12:30 -
|
Giulia
Spaletta:
Inverse filtering of
astronomical images
|
|
13:00 -
|
Giulia
Spaletta:
Precise numerical computation
|
|
14:00 -
|
Lunch
|
|
15:30 -
|
Thomas
Serafini:
Gradient projection methods
for large-scale quadratic
programs in training support
vector machines
|
|
16:10 -
|
Yaroslav
D. Sergeyev:
A test-problem generator for
global optimization methods
|
|
16:50 -
|
Valeria
Ruggiero:
A Newton inexact
interior-point method combined
with Hestenes multipliers'
scheme
|
|
17.30
-
|
Carla
Durazzi:
A modified augmented
lagrangian linesearch
interior-point Newton method for
nonlinear programming combined
by an inner iterative scheme
|
|
18:00 -
|
Federica
Tinti:
Numerical methiods for
monotone variational
inequalities
|
|
18:30 -
|
Closing
|
Abstracts
Inverse
Problems with parallel
Architectures
|
|
[Program]
|
|
|
|
Fabiana
Zama, Elena Loli Piccolomini, G. Landi
Department of Mathematics, University of
Bologna
We
focous our attention on three classes of
inverse problems very representative in the
area of imaging. Issues relative to
the ill-conditioning and the
regularization algorithms are analyzed for
the parallel computing environment. The
Conjugate Gradients iterations,
eventually coupled with the Tikhonov
functional, are analyzed as an efficient
iterative regularization method. In the
first application we reconstruct sequences
of dynamic Magnetic Resonance Images.
This application requires the solution of
many small size problems which are
independent and ill-posed.
The second problem is the image restoration
with space variant non separable Point
Spread Functions. In particular a domain
Decomposition method coupled with iterative
regularization methods is analyzed.
Finally we consider 3D tomographic problems
and propose a parallel iterative
regularization method suitable for
distributed memory architectures.
Inverse
filtering of astronomical images
|
|
[Program]
|
|
|
|
Giulia
Spaletta*, Luca
Caucci**
|
|
*
|
Department
of Mathematics, University of
Bologna
|
|
**
|
Department
of Computer Science, University
of Bologna
|
The
atmosphere of the earth and the instruments
of observation both constitute a
source of distortion in astronomical imaging.
Assuming linearity and space invariance of
the image formation system, the
observed image can be expressed as the
convolution of the original image with
the blurring function: if the latter is
known, then we are faced with the inverse
problem of classical deconvolution.
The restoration algorithms considered here
try to remove the blur using a priori
constraints, without the knowledge of the
blurring function; this approach is
often referred to as blind deconvolution.
The programming environment is that of
Mathematica. The effectiveness of this
class of methods is tested on both simulated
and real data.
Giulia
Spaletta*, Mark
Sofroniou**
|
|
*
|
Department
of Mathematics, University of
Bologna
|
|
**
|
Wolfram
Research Inc.
|
Arithmetic
systems such as those based on IEEE
standards currently make no attempt to
track the propagation of errors. A formal
error analysis, however, can be
complicated and is often confined to the
realm of experts in numerical analysis. In
recent years there has been a resurgence of
interest in automated methods for
accurately monitoring the error flow. In
this work a floating point system
based on significance arithmetic, in
Mathematica, will be described, together
with its differences over conventional fixed
precision floating point systems.
Gradient
Projection Methods for
Large-scale Quadratic Programs
in Training Support Vector
Machines
|
|
[Program]
|
|
|
|
Thomas
Serafini*,
Gaetano Zanghirati**,
Luca Zanni*
|
|
*
|
Department
of Mathematics, University of
Modena and Reggio Emilia
|
|
**
|
Department
of Mathematics, University of
Ferrara
|
A
common approach in solving the training
problem of the learning machine known as
Support Vector Machine, gives rise to a
special quadratic programming problem with
convex objective, a single linear quality
constraint and box constraints. Since the
Hessian matrix is dense and typically large
in real-world applications (105
or more), the numerical issues involved in
the solution of such a QP problem are a
challenge. This work is concerned with the
analysis and development of special
decomposition techniques which split the
main problem into a sequence of smaller QP
subproblems: we design a decomposition
scheme able to work efficiently when
the subproblem size is medium to large.
The key point is an efficient inner QP
solver for the quadratic subproblem:
we will show that in the case of gaussian
SVM, such a solver can be derived by the
Variable Projection Method (VPM). This
solver is well suited for implementations on
multiprocessor systems and it is used as the
basis to develop a parallel
decomposition technique.
A
Test-Problem Generator for
Global Optimization Methods
|
|
[Program]
|
|
|
|
Yaroslav
D. Sergeyev*,
Marco Gaviano**,
Dimitri E. Kvasov*,
Daniela Lera**
|
|
*
|
Engineering
Department, Calabria University
|
|
**
|
Department
of Mathematics, University of
Cagliari
|
A
procedure for generating three types of
classes of test functions (non-differentiable,
continuously differentiable, and twice
continuously differentiable) for
multiextremal multidimensional
box-constrained global optimization and a
corresponding package of C subroutines are
presented. Test functions are generated by
defining a convex quadratic function
systematically distorted by polynomials in
order to introduce local minima. Each test
class consists of 100 functions generated
randomly and is defined by the following
parameters: (i) problem dimension, (ii)
number of local minima, (iii) value of the
global minimum, (iv) radius of the
attraction region of the global minimizer,
(v) distance from the global minimizer to
the vertex of the quadratic function.
A complete information about each generated
function including locations and values of
all local minima is supplied to the user.
Partial derivatives are also generated where
it is possible.
A
Newton Inexact Interior-Point
Method Combined with Hestenes
Multipliers' Scheme
|
|
[Program]
|
|
|
|
Valeria
Ruggiero*,
Emanuele Galligani**,
Silvia Bonettini**
|
|
*
|
Department
of Mathematics, University of
Ferrara
|
|
**
|
Department
of Mathematics, University of
Modena and Reggio Emilia
|
This
work deals with the solution of nonlinear
programming problems arising from
elliptic control problems by Newton
Interior-Point method. At each step of the
method we have to solve a large scale
perturbed Newton system that is symmetric
and indefinite; an inner iterative
scheme, with adaptive stopping rule, can be
used in order to avoid unnecessary inner
iterations, especially when the current
outer iterate is far from the solution.
Under conditions that guarantee the
nonsingularity of the matrix of the system
and the boundedness of its inverse, the
system can be viewed as the Lagrange
necessary conditions for the minimum
point of a quadratic programming problem and
it can be efficiently solved by the
iterative Hestenes' multipliers scheme. This
scheme involves at each iteration a
solution of a smaller sparse symmetric
positive definite system that can be solved
by efficient direct sparse solvers.
A
Modified Augmented Lagrangian
Linesearch Interior-Point Newton
Method for Nonlinear Programming
Combined by an Inner Iterative
Scheme
|
|
[Program]
|
|
|
|
Carla
Durazzi, Valeria Ruggiero
Department of Mathematics, University of
Ferrara
In
these recent years much research activity
has been devoted to the field of
Interior-Point methods for linear and
nonlinear programming problems. In
particular, a new Interior-Point algorithm
for nonlinear programming problems has been
proposed by Tapia and Argaez [JOTA,
2002] which is based on the notion on "quasi-central
path" and which uses a modified merit
function that couples the objective function
with the constraints. The aim of this work
is to introduce, for the Newton iteration
occurring at each step of the algorithm, an
iterative solver with an adatpive
termination rule which avoids unnecessary
iterations when we are far from the solution.
This approach seems to be promising
especially for large and structured
nonlinear problems. The global convergence
of the obtained scheme has already
been proved, while the numerical
experimentation is in progress.
Numerical
Methods for Monotone Variational
Inequalities
|
|
[Program]
|
|
|
|
Federica
Tinti
Department of Mathematics, University of
Padova
We
study stationary iterative methods for
solving variational inequality problems.
These include projection methods and
extragradient methods. The projection
methods require the restrictive
assumption that F or F-1 be strongly
monotone for convergence, while the
extragradient methods require only that F be
monotone and that a solution exists.
Both methods use little storage and can
readily exploit any sparsity or separable
structure in F or in X. Unlike the
extragradient methods, the projective
methods require only one projection
per iteration rather than two.
The choice of the projection parameter a
must be adaptive because, if a is too small
the convergence is slower; whereas if a is
too large, there might be no convergence at
all. We focus on some specific
extragradient methods making use of
different choices of a. We also study
a new projection algorithm which consist of
two steps per iteration: the first step
constructs an appropriate hyperplane which
separates the current iterate from the
solution of the problem; the second
step determines the next iterate as the
projection of the current iterate onto the
intersection of the feasible set with the
halfspace containg the solution set.
|
|
