- NumPI - Mailing list — Dipartimento di Matematica, UniPI

Seminari su Mathematica
by Francesco Romani 02 Mar '16

02 Mar '16

Nell’ambito del corso di Esperienze di programmazione saranno tenuti 4 seminari introduttivi di circa 2 ore sul linguaggio Mathematica. Mercoledì 9/3 11-13 Aula C1 Introduzione a Mathematica Mercoledì 16/3 11-13 Aula C1 Grafica con Mathematica Mercoledì 23/3 11-13 Aula C1 Programmazione in Mathematica Mercoledì 27/4 11-13 Aula C1 Calcolo Numerico con Mathematica La partecipazione è aperta a tutti e vi prego di diffondere l’informazione ad eventuali interessati. Grazie, saluti, FR ____________________________ Prof. Francesco Romani Dipartimento di Informatica Via Buonarroti 2, 56127 PISA, ITALY Tel +39-050-2212734 FAX +39-050-2212726 http://www.di.unipi.it/~romani

1 0

Mathematica
by Francesco Romani 29 Feb '16

29 Feb '16

Anche quest’anno, all’interno del corso di Esperienze di Programmazione, faccio 4-5 seminari su Mathematica. L’orario è mercoledi 11-13 / Venerdi 16-18 Avendo una certra libertà per collocarli volevo sapere se qualcuno ha intenzione di seguirli e ha preferenze sugli orari. Grazie saluti Francesco ____________________________ Prof. Francesco Romani Dipartimento di Informatica Via Buonarroti 2, 56127 PISA, ITALY Tel +39-050-2212734 FAX +39-050-2212726 http://www.di.unipi.it/~romani

1 0

Optimization & Numerical Analysis seminars: Masciotta
by Federico Poloni 29 Feb '16

29 Feb '16

Speaker: Andrea Masciotta Affiliation: Dipartimento di Matematica, Università di Pisa Time: Monday, 7 March 2016, 14:30 Place: Sala Seminari Ovest, Dipartimento di Informatica, Università di Pisa Title: Minimization algorithms for compressive sensing Abstract: Compressive sensing is a new approach to digital signals acquisition and processing. Its main aim is the reconstruction of sparse signals or images (i.e. with few significant coefficients) from what was previously believed to be incomplete information. Compressive sensing has many potential applications, not only limited to the analysis of signals or images. In this talk we will first describe the main theoretical properties of compressive sensing, then three solution algorithms based on \ell_1 minimization will be presented, along with numerical experiments to highlight the main characteristics of these three methods in the framework of compressive sensing. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 0

Optimization & Numerical Analysis seminars: Miglierina
by Federico Poloni 17 Feb '16

17 Feb '16

Speaker: Enrico Miglierina Affiliation: Università Cattolica del Sacro Cuore, Milano Time: Thursday, 25 February 2016, 15:00 Place: Sala Seminari Est, Dipartimento di Informatica, Università di Pisa Title: Stability by set convergences: from Vector to Set optimization Abstract: (pdf) http://pages.di.unipi.it/fpoloni/files/seminari/Miglierina.pdf The notions of set convergences reveal to be very useful to study stability properties in vector optimization. Indeed, some results that show how the convergence of feasible region implies the convergence of efficient frontiers are known. The oldest ones are based on suitable compactness assumptions that concern the sequence of sets as a whole(see \cite{Attouch-Rihai,Bednarczuk2007,Luc-Lucchetti-Malivert,LoridanMorganRaucci,Penot-Sterna}). Moreover, more recently, some results about convergence of efficient frontiers have been obtained by replacing compactness by convexity (\cite{Lucchetti-Miglierina2004Opt,MM2005}). After a presentation of these results, the last aim of the talk is to extend this class of results to the broader framework of set optimization, that recently received an increasing attention in the literature (\cite{Gutierrez-Miglierina-Molho-Novo}). === Everyone is welcome! -- --federico poloni _______________________________________________ Numpi.di mailing list Numpi.di(a)listgateway.unipi.it http://listgateway.unipi.it/mailman/listinfo/numpi.di

1 0

[Dipartimento.di] Reminder: Optimization & Numerical Analysis seminars: Strabic
by Federico Poloni 18 Dec '15

18 Dec '15

Speaker: Nataša Strabić Affiliation: The University of Manchester Time: Wednesday, December, 9; h. 15:00 Place: Sala Seminari Ovest, Dipartimento di Informatica, Università di Pisa Title: Recent Progress on the Nearest Correlation Matrix Problem Abstract: In a wide range of applications it is required to replace an empirically obtained unit diagonal indefinite symmetric matrix with a valid correlation matrix (unit diagonal positive semidefinite matrix). A popular replacement is the nearest correlation matrix in the Frobenius norm. The first method for computing the nearest correlation matrix with guaranteed convergence was the alternating projections method proposed by Higham in 2002. The rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. Although a faster globally convergent Newton algorithm was subsequently developed by Qi and Sun in 2006, the alternating projections method remains very widely used. We show that Anderson acceleration, a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. This is particularly significant for the nearest correlation matrix problem with fixed elements because no Newton method with guaranteed convergence is available for it. Both methods for computing the nearest correlation matrix are based on repeated eigenvalue decompositions and so they can be infeasible in time-critical situations. We have recently proposed an alternative method to restore definiteness to an indefinite matrix called shrinking. The method is based on computing the optimal parameter in a convex linear combination of the indefinite starting matrix and a chosen positive definite target matrix. We show how this problem can be solved by the bisection method and posed as a generalized eigenvalue problem, and we demonstrate how exploiting positive definiteness in these two methods leads to impressive computational savings. The work on these two topics is joint with Nicholas J. Higham, and, for shrinking, with Vedran Šego. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143 ______________________________________________ Dipartimento.di mailing list Dipartimento.di(a)listgateway.unipi.it http://listgateway.unipi.it/mailman/listinfo/dipartimento.di

2 1

[Dipartimento.di] Optimization & Numerical Analysis seminars: Strabic
by Federico Poloni 03 Dec '15

03 Dec '15

Speaker: Nataša Strabić Affiliation: The University of Manchester Time: Wednesday, December, 9; h. 15:00 Place: Sala Seminari Ovest, Dipartimento di Informatica, Università di Pisa Title: Recent Progress on the Nearest Correlation Matrix Problem Abstract: In a wide range of applications it is required to replace an empirically obtained unit diagonal indefinite symmetric matrix with a valid correlation matrix (unit diagonal positive semidefinite matrix). A popular replacement is the nearest correlation matrix in the Frobenius norm. The first method for computing the nearest correlation matrix with guaranteed convergence was the alternating projections method proposed by Higham in 2002. The rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. Although a faster globally convergent Newton algorithm was subsequently developed by Qi and Sun in 2006, the alternating projections method remains very widely used. We show that Anderson acceleration, a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. This is particularly significant for the nearest correlation matrix problem with fixed elements because no Newton method with guaranteed convergence is available for it. Both methods for computing the nearest correlation matrix are based on repeated eigenvalue decompositions and so they can be infeasible in time-critical situations. We have recently proposed an alternative method to restore definiteness to an indefinite matrix called shrinking. The method is based on computing the optimal parameter in a convex linear combination of the indefinite starting matrix and a chosen positive definite target matrix. We show how this problem can be solved by the bisection method and posed as a generalized eigenvalue problem, and we demonstrate how exploiting positive definiteness in these two methods leads to impressive computational savings. The work on these two topics is joint with Nicholas J. Higham, and, for shrinking, with Vedran Šego. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143 ______________________________________________ Dipartimento.di mailing list Dipartimento.di(a)listgateway.unipi.it http://listgateway.unipi.it/mailman/listinfo/dipartimento.di

1 0

Optimization & Numerical Analysis seminars: Fenu
by Federico Poloni 19 Nov '15

19 Nov '15

Speaker: Caterina Fenu Affiliation: Università di Pisa Time: Thursday, November, 26; 9 am Place: Sala Seminari Ovest, Dipartimento di Informatica, Università di Pisa Title: Fast Computation of Centrality Indices Abstract: One of the main issues in complex networks theory is to find the “most important” nodes. To this aim, one can use matrix functions applied to its adjacency matrix. After an introduction on the use of Gauss-type quadrature rules, we will discuss a new computational method to rank the nodes of both directed and undirected (unweighted) networks according to the values of these functions. The algorithm uses a low-rank approximation of the adjacency matrix, then Gauss quadrature is used to refine the computation. Extended pdf abstract on http://www.di.unipi.it/~fpoloni/files/seminari/Fenu.pdf === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143

1 0

Optimization & Numerical Analysis seminars: Brugiapaglia
by Federico Poloni 23 Oct '15

23 Oct '15

Speaker: Simone Brugiapaglia Affiliation: Politecnico di Milano --- Laboratory for Modeling and Scientific Computing MOX Time: Tuesday, December 15, 11 am Place: Sala Seminari Est, Dipartimento di Informatica, Università di Pisa Title: CORSING: Sparse approximation of PDEs based on Compressed Sensing Abstract: We present a novel method for the numerical approximation of PDEs, motivated by recent developments in sparse representation, and particularly by compressed sensing. We named this approach CORSING (COmpRessed SolvING). Establishing an analogy between the sampling of a signal and the Petrov-Galerkin discretization of a PDE, the CORSING method can recover the best s-term approximation to the solution with respect to N suitable trial functions, with s<<N, by evaluating the bilinear form associated with the PDE against a randomized choice of m<<N test functions. This yields an underdetermined m x N linear system, that is solved by means of sparse optimization techniques. A theoretical analysis of the CORSING procedure is presented, based on the concepts of local a-coherence and restricted inf-sup property, along with numerical experiments that confirm the robustness and reliability of the proposed strategy. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 0

Seminario di Dierk Schleicher
by Dario A. Bini 16 Oct '15

16 Oct '15

Speaker: Dierk Schleicher Title: Newton’s method as an unexpectedly efficient root finder Time: Friday, October 23; 10:00 Place: Aula Magna, Dipartimento di Matematica Abstract: Newton’s method is well known as a root finder locally near the roots. It is often “not recommended” as a global root finder because of its “chaotic” properties. We give a very efficient theoretical upper bound on its speed of convergence: all roots of a degree d polynomial can be found with accuracy eps in O(d^2 log^4 d + d log|\log eps|) Newton iterations in the expected case — very close to the theoretical upper bound of O(d^2) for this method. In practice, all roots of polynomials of degree more than a million are found routinely and in (4log 2) d^2 iterations — in practice, this means less than a day for degree a million on standard laptops. A modified method, for which we do not yet have a complete theory, brings this down to 3 d log^2 d iterations, which in practice for certain polynomials finds all roots of degree a million in a matter of minutes. === Everyone is welcome! Dario A. Bini

1 0

Optimization & Numerical Analysis Seminars: Nesti
by Federico Poloni 14 Sep '15

14 Sep '15

Speaker: Tommaso Nesti (University of Pisa) Title: Numerical methods for computing the steady-state distribution of a G-network. Time: Wednesday, September 23; 16:00 Place: Sala seminari est, informatica Abstract: G-networks are a class of queueing networks introduced by E. Gelembe in 1989, which are characterized by the presence of positive and negative customers. Unlike classical queueing networks, the equations yielding the steady-state distribution of a G-network are nonlinear, resulting in the need of developing efficient numerical methods for their solution. In this talk we present two numerical methods for the computation of the steady-state distribution, namely a fixed point and a Newton-Raphson iteration. Using tools from nonnegative matrix theory, we prove that both methods are locally convergent to the fixed point, with linear and quadratic rate of convergence, respectively. We compare these methods with an existing algorithm, concluding that the Newton-Raphson iteration is a preferable choice for G-networks with a moderate number of queues. We conclude by suggesting a possible application for future research. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143

1 0

Evento AIRO (e conferenza relativa)
by Federico Poloni 31 Aug '15

31 Aug '15

Segnalo anche su questa lista l'evento sociale della conferenza AIRO: http://www.airo.org/conferences/airo2015/e-sport Si tratta di un torneo informale di un videogioco open source che si svolgerà al museo degli strumenti per il calcolo la sera dell'8 settembre. "The competition is open to all the conference participants, the accompanying persons, the organizers, any of their relative, friend and acquaintance (recursively), and whomever can claim any relationship with the conference, however tenuous and imaginative it may be. Fabulous final prices, and gadgets for all participants!" L'evento è collegato alla conferenza dell'AIRO (associazione italiana ricerca operativa) che si svolgerà la prossima settimana al dipartimento di informatica http://www.airo.org/conferences/airo2015/program. Per chi è interessato all'algebra lineare numerica segnalo in particolare il minisimposio "Numerical Methods for Complex Networks", in cui parleranno Francesca Arrigo, Dario Fasino e Caterina Fenu. -federico -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 0

Optimization & Numerical Analysis Seminars: Flores-Bazan and Locatelli
by Federico Poloni 29 Jun '15

29 Jun '15

Two seminars in optimization, one after the other, are taking place next Tuesday. Speaker1: Fabian Flores-Bazan (University of Concepcion) Title1: Strong duality in nonconvex optimization with a single equality and geometric constraints: applications to QP Time1: Tuesday, June 30; 15:00 Place1: Sala seminari est, informatica Speaker2: Marco Locatelli (Università di Parma) Title2: Some results about convex envelopes Time2: Tuesday, June 30; 15:45 Place2: Sala seminari est, informatica Abstract1: The validity of strong duality for a non convex optimization problem under a single equality and geometric constraints is characterized in a topological and geometric manner. In particular, a hidden convexity of the conic hull of joint-range of the pair of functions associated to the original problem, is obtained. Applications to derive KKT conditions without standard constraints qualification are also discussed. Several examples showing our results provide much more information than those appearing elsewhere, are given. Furthermore, first and second order optimality condition, for a non convex quadratic optimization problem under two quadratic equality constraints, are also presented. Finally, the standard quadratic problem involving a non necessarily polyhedral cone is analyzed in detail. The talk is based on joints works with G. Carcamo and F. Opazo. Abstract2: In this talk we discuss convex envelopes for some bivariate functions over general polytopes and for some $n$-dimensional quadratic functions over the unit simplex. We first give two formulations of convex envelope, a primal and a dual one. Next, we discuss how to derive the convex envelope for some bivariate functions over polytopes, provided that some given assumptions are fulfilled. It will turn out that the formula of the convex envelope can be derived through the solution of a parametric convex program or, equivalently, through the solution of the corresponding KKT system. For what concerns the $n$-dimensional quadratic functions over the unit simplex, we will first associate a graph to the quadratic function, and next we will show that the derivation of the convex envelope is related to the identification of the spanning forests over this graph. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143

2 1

Fwd: Call per data analyst
by Federico Poloni 18 Jun '15

18 Jun '15

Ricevo e inoltro questa offerta di lavoro. -federico -------- Forwarded Message -------- in Zanichelli cercano un data analyst junior a tempo determinato, e una parte della selezione (quella "tecnica") la faccio io. In allegato c'è la call: potreste girarla, per favore, a chiunque possa essere interessato? Gli interessati possono inviare cv e lettera di presentazione al nevio.dubbini(a)gmail.com. (NB il mio indirizzo email non c'è nella call allegata, quindi andrebbe comunicato nel testo dell'email). Grazie, ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Nevio Dubbini mail: nevio.dubbini(a)gmail.com web: sites.google.com/site/neviodubbini ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1 0

Fwd: [Dipartimento.di] avviso ciclo di seminari - 8, 10, 11 giugno
by Federico Poloni 04 Jun '15

04 Jun '15

In the framework of the research project "Mathematical models and computational methods for complex networks" by the University of Pisa, Paola Boito (Faculté des Sciences et Techniques Université de Limoges) will give three seminars on "Complex networks, functions of matrices and quadrature rules". The abstract is provided below. The seminars will take place in June at the Department of Computer Science of the University of Pisa: -- June 8th, 15:00-16:00, sala seminari est (room 351); -- June 10th, 10:00-11:00, sala seminari est (room 351); -- June 11th, 15:00-16:00, sala seminari est (room 351). Abstract. One cornerstone of our modern society is the use of different kinds of networks. Our cities are connected by a network of streets and railways, telecommunication networks including their wireless, mobile components, the internet, and the World Wide Web build the most important infrastructure for communication and information worldwide. Designing and managing such networks pose challenging algorithmic and numerical problems. These three talks are concerned with the development, analysis and application of numerical linear algebra tools for the quantitative study of important properties of large-scale complex networks, such as centrality, betweenness and communicability measures. Specifically, we design efficient algorithms for the fast approximation of the entries of matrix functions such as the exponential and the resolvent of adjacency matrices and graph Laplacians, as well as their traces. While these matrices are quite sparse, in the case of complex networks they behave very differently from the matrices associated with regular lattices (grids), such as those arising from discretizations of partial differential equations. Hence, there is a need to develop new methods, both computational and analytical, to deal with these very large-scale problems. Potential applications include the analysis of social networks, the study of biological and neurological networks, applications in physics and operations research, and so forth.

1 1

Optimization & Numerical Analysis Seminar: N. Vannieuwenhoven
by Federico Poloni 03 Jun '15

03 Jun '15

Speaker: Nick Vannieuwenhoven (KU Leuven) Title: Towards a perturbation theory for the tensor rank decomposition Date: Thursday, 4 June 2015. Time: 11:00 Place: Sala Seminari Ovest, dipartimento di informatica Abstract: The tensor rank decomposition is a decomposition of a tensor into a linear combination of rank-1 tensors. One of the key advantages of higher-order tensors is that this decomposition is generally unique, which allows for an interpretation of the individual rank-1 terms. Because of this property, the tensor rank decomposition has found application in several domains. For instance, they can be used as a clustering algorithm in an unsupervised learning setting assuming a certain statistical model wherein each of the rank-1 tensors in the decomposition will correspond with a cluster. In the applications where tensor rank decompositions arise, the tensor is usually known only up to some small perturbation error. This raises the following interesting problem: Suppose that the tensor is perturbed by a small quantity, by how much can the individual rank-1 terms change relative to the magnitude of the perturbation? Can it be unbounded? In this presentation, I will explore the definition of a possible condition number that answers these questions up to first order. == Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 1

Reminder: Optimization & Numerical Analysis Seminars: F. Romani
by Federico Poloni 13 May '15

13 May '15

Date: Thursday May 14, 2015 Time: 11:00 Place: Sala Seminari Ovest, dipartimento di informatica Speaker: Francesco Romani, dipartimento di informatica, U Pisa. Title: *Krylov subspace methods for the solution of linear systems* Abstract: Krylov subspace methods are iterative methods for the solution of linear systems which operate by multiplying the system matrix (sometimes also its transpose) by a vector. They are recommended when the system matrix is large and sparse or with a strong structure. The most common Krylov subspace methods are presented focusing the attention mainly on the practical and empirical aspects. == The seminar will be in Italian (but with slides in English). Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 0

Optimization & Numerical Analysis Seminars: F. Romani
by Federico Poloni 07 May '15

07 May '15

Date: Thursday May 14, 2015 Time: 11:00 Place: Sala Seminari Ovest, dipartimento di informatica Speaker: Francesco Romani, dipartimento di informatica, U Pisa. Title: *Krylov subspace methods for the solution of linear systems* Abstract: Krylov subspace methods are iterative methods for the solution of linear systems which operate by multiplying the system matrix (sometimes also its transpose) by a vector. They are recommended when the system matrix is large and sparse or with a strong structure. The most common Krylov subspace methods are presented focusing the attention mainly on the practical and empirical aspects. == The seminar will be in Italian (but with slides in English). Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 0

Reminder: Optimization & Numerical Analysis Seminar: M.G. Scutellà
by Federico Poloni 29 Apr '15

29 Apr '15

Our next seminar is tomorrow morning. Date: Thursday April 30, 2015 Time: 10:00 Place: Sala Seminari Ovest, dipartimento di informatica Speaker: Maria Grazia Scutellà, dipartimento di informatica, U Pisa. Title: *Optimizing Green Wireless LANs* Abstract: We consider problems arising in the design of Green (or energy-saving) Wireless Local Area Networks (GWLANs). In this context, decisions on powering-on a set of access points, and decisions on the assignment of the user terminals to the opened access points, have to be taken simultaneously. In particular, the level of power assigned to each access point may affect, in a nonlinear way, the capacity of the connections between the access points and the user terminals that are assigned to them. The aim is to minimize the overall power consumption of the access points, which is given by a linear dependency between the power consumed and the total demand assigned to the access points, via assignment costs. In the first part of the talk we present a Mixed Integer formulation with NonLinear constraints (MINLP) and an optimization approach, belonging to the framework of Branch and Benders Cut methods, which is based on the proposed MINLP formulation. In a non-standard fashion, the master problem of the approach includes the variables of the Benders subproblem, but relaxes their integrality. The approach has been tested on a large set of instances, and compared to a more traditional Benders decomposition algorithm on a subset of instances without the assignment costs, where the two approaches can be compared. The main achievements of the computational experimentation are shortly discussed. Then, in the second part of the talk, we address the optimization of GWLANs in a more realistic scenario, which takes into account also some uncertainty factors. Specifically, we present a robust optimization approach that incorporates both link capacity fluctuations and user mobility under Bertsimas and Sim's robust optimization paradigm. Again, preliminary computational results are shortly discussed. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143

1 0

Optimization & Numerical Analysis Seminar: M.G. Scutellà
by Federico Poloni 23 Apr '15

23 Apr '15

Date: Thursday April 30, 2015 Time: 10:00 Place: Sala Seminari Ovest, dipartimento di informatica Speaker: Maria Grazia Scutellà, dipartimento di informatica, U Pisa. Title: *Optimizing Green Wireless LANs* Abstract: We consider problems arising in the design of Green (or energy-saving) Wireless Local Area Networks (GWLANs). In this context, decisions on powering-on a set of access points, and decisions on the assignment of the user terminals to the opened access points, have to be taken simultaneously. In particular, the level of power assigned to each access point may affect, in a nonlinear way, the capacity of the connections between the access points and the user terminals that are assigned to them. The aim is to minimize the overall power consumption of the access points, which is given by a linear dependency between the power consumed and the total demand assigned to the access points, via assignment costs. In the first part of the talk we present a Mixed Integer formulation with NonLinear constraints (MINLP) and an optimization approach, belonging to the framework of Branch and Benders Cut methods, which is based on the proposed MINLP formulation. In a non-standard fashion, the master problem of the approach includes the variables of the Benders subproblem, but relaxes their integrality. The approach has been tested on a large set of instances, and compared to a more traditional Benders decomposition algorithm on a subset of instances without the assignment costs, where the two approaches can be compared. The main achievements of the computational experimentation are shortly discussed. Then, in the second part of the talk, we address the optimization of GWLANs in a more realistic scenario, which takes into account also some uncertainty factors. Specifically, we present a robust optimization approach that incorporates both link capacity fluctuations and user mobility under Bertsimas and Sim's robust optimization paradigm. Again, preliminary computational results are shortly discussed. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143

1 0

Reminder: Optimization & Numerical Analysis Seminar: F. Poloni
by Federico Poloni 16 Apr '15

16 Apr '15

Date: Thursday April 16, 2015 Time: 11:00 Place: Sala Riunioni Est, dipartimento di informatica Speaker: Federico Poloni, dipartimento di informatica, U Pisa. Title: *Methods for accurate invariant subspace computations.* Abstract: We consider two modelling problems, one arising in control theory (linear-quadratic regulator) and one arising in the modelling of queues (or buffers) under a continuous-time Markov model. The solution of both can be reduced to finding the invariant subspace of a suitable structured matrix, or equivalently solving a Riccati-like matrix equation. I will present linear algebra tools that can be used to solve them accurately; in particular: * a QR-like matrix factorization in which a tall skinny n x m matrix is factored as U*R, where R is m x m square invertible and U has a m x m identity submatrix and all its other entries bounded in modulus by 1. This factorization can be formulated as an optimization problem (maximum volume submatrix) or as finding a suitable set of basic variables in a tableau. * (if time allows) a numerical method for the Markov problem based on a technique (GTH method) to solve linear systems with a (possibly ill-conditioned) M-matrix without subtractions, obtaining high accuracy in both large and small entries of the solution. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143

1 0

Optimization & Numerical Analysis Seminar: F. Poloni
by Federico Poloni 10 Apr '15

10 Apr '15

Date: Thursday April 16, 2015 Time: 11:00 Place: Sala Riunioni Est, dipartimento di informatica Speaker: Federico Poloni, dipartimento di informatica, U Pisa. Title: *Methods for accurate invariant subspace computations.* Abstract: We consider two modelling problems, one arising in control theory (linear-quadratic regulator) and one arising in the modelling of queues (or buffers) under a continuous-time Markov model. The solution of both can be reduced to finding the invariant subspace of a suitable structured matrix, or equivalently solving a Riccati-like matrix equation. I will present linear algebra tools that can be used to solve them accurately; in particular: * a QR-like matrix factorization in which a tall skinny n x m matrix is factored as U*R, where R is m x m square invertible and U has a m x m identity submatrix and all its other entries bounded in modulus by 1. This factorization can be formulated as an optimization problem (maximum volume submatrix) or as finding a suitable set of basic variables in a tableau. * (if time allows) a numerical method for the Markov problem based on a technique (GTH method) to solve linear systems with a (possibly ill-conditioned) M-matrix without subtractions, obtaining high accuracy in both large and small entries of the solution. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143

1 0

Reminder: Optimization & Numerical Analysis seminars: R. Vandebril
by Federico Poloni 08 Apr '15

08 Apr '15

Date: Giovedi' 9 Aprile Time: 11:00 Place: Aula Seminari, dipartimento di matematica Speaker: Raf Vandebril, Department of Computer Science, KU Leuven. Title: *The Companion QR* Abstract: In this lecture we will propose a new fast and stable manner of computing roots of polynomials. Roots of polynomials are typically computed by putting the coefficients of the polynomial in the companion matrix and then computing the eigenvalues of this matrix. Exploiting the available low-rank structure leads to an algorithm of quadratic instead of cubic complexity. Several low-cost algorithms have already been proposed. Either they fully exploit the low-rank properties of the involved matrices by representing them for instance via quasiseparable factors, or they write the companion matrix as the sum of a unitary plus low rank matrix and exploit this structure. In this lecture we will use the second manner. However, only a single QR step requires the use of the low rank part. After that we can put the low rank term aside and continue only with the unitary matrix, translating the problem thereby to a unitary eigenvalue problem. Only in the end the low rank matrix is reconstructed to retrieve the eigenvalues. Numerical experiments validate the approach, illustrate its reliability and speed. The algorithm is compared against other available methods and a proof of backward stability is provided. This research is joint work with David S.\ Watkins and Jared L.\ Aurentz from Washington State University, USA and Thomas Mach from the KU Leuven, Belgium. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 0

Optimization & Numerical Analysis seminars: R. Vandebril
by Federico Poloni 01 Apr '15

01 Apr '15

Date: Giovedi' 9 Aprile Time: 11:00 Place: Aula Seminari, dipartimento di matematica Speaker: Raf Vandebril, Department of Computer Science, KU Leuven. Title: *The Companion QR* Abstract: In this lecture we will propose a new fast and stable manner of computing roots of polynomials. Roots of polynomials are typically computed by putting the coefficients of the polynomial in the companion matrix and then computing the eigenvalues of this matrix. Exploiting the available low-rank structure leads to an algorithm of quadratic instead of cubic complexity. Several low-cost algorithms have already been proposed. Either they fully exploit the low-rank properties of the involved matrices by representing them for instance via quasiseparable factors, or they write the companion matrix as the sum of a unitary plus low rank matrix and exploit this structure. In this lecture we will use the second manner. However, only a single QR step requires the use of the low rank part. After that we can put the low rank term aside and continue only with the unitary matrix, translating the problem thereby to a unitary eigenvalue problem. Only in the end the low rank matrix is reconstructed to retrieve the eigenvalues. Numerical experiments validate the approach, illustrate its reliability and speed. The algorithm is compared against other available methods and a proof of backward stability is provided. This research is joint work with David S.\ Watkins and Jared L.\ Aurentz from Washington State University, USA and Thomas Mach from the KU Leuven, Belgium. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 0

Fwd: [Dipartimento.di] Avviso Seminario: Leonardo Robol - Seminario di Esperienze di Programmazione
by Federico Poloni 31 Mar '15

31 Mar '15

Inoltro per altri possibili interessati. -------- Forwarded Message -------- Subject: [Dipartimento.di] Avviso Seminario: Leonardo Robol - Seminario di Esperienze di Programmazione Date: Mon, 30 Mar 2015 13:40:22 +0200 From: Gianna M. Del Corso <gianna.delcorso(a)unipi.it> To: dipartimento(a)di.unipi.it Nell'ambito del corso di Esperienze di Programmazione *Mercoledi' 1 Aprile 2015* - ore 11.00 Dip. di Informatica - Aula Seminari EST si terra' il seminario di LEONARDO ROBOL (Scuola Normale Superiore) INTRODUZIONE A JULIA Sarà presentato Julia, un linguaggio per il calcolo scientifico attualmente in fase di sviluppo. Verranno mostrate la sintassi e le principali differenze con i linguaggi attualmente più diffusi, come MATLAB e FORTRAN. Verrà fatta una panoramica delle principale caratteristiche della piattaforma, come i pacchetti aggiuntivi, il notebook IJulia, la gestione dei tipi e il raggiungimento di ottime performance (comparabili a quelle di C e FORTRAN) grazie all'utilizzo di LLVM come backend. Sarà infine presentato qualche esempio per mostrare le potenzialità di Julia per lo sviluppo di codice parallelo. L'interprete è open source e disponibile su http://julialang.org/. ======================== Riferimento: Gianna Del Corso Gianna M. Del Corso, PhD Dipartimento di Informatica, Universita' di Pisa Largo Pontecorvo, 3 56127 Pisa, Italy ph. +39-050-2213118 fax +39-050-2212726 Gianna M. Del Corso, PhD Dipartimento di Informatica, Universita' di Pisa Largo Pontecorvo, 3 56127 Pisa, Italy ph. +39-050-2213118 fax +39-050-2212726

1 0

Optimization & numerical analysis seminars: A. Frangioni
by Federico Poloni 19 Mar '15

19 Mar '15

In the next months we are holding a small cycle of joint seminars between the optimization and numerical analysis groups; their purpose is describing each other's research work, with an eye to possible new common areas of interest. Prof. Frangioni's seminar is the first one of the series. Time: Thursday 2015-Mar-19 (next week), h. 10:00 Place: Sala Seminari Ovest, Dipartimento di Informatica Speaker: Antonio Frangioni, Università di Pisa Title: *Iterative approaches for graph-structured linear systems arising in optimization* Abstract: When applying Interior Point (IP) algorithm to the solution of linear or convex separable optimization problems with strong graph structure, like the Min Cost Flow (MCF) problem, one has to repeatedly solve linear systems with strong graph structure. One of the two possible approach leads to systems with a M-matrix that is basically the weighted Laplacian of the underlying graph, where the weights (but not the graph) change at each iteration of the IP methods and typically become "very imbalanced" at the last ones. For this problem we have used two different techniques: Preconditioned Conjugate Gradient (PCG) methods, based on the idea of extracting a proper triangulated subgraph of the original graph which strictly contains a spanning tree. We have defined a new class of triangulated graphs, called Brother-Connected Trees (BCT), and discuss some fast heuristics for finding BCTs of "large" weight, starting from either the Kruskal algorithm or the Prim one. In addition we have studied multi-iterative techniques where the above PCG approach has been combined with specialized coarser-grid operators which preserve the graph structure of the projected matrix at the inner levels and smoothers, that have been completely characterized. Quite a lot of work still remains to do for understanding which is the best combination of preconditioning and coarsening at different stages of the overarching IP algorithm, implementing these techniques in an efficient solver, and extending them to "truly" interesting graph-structured problems like Multicommodity MCF ones. Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 1

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

NumPI