Speaker: Margherita Porcelli
Affiliation: Università di Bologna
Time: Friday, 04/06/2021, 16:00
Title: Relaxed Interior point methods for low-rank semidefinite
programming problems
In this talk we will discuss a relaxed variant of interior point
methods for semidefinite programming problems (SPDs). We focus on
problems in which the primal variable is expected to be low-rank at
optimality. Such situations are common in relaxations of combinatorial
optimization problems, for example in maximum cut problems as well as
in matrix completion problems. We exploit the structure of the sought
solution and relax the rigid structure of IPMs for SDP. In
anticipation to converging to a low-rank primal solution, a special
nearly low-rank form of all primal iterates is imposed. To accommodate
such a (restrictive) structure, the first order optimality conditions
have to be relaxed and are therefore approximated by solving an
auxiliary least-squares problem. The relaxed interior point framework
opens numerous possibilities how primal and dual approximated Newton
directions can be computed. In particular, it admits the application of
both the first- and the second-order methods in this context. In this
talk we will focus on second-order approaches and discuss the
difficulties arising in the linear algebra phase. A prototype
implementation is shown as well as computational results on matrix
completion problems. In particular, we will consider mildly-ill
conditioned and noisy random problems as well as problems arising in
diverse applications as the matrix to be recovered represents city-to-
city distances, a grayscale image, game parameters in a basketball
tournament.
This is joint work with S. Bellavia (Unifi) and J. Gondzio (Univ.
Edinburgh)
https://www.dm.unipi.it/webnew/it/seminari/relaxed-interior-point-methods-l…
Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4
Speaker: Alfredo Buttari
Affiliation: CNRS, IRIT, Toulouse
Time: Friday, 14/05/2021, 16:00
Title: Reducing the complexity of linear systems solvers through the
block low-rank format
Direct linear system solvers are commonly regarded as robust methods
for computing the solution of linear systems of equations. Nonetheless,
their complexity makes the handling of very large size problems
difficult or unfeasible due to excessive execution
time or memory consumption. In this talk we discuss the use of low-rank
approximation techniques that allow for reducing this complexity at the
price of a loss in precision which can be reliably controlled. To take
advantage of these low-rank approximations, we
have designed a format called block low-rank (BLR) whose objective is
to achieve a favorable compromise between complexity and efficiency of
operations thanks to its regular structure. We will present the basic
BLR format as well as more advanced variants and the associated
algorithms; we will analyze their theoretical properties and discuss
the issues related to their efficient implementation on parallel
computers. We will specifically focus on the use of BLR for the
solution of sparse linear systems. The ombination of this format with
sparse direct methods, such as the multifrontal one, leads to efficient
parallel solvers with scalable complexity. These can either be used as
standalone direct solvers or in combination with other techniques such
as iterative or multigrid methods. We will present experimental results
on real-life problems obtained by integrating the BLR format within the
MUMPS parallel sparse direct solver.
https://www.dm.unipi.it/webnew/it/seminari/reducing-complexity-linear-syste…
Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4
Speaker: Stefano Pozza
Affiliation: Charles University, Prague
Time: Friday, 07/05/2021, 16:00
Title: The Short-term Rational Lanczos Method and Applications
Rational Krylov subspaces have become a reference tool in dimension
reduction procedures for several application problems. When data
matrices are symmetric, a short-term recurrence can be used to generate
an associated orthonormal basis. In the past this procedure was
abandoned because it requires twice the number of linear system solves
per iteration than with the classical long-term method. We propose an
implementation that allows one to obtain key rational subspace matrices
without explicitly storing the whole orthonormal basis, with a moderate
computational overhead associated with sparse system solves. Several
applications are discussed to illustrate the advantages of the proposed
procedure.
https://www.dm.unipi.it/webnew/it/seminari/short-term-rational-lanczos-meth…
Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4
