Charles University Chapter of SIAM

Our Events - SIAM SC Seminar - Other Events

Meeting of European SIAM Chapters 2017

Date: 28/08/2017 09:00 - 30/08/2017 13:00
Place: Prague, V Holešovičkách 747/2

Meeting of European SIAM Chapters (MESIAM 2017) was held in Prague on August 28-30, 2017. See the event description at the SIAM News Blog.

List of Participants

Shanzai Lee, Shenzen
Kejun Tang, Shanghai
Anna Thunen, Aachen
Daniel Bankmann, Berlin
Qays Shakir, Galway
Enrique Sita Sanmartin, Heidelberg
Xiaoyu Chen, Heidelberg
Xuke Hu, Heidelberg
Shiyue Zhang, Heidelberg
Alexandru Iosif, Magdeburg
Cleophas Kweyu, Magdeburg
Manuela Hund, Magdeburg
Carolin Penke, Magdeburg
Rana Atta Ur Rahman, Magdeburg
Han Cao, Mannheim
Marie Kubínová, Prague
Petr Lukáš, Prague
Jan Kuřátko, Prague
Marek Netušil, Prague
Erika Maringová, Prague
Jakub Hrnčíř, Prague
Tomáš Gergelits, Prague
Vít Orava, Prague
Petr Pelech, Prague
Bernd Perscheid, Trier
Claudia Adams, Trier
Dennis Kreber, Trier

Invited Lectures

Unusual spectral properties of a class of Schrödinger operators

Pavel Exner (Doppler Institute for Mathematical Physics and Applied Mathematics, Prague, Czech Republic)

The aim of this talk is to discuss several classes of Schrödinger operators with potentials that are below unbounded but their negative part is localized in narrow channels. A prototype of such a behavior can be found in Smilansky-Solomyak model devised to illustrate that an an irreversible behavior is possible even if the heat bath to which the systems is coupled has a finite number of degrees of freedom. We review its properties and analyze a regular version of this model, as well as another system in which x^py^p potential is amended by a negative radially symmetric term. All of them have the common property that they exhibit an abrupt parameter-dependent spectral transition: if the coupling constant exceeds a critical value the spectrum changes from a below bounded, partly or fully discrete, to the continuous one covering the whole real axis. We also discuss resonance effects in such models. The results come from a common work with Diana Barseghyan, Andrii Khrabustovskyi, Vladimir Lotoreichik and Miloš Tater.

Digital Signal Processing and Software-Defined Radios in Remote Attacks on GPS

Tomáš Rosa (Raiffeisenbank, a.s., Prague, Czech Republic)

The possibility of position, velocity, and also time forging for the civil GPS service is a well-known implication of deliberately missing cryptographic protections of the L1 C/A satellite signal. Practical feasibility was already demonstrated several times, so is there anything new and interesting? It is in the massive rise of software-defined radio phenomenon that will soon allow even unskilled hackers to download the attack code from the internet and let it run. It is also interesting to see the mathematics behind the digital signal processing that enables software-defined radios to exist that in turn have such a strong effect on the risk associated with trustingly relaying on the “trustworthy” GPS service.

Copositive Optimization in Infinite Dimension

Claudia Adams (Trier University, Trier, Germany)

Many combinatorial optimization problems can be formulated as conic convex optimization problems (e.g. stable set, maximum clique, maximum cut). Especially NP-hard problems can be written as copositive programs. In this case the hardness is moved totally into the copositivity constraint. We will show how to lift this theory to infinite dimension and we study operators in Hilbert spaces instead of matrices. For that purpose we develop a new theory of semidefinite and copositive optimization in infinite dimensional spaces. This new theory will use tools from functional analysis, but the restriction to finite dimensions provides the usual duality theory. In this context we discuss some properties which are equivalent to the ones in finite dimension and we also point out differences. We will show some special cases for which the theory can be formulated very well and some cases for which it is not easy. Understanding these cases and special properties is essential for developing solution approaches for problems of that kind. We will discuss an essential and popular norm in functional analysis, the symmetric projective norm, and its relevant properties. Furthermore we will explain its importance for our duality theory.

Multilevel optimal control of differential-algebraic systems

Daniel Bankmann (Technische Universität Berlin, Berlin, Germany)

Optimal control tasks arise in a variety of applications from, e.g., mechanical or electrical engineering, where one wants to minimize a certain cost functional with respect to some input function and the resulting state trajectory. Usually, the systems describing the dynamical behavior of these applications are governed by ordinary differential equation.However, the dynamics of such a system may be restricted to a manifold, and thus, one has to impose additional algebraic constraints which altogether constitute a so-called differential-algebraic system. Furthermore, in certain applications, e.g. humanoid locomotion of robots or simulation of gas flows in gas networks, the cost functional and the system descriptions may depend on parameters. This introduces a second level of optimization. In this talk I want to give a brief overview of multilevel optimal control problems and their numerical treatment. We point out difficulties that arise in this setting and present first approaches to deal with these problems.

MIP and Heuristics for Multiple Earth-Observing Satellites Scheduling Problem

Xiaoyu Chen (Heidelberg University, Heidelberg, Germany)

Earth observing satellites play a significant role in resource exploration, disaster alert and environmental damage analysis. We address a problem of multiple satellites scheduling with limited observing ability, which is a highly combinatorial problem due to the large search space for potential solutions. We decompose the problem into preprocessing and scheduling. By preprocessing it, we cope with some constraints, so that the input of the problem is only the available resources, the requested missions and the eligibility of resources for missions. By analyzing the distribution features of the visible time windows of missions and the contention degree of the available time interval on each resource, we construct a more exact mixed integer programming (MIP) optimization model for the satellites scheduling problem and solve it with Gurobi. We design several different kinds of instances to test the efficiency and applicability of the model. In comparison with some heuristic methods (including Greedy Techniques, and Evolutionary Algorithm), the results verify the correctness and efficiency of this scheduling model, indicating that the constructed algorithms are feasible.

Parametrized Sylvester Equations in Model Order Reduction

Manuela Hund (Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany)

Various mathematical and physical processes can be modeled as linear time-invariant (LTI) input-output systems. Since these systems often have a huge number of degrees of freedom, numerical simulations might be too expensive or even impossible caused by the computational time and memory requirements. Nevertheless, these LTI systems can be solved fast and sufficiently accurate if they are reduced to LTI systems of much smaller order, such that structural properties are preserved and the error between these systems or system outputs is small in a suitable norm. There are several model order reduction (MOR) techniques to reduce the order of a given LTI system. The basic idea of linear MOR is to project the given matrices of the system onto a much lower dimensional subspace, that computes the dynamics in the state space sufficiently well. In my talk I will present a projection method, that samples the time-dependent dynamics by orthogonal polynomials. The projection matrix is directly obtained from a sparse-dense Sylvester equation, which is a system of equations resulting in a solution matrix instead of a solution vector. Here, sparse-dense means that the matrices have a special structure, i.e. matrices multiplied from the left to the solution matrix are large and sparse and matrices multiplied from the right are small and dense. I will furthermore show two possibilities to obtain a parametrized Sylvester equation. On the one hand, we can parametrize the small and dense matrices containing information about the orthogonal polynomials. It is known, that the above mentioned time-domain MOR is related to another MOR method, moment matching. The goal of the latter procedure is to match the moments of the transfer function describing the relation of the input and the output of the original system. Therefor so-called expansion points are needed. Due to the equivalence it is known, that these expansion points are given by the spectrum of the small and dense matrices. Thus to obtain a broader spectrum, we can use parametrized families of Jacobi polynomials, such that the Sylvester equation gets parametrized in the small matrices. On the other hand, considering a system with parameter-dependent matrices, we are seeking for a well-approximating reduced system. A good indicator for this is measuring the error between their transfer functions in the H2 norm, which is an important system norm describing the influence of the inputs on the outputs. In the non-parametric case it is known, that the H2-optimality can be guaranteed by solving the Wilson conditions, that are given by Sylvester equations. Our final goal is to solve this H2-optimal parametric MOR problem via a fixed point iteration on the Wilson conditions along the lines of the two sided iterative approximation (TSIA) algorithm. Considering non-parametric systems, where the input and output are given by vectors instead of matrices, it is known, that the TSIA algorithm computes the same subspace resulting in the same projection matrix as the iterative rational Krylov algorithm (IRKA). The latter one can be seen as a generalization of moment matching, since each iteration of this algorithm is moment matching with expansion points, that are adapted on-the-fly resulting in locally optimally placed expansion points for the system in the sense of H2 optimal approximation. Thus our idea could in turn serve as an alternative H2-optimal MOR algorithm to the “parametric IRKA”, which is an extension of IRKA for parametric systems by interpolating the parameter space. In my talk, I will present first results towards this goal.

The Computation of the Discriminant of a Mass Action Network

Alexandru Iosif (Institut für Algebra und Geometrie, Universität Magdeburg, Magdeburg, Germany)

The steady states of a mass-action network are the non-negative real solutions to a parametric system of polynomial equations. It is a central problem to classify the number of isolated real solutions of such a system in certain linear subspaces. One approach to this problem is the computation of discriminants. We exemplify this method on the dual-site phosphorylation network.

Subset selection and regression problems

Dennis Kreber Trier University, Trier, Germany

Sparsity is an often desired property in regression and an extensively examined area of research. One of the most prominent methods to select relevant variables is the Lasso method. Sufficient conditions on the data under which Lasso generates a predictive, sparse solution are well known, however they are hard to verify. Thus, if those conditions are not satisfied, Lasso can exclude predictive variables or can fail at producing sparsity. To avoid these disadvantages, instead of a regularization term, a cardinalityconstrained subset selection formulation is used to limit the number of non-zero regression coefficients. The resulting problem is NP-hard and can be solved via mixed integer quadratic programming. We present an equivalent mixed integer linear formulation for this problem and show properties of the subset selection, which can be useful to find a solution more efficiently.

Symmetric Factorization of Saddle-point Matrices in Nonlinear Optimization and Reusing Pivots

Jan Kuřátko (Institute of Computer Science Academy of Sciences of the Czech Republic, Prague, Czech Republic)

Iterative methods for nonlinear optimization usually solve a sequence of linear systems. In this talk we will address the application of direct methods in solving linear systems where the matrix is symmetric and indefinite. Moreover, we assume that the matrices from that sequence of linear systems are related such that the structure of blocks and bands of nonzero elements remains the same. We solve the linear system by the symmetric indefinite factorization that is by Bunch-Parlett or Bunch-Kaufman methods. We will describe how to use the knowledge of the pattern of 1x1 and 2x2 pivots from one iteration in the next iteration of the optimization method. We will describe our strategy for monitoring the pivots and the stability of the factorization. According to our strategy we either skip searching for pivots or update the permutation matrix if needed. In addition, we will present our method that adaptively switches from the signed Cholesky factorization to Bunch-Parlett or Bunch-Kaufman. We will show on examples that this monitoring strategy reduces the time spent on searching the matrix for pivots.

Fast Solution of the Poisson-Boltzman Equation by the Reduced Basis Method and Range-Separated tensor format

Cleophas Kweyu (Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany)

The Poisson-Boltzmann equation (PBE) is a nonlinear elliptic parametrized partial differential equation that arises in biomolecular modeling and is a fundamental tool for structural biology. It is used to calculate electrostatic potentials around an ensemble of fixed charges immersed in an ionic solution. Efficient numerical computation of the PBE yields a high number of degrees of freedom in the resultant algebraic system of equations, ranging from several hundred thousands to millions. Coupled with the fact that in most cases the PBE requires to be solved multiple times for a large number of system configurations, this poses great computational challenges to conventional numerical techniques. To accelerate such computations, we here present the new range-separated tensor format for purposes of modifying the PBE in order to eliminate the terms related to singularities and also to obtain affine parametric dependence in the resultant algebraic system. Then we apply the reduced basis method (RBM) which further reduces the computational complexity by constructing a reduced order model of typically low dimension. The end results are reduced storage space and improved computational speed-up which enable the PBE simulations in a many-query context.

End to End Learning for DeepDriving with leveraging available scene segmentation side tasks to improve performance under a privileged learning paradigm and Robust Exponential Stability of Periodic Solutions for Static Recurrent Neural Networks with Delays

Shanzai Lee (The Western World Laboratory, Shenzen, China)

In this paper we reference to other scientists using Deep Q-Networks as the refinement step in Inverse Reinforcement Learning approaches. This enabled us to extract the rewards in scenarios with large state spaces such as driving, given expert demonstrations. The aim of this work was to extend the general approach to IRL. Exploring more advanced methods like Maximum Entropy IRL and the support for nonlinear reward functions is currently under investigation. We also give a proof of the mathematical aspects of the theory used in this paper. The static recursive neural network with Markovian modulation and the time-delay static recurrent neural network model considering both random perturbation and Markovian switching are studied. The linear matrix inequality, the finite state space Markov chain property and the Lyapunov-krasovskii function , The judgment condition of the global exponential stability of the system is obtained. Firstly, the global exponential stability problem of quasi - static neural neural network with time - delay and recursive neural network is studied by using the generalized Halanay inequality. Then the stability of the Markovian response sporadic static recurrent neural network is studied by combining the properties of Markov chain.Our paper draws on a novel FCN-LSTM architecture, which can be learned from large-scale crowd-sourced vehicle action data, and leverages available scene segmentation side tasks to improve performance under a privileged learning paradigm.

On Optimization of Stabilized Methods in FEM

Petr Lukáš (Charles University, Prague, Czech Republic)

In stabilized methods in FEM we typically use h-adaptivity or p-adaptivity. We will introduce a new approach to optimization. The optimization procedure is based on minimizing an error functional which we call error indicator. Numerical results will be provided.

The Separation Problem for 1-Wheel Inequalities and Extended Formulations

Bernd Perscheid (Trier University, Trier, Germany)

Finding a maximum stable set in a graph is NP-hard. Therefore, it is out of reach to describe the convex hull of incidence vectors by a polynomial system of inequalities. The cycle inequalities are an exponential class of valid stable set inequalities. Yannakakis (1991) shows how the separation problem for cycles can be solved with an extended formulation. We focus on solving the 1-wheel separation problem for stable sets in polynomial time. Our efficient and compact extended formulation can be used to avoid the application of shortest path algorithms. The construction relies on satisfying sufficient conditions for a given vector x in product graphs. These conditions are implicitly represented by adding polynomially many inequalities.

Surface Face Graphs and Their Tightness

Qays Shakir (National University of Ireland, Galway, Ireland)

Geometric rigidity theory is a tool which is designed to decide whether a framework (typically bar and joint) is rigid or flexible. Geometric and combinatoric mathematical aspects are used to build such theory. Combinatorially, Lamans theorem gives a complete answer for the rigidity status of a framework in two dimensions using (2,3)-tightness. In three dimensions, if a framework is minimally 3-rigid then its abstract graph is (3,6)-tight while the converse is not true in general; the double banana graph is a typical counterexample. Such observation motivated us to study (3,6)-tightness via various surfaces . The main theorem which is proved in this project is: Theorem: Let G be a Σ-face graph. If G has at least one triangle then G is (3,6)- tight if and only if every proper ∂-curve (c, Uc) in G satisfies the girth inequality.

Multi-Leader-Follower Games

Anna Thünen (RWTH Aachen University, Aachen, Germany)

The multi-leader-follower game is a particular subset of classical game theory. These models serve as an analytical tool to study the strategic behavior of individuals on a noncooperative manner. In particular, the individuals (players) are divided into two groups, namely the leaders and the followers, according to their position in the game. Mathematically, this leads optimization problems with optimization problems as constraints. Most recently, such type of models gains an increasing interest among mathematicians as well as scientists of other fields such as operations research, robotics and computer sciences. However, compared to the knowledge of other classical game models so far only very little is known concerning existence and uniqueness theory as well as suitable numerical solution methods. In this talk, we give an introduction to multi-leader-follower games where we formulate them as equilibrium problems with equilibrium constraints (EPEC). Furthermore, we illustrate challenges and present early results.

List of Participants Conference poster Programme Book of abstracts