TY - JOUR
AB - We show how to learn discrete field theories from observational data of fields on a space-time lattice. For this, we train a neural network model of a discrete Lagrangian density such that the discrete Euler--Lagrange equations are consistent with the given training data. We, thus, obtain a structure-preserving machine learning architecture. Lagrangian densities are not uniquely defined by the solutions of a field theory. We introduce a technique to derive regularisers for the training process which optimise numerical regularity of the discrete field theory. Minimisation of the regularisers guarantees that close to the training data the discrete field theory behaves robust and efficient when used in numerical simulations. Further, we show how to identify structurally simple solutions of the underlying continuous field theory such as travelling waves. This is possible even when travelling waves are not present in the training data. This is compared to data-driven model order reduction based approaches, which struggle to identify suitable latent spaces containing structurally simple solutions when these are not present in the training data. Ideas are demonstrated on examples based on the wave equation and the Schrödinger equation.
AU - Offen, Christian
AU - Ober-Blöbaum, Sina
ID - 46469
IS - 1
JF - Chaos
SN - 1054-1500
TI - Learning of discrete models of variational PDEs from data
VL - 34
ER -
TY - JOUR
AB - AbstractApproximation of subdifferentials is one of the main tasks when computing descent directions for nonsmooth optimization problems. In this article, we propose a bisection method for weakly lower semismooth functions which is able to compute new subgradients that improve a given approximation in case a direction with insufficient descent was computed. Combined with a recently proposed deterministic gradient sampling approach, this yields a deterministic and provably convergent way to approximate subdifferentials for computing descent directions.
AU - Gebken, Bennet
ID - 51208
JF - Computational Optimization and Applications
KW - Applied Mathematics
KW - Computational Mathematics
KW - Control and Optimization
SN - 0926-6003
TI - A note on the convergence of deterministic gradient sampling in nonsmooth optimization
ER -
TY - JOUR
AB - We derive efficient algorithms to compute weakly Pareto optimal solutions for smooth, convex and unconstrained multiobjective optimization problems in general Hilbert spaces. To this end, we define a novel inertial gradient-like dynamical system in the multiobjective setting, which trajectories converge weakly to Pareto optimal solutions. Discretization of this system yields an inertial multiobjective algorithm which generates sequences that converge weakly to Pareto optimal solutions. We employ Nesterov acceleration to define an algorithm with an improved convergence rate compared to the plain multiobjective steepest descent method (Algorithm 1). A further improvement in terms of efficiency is achieved by avoiding the solution of a quadratic subproblem to compute a common step direction for all objective functions, which is usually required in first-order methods. Using a different discretization of our inertial gradient-like dynamical system, we obtain an accelerated multiobjective gradient method that does not require the solution of a subproblem in each step (Algorithm 2). While this algorithm does not converge in general, it yields good results on test problems while being faster than standard steepest descent.
AU - Sonntag, Konstantin
AU - Peitz, Sebastian
ID - 46019
JF - Journal of Optimization Theory and Applications
TI - Fast Multiobjective Gradient Methods with Nesterov Acceleration via Inertial Gradient-Like Systems
ER -
TY - GEN
AB - The efficient optimization method for locally Lipschitz continuous multiobjective optimization problems from [1] is extended from finite-dimensional problems to general Hilbert spaces. The method iteratively computes Pareto critical points, where in each iteration, an approximation of the subdifferential is computed in an efficient manner and then used to compute a common descent direction for all objective functions. To prove convergence, we present some new optimality results for nonsmooth multiobjective optimization problems in Hilbert spaces. Using these, we can show that every accumulation point of the sequence generated by our algorithm is Pareto critical under common assumptions. Computational efficiency for finding Pareto critical points is numerically demonstrated for multiobjective optimal control of an obstacle problem.
AU - Sonntag, Konstantin
AU - Gebken, Bennet
AU - Müller, Georg
AU - Peitz, Sebastian
AU - Volkwein, Stefan
ID - 51334
T2 - arXiv:2402.06376
TI - A Descent Method for Nonsmooth Multiobjective Optimization in Hilbert Spaces
ER -
TY - GEN
AB - We introduce the concept of a k-token signed graph and study some of its combinatorial and algebraic properties. We prove that two switching isomorphic signed graphs have switching isomorphic token graphs. Moreover, we show that the Laplacian spectrum of a balanced signed graph is contained in the Laplacian spectra of its k-token signed graph. Besides, we introduce and study the unbalance level of a signed graph, which is a new parameter that measures how far a signed graph is from being balanced. Moreover, we study the relation between the frustration index and the unbalance level of signed graphs and their token signed graphs.
AU - Dalfó, C.
AU - Fiol, M. A.
AU - Steffen, Eckhard
ID - 52342
T2 - arXiv:2403.02924
TI - On token signed graphs
ER -
TY - JOUR
AB - Heteroclinic structures organize global features of dynamical systems. We analyse whether heteroclinic structures can arise in network dynamics with higher-order interactions which describe the nonlinear interactions between three or more units. We find that while commonly analysed model equations such as network dynamics on undirected hypergraphs may be useful to describe local dynamics such as cluster synchronization, they give rise to obstructions that allow to design of heteroclinic structures in phase space. By contrast, directed hypergraphs break the homogeneity and lead to vector fields that support heteroclinic structures.
AU - Bick, Christian
AU - von der Gracht, Sören
ID - 52726
IS - 2
JF - Journal of Complex Networks
KW - Applied Mathematics
KW - Computational Mathematics
KW - Control and Optimization
KW - Management Science and Operations Research
KW - Computer Networks and Communications
SN - 2051-1329
TI - Heteroclinic dynamics in network dynamical systems with higher-order interactions
VL - 12
ER -
TY - JOUR
AB - For 0 ≤ t ≤ r let m(t, r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t, r) known, for instance m(3, 3) = m(4, r) = 1, and m(t, r) ≤ r − 2 for all t = 5,
and m(t, r) ≤ r − 3 if r is even. We prove that m(2l, r) ≤ 3l − 6 for every l ≥ 3 and r ≥ 2l.
AU - Ma, Yulai
AU - Mattiolo, Davide
AU - Steffen, Eckhard
AU - Wolf, Isaak Hieronymus
ID - 49905
JF - Combinatorica
KW - Computational Mathematics
KW - Discrete Mathematics and Combinatorics
SN - 0209-9683
TI - Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs
VL - 44
ER -
TY - JOUR
AB - As in almost every other branch of science, the major advances in data
science and machine learning have also resulted in significant improvements
regarding the modeling and simulation of nonlinear dynamical systems. It is
nowadays possible to make accurate medium to long-term predictions of highly
complex systems such as the weather, the dynamics within a nuclear fusion
reactor, of disease models or the stock market in a very efficient manner. In
many cases, predictive methods are advertised to ultimately be useful for
control, as the control of high-dimensional nonlinear systems is an engineering
grand challenge with huge potential in areas such as clean and efficient energy
production, or the development of advanced medical devices. However, the
question of how to use a predictive model for control is often left unanswered
due to the associated challenges, namely a significantly higher system
complexity, the requirement of much larger data sets and an increased and often
problem-specific modeling effort. To solve these issues, we present a universal
framework (which we call QuaSiModO:
Quantization-Simulation-Modeling-Optimization) to transform arbitrary
predictive models into control systems and use them for feedback control. The
advantages of our approach are a linear increase in data requirements with
respect to the control dimension, performance guarantees that rely exclusively
on the accuracy of the predictive model, and only little prior knowledge
requirements in control theory to solve complex control problems. In particular
the latter point is of key importance to enable a large number of researchers
and practitioners to exploit the ever increasing capabilities of predictive
models for control in a straight-forward and systematic fashion.
AU - Peitz, Sebastian
AU - Bieker, Katharina
ID - 21199
JF - Automatica
TI - On the Universal Transformation of Data-Driven Models to Control Systems
VL - 149
ER -
TY - JOUR
AB - Regularization is used in many different areas of optimization when solutions
are sought which not only minimize a given function, but also possess a certain
degree of regularity. Popular applications are image denoising, sparse
regression and machine learning. Since the choice of the regularization
parameter is crucial but often difficult, path-following methods are used to
approximate the entire regularization path, i.e., the set of all possible
solutions for all regularization parameters. Due to their nature, the
development of these methods requires structural results about the
regularization path. The goal of this article is to derive these results for
the case of a smooth objective function which is penalized by a piecewise
differentiable regularization term. We do this by treating regularization as a
multiobjective optimization problem. Our results suggest that even in this
general case, the regularization path is piecewise smooth. Moreover, our theory
allows for a classification of the nonsmooth features that occur in between
smooth parts. This is demonstrated in two applications, namely support-vector
machines and exact penalty methods.
AU - Gebken, Bennet
AU - Bieker, Katharina
AU - Peitz, Sebastian
ID - 27426
IS - 3
JF - Journal of Global Optimization
TI - On the structure of regularization paths for piecewise differentiable regularization terms
VL - 85
ER -
TY - GEN
AB - Extending the notion of maxcut, the study of the frustration index of signed graphs is one of the basic questions in the theory of signed graphs. Recently two of the authors initiated the study of critically frustrated signed graphs. That is a signed graph whose frustration index decreases with the removal of any edge. The main focus of this study is on critical signed graphs which are not edge-disjoint unions of critically frustrated signed graphs (namely non-decomposable signed graphs) and which are not built from other critically frustrated signed graphs by subdivision. We conjecture that for any given k there are only finitely many critically k-frustrated signed graphs of this kind.
Providing support for this conjecture we show that there are only two of such critically 3-frustrated signed graphs where there is no pair of edge-disjoint negative cycles. Similarly, we show that there are exactly ten critically 3-frustrated signed planar graphs that are neither decomposable nor subdivisions of other critically frustrated signed graphs. We present a method for building non-decomposable critically frustrated signed graphs based on two given such signed graphs. We also show that the condition of being non-decomposable is necessary for our conjecture.
AU - Cappello, Chiara
AU - Naserasr, Reza
AU - Steffen, Eckhard
AU - Wang, Zhouningxin
ID - 44501
T2 - arXiv:2304.10243
TI - Critically 3-frustrated signed graphs
ER -
TY - JOUR
AB - Ancestral reconstruction is a classic task in comparative genomics. Here, we study the genome median problem, a related computational problem which, given a set of three or more genomes, asks to find a new genome that minimizes the sum of pairwise distances between it and the given genomes. The distance stands for the amount of evolution observed at the genome level, for which we determine the minimum number of rearrangement operations necessary to transform one genome into the other. For almost all rearrangement operations the median problem is NP-hard, with the exception of the breakpoint median that can be constructed efficiently for multichromosomal circular and mixed genomes. In this work, we study the median problem under a restricted rearrangement measure called c4-distance, which is closely related to the breakpoint and the DCJ distance. We identify tight bounds and decomposers of the c4-median and develop algorithms for its construction, one exact ILP-based and three combinatorial heuristics. Subsequently, we perform experiments on simulated data sets. Our results suggest that the c4-distance is useful for the study the genome median problem, from theoretical and practical perspectives.
AU - Silva, Helmuth O.M.
AU - Rubert, Diego P.
AU - Araujo, Eloi
AU - Steffen, Eckhard
AU - Doerr, Daniel
AU - Martinez, Fábio V.
ID - 44857
IS - 3
JF - RAIRO - Operations Research
KW - Management Science and Operations Research
KW - Computer Science Applications
KW - Theoretical Computer Science
SN - 0399-0559
TI - Algorithms for the genome median under a restricted measure of rearrangement
VL - 57
ER -
TY - GEN
AU - Ma, Yulai
AU - Mattiolo, Davide
AU - Steffen, Eckhard
AU - Wolf, Isaak Hieronymus
ID - 44859
T2 - arXiv:2305.08619
TI - Sets of r-graphs that color all r-graphs
ER -
TY - GEN
AB - We present a novel method for high-order phase reduction in networks of
weakly coupled oscillators and, more generally, perturbations of reducible
normally hyperbolic (quasi-)periodic tori. Our method works by computing an
asymptotic expansion for an embedding of the perturbed invariant torus, as well
as for the reduced phase dynamics in local coordinates. Both can be determined
to arbitrary degrees of accuracy, and we show that the phase dynamics may
directly be obtained in normal form. We apply the method to predict remote
synchronisation in a chain of coupled Stuart-Landau oscillators.
AU - von der Gracht, Sören
AU - Nijholt, Eddie
AU - Rink, Bob
ID - 45498
T2 - arXiv:2306.03320
TI - A parametrisation method for high-order phase reduction in coupled oscillator networks
ER -
TY - JOUR
AU - Ma, Yulai
AU - Mattiolo, Davide
AU - Steffen, Eckhard
AU - Wolf, Isaak Hieronymus
ID - 46256
IS - 3
JF - SIAM Journal on Discrete Mathematics
KW - General Mathematics
SN - 0895-4801
TI - Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
VL - 37
ER -
TY - CONF
AB - The article shows how to learn models of dynamical systems from data which are governed by an unknown variational PDE. Rather than employing reduction techniques, we learn a discrete field theory governed by a discrete Lagrangian density $L_d$ that is modelled as a neural network. Careful regularisation of the loss function for training $L_d$ is necessary to obtain a field theory that is suitable for numerical computations: we derive a regularisation term which optimises the solvability of the discrete Euler--Lagrange equations. Secondly, we develop a method to find solutions to machine learned discrete field theories which constitute travelling waves of the underlying continuous PDE.
AU - Offen, Christian
AU - Ober-Blöbaum, Sina
ED - Nielsen, F
ED - Barbaresco, F
ID - 42163
KW - System identification
KW - discrete Lagrangians
KW - travelling waves
T2 - Geometric Science of Information
TI - Learning discrete Lagrangians for variational PDEs from data and detection of travelling waves
VL - 14071
ER -
TY - JOUR
AB - The principle of least action is one of the most fundamental physical principle. It says that among all possible motions connecting two points in a phase space, the system will exhibit those motions which extremise an action functional. Many qualitative features of dynamical systems, such as the presence of conservation laws and energy balance equations, are related to the existence of an action functional. Incorporating variational structure into learning algorithms for dynamical systems is, therefore, crucial in order to make sure that the learned model shares important features with the exact physical system. In this paper we show how to incorporate variational principles into trajectory predictions of learned dynamical systems. The novelty of this work is that (1) our technique relies only on discrete position data of observed trajectories. Velocities or conjugate momenta do not need to be observed or approximated and no prior knowledge about the form of the variational principle is assumed. Instead, they are recovered using backward error analysis. (2) Moreover, our technique compensates discretisation errors when trajectories are computed from the learned system. This is important when moderate to large step-sizes are used and high accuracy is required. For this,
we introduce and rigorously analyse the concept of inverse modified Lagrangians by developing an inverse version of variational backward error analysis. (3) Finally, we introduce a method to perform system identification from position observations only, based on variational backward error analysis.
AU - Ober-Blöbaum, Sina
AU - Offen, Christian
ID - 29240
JF - Journal of Computational and Applied Mathematics
KW - Lagrangian learning
KW - variational backward error analysis
KW - modified Lagrangian
KW - variational integrators
KW - physics informed learning
SN - 0377-0427
TI - Variational Learning of Euler–Lagrange Dynamics from Data
VL - 421
ER -
TY - JOUR
AB - The numerical solution of an ordinary differential equation can be interpreted as the exact solution of a nearby modified equation. Investigating the behaviour of numerical solutions by analysing the modified equation is known as backward error analysis. If the original and modified equation share structural properties, then the exact and approximate solution share geometric features such as the existence of conserved quantities. Conjugate symplectic methods preserve a modified symplectic form and a modified Hamiltonian when applied to a Hamiltonian system. We show how a blended version of variational and symplectic techniques can be used to compute modified symplectic and Hamiltonian structures. In contrast to other approaches, our backward error analysis method does not rely on an ansatz but computes the structures systematically, provided that a variational formulation of the method is known. The technique is illustrated on the example of symmetric linear multistep methods with matrix coefficients.
AU - McLachlan, Robert
AU - Offen, Christian
ID - 29236
IS - 1
JF - Journal of Geometric Mechanics
KW - variational integrators
KW - backward error analysis
KW - Euler--Lagrange equations
KW - multistep methods
KW - conjugate symplectic methods
TI - Backward error analysis for conjugate symplectic methods
VL - 15
ER -
TY - JOUR
AB - Recently, Hamiltonian neural networks (HNN) have been introduced to incorporate prior physical knowledge when
learning the dynamical equations of Hamiltonian systems. Hereby, the symplectic system structure is preserved despite
the data-driven modeling approach. However, preserving symmetries requires additional attention. In this research, we
enhance the HNN with a Lie algebra framework to detect and embed symmetries in the neural network. This approach
allows to simultaneously learn the symmetry group action and the total energy of the system. As illustrating examples,
a pendulum on a cart and a two-body problem from astrodynamics are considered.
AU - Dierkes, Eva
AU - Offen, Christian
AU - Ober-Blöbaum, Sina
AU - Flaßkamp, Kathrin
ID - 37654
IS - 6
JF - Chaos
SN - 1054-1500
TI - Hamiltonian Neural Networks with Automatic Symmetry Detection
VL - 33
ER -
TY - JOUR
AB - The Koopman operator has become an essential tool for data-driven approximation of dynamical (control) systems in recent years, e.g., via extended dynamic mode decomposition. Despite its popularity, convergence results and, in particular, error bounds are still quite scarce. In this paper, we derive probabilistic bounds for the approximation error and the prediction error depending on the number of training data points; for both ordinary and stochastic differential equations. Moreover, we extend our analysis to nonlinear control-affine systems using either ergodic trajectories or i.i.d.
samples. Here, we exploit the linearity of the Koopman generator to obtain a bilinear system and, thus, circumvent the curse of dimensionality since we do not autonomize the system by augmenting the state by the control inputs. To the
best of our knowledge, this is the first finite-data error analysis in the stochastic and/or control setting. Finally, we demonstrate the effectiveness of the proposed approach by comparing it with state-of-the-art techniques showing its superiority whenever state and control are coupled.
AU - Nüske, Feliks
AU - Peitz, Sebastian
AU - Philipp, Friedrich
AU - Schaller, Manuel
AU - Worthmann, Karl
ID - 23428
JF - Journal of Nonlinear Science
TI - Finite-data error bounds for Koopman-based prediction and control
VL - 33
ER -
TY - JOUR
AB - Many problems in science and engineering require an efficient numerical approximation of integrals or solutions to differential equations. For systems with rapidly changing dynamics, an equidistant discretization is often inadvisable as it results in prohibitively large errors or computational effort. To this end, adaptive schemes, such as solvers based on Runge–Kutta pairs, have been developed which adapt the step size based on local error estimations at each step. While the classical schemes apply very generally and are highly efficient on regular systems, they can behave suboptimally when an inefficient step rejection mechanism is triggered by structurally complex systems such as chaotic systems. To overcome these issues, we propose a method to tailor numerical schemes to the problem class at hand. This is achieved by combining simple, classical quadrature rules or ODE solvers with data-driven time-stepping controllers. Compared with learning solution operators to ODEs directly, it generalizes better to unseen initial data as our approach employs classical numerical schemes as base methods. At the same time it can make use of identified structures of a problem class and, therefore, outperforms state-of-the-art adaptive schemes. Several examples demonstrate superior efficiency. Source code is available at https://github.com/lueckem/quadrature-ML.
AU - Dellnitz, Michael
AU - Hüllermeier, Eyke
AU - Lücke, Marvin
AU - Ober-Blöbaum, Sina
AU - Offen, Christian
AU - Peitz, Sebastian
AU - Pfannschmidt, Karlson
ID - 21600
IS - 2
JF - SIAM Journal on Scientific Computing
TI - Efficient time stepping for numerical integration using reinforcement learning
VL - 45
ER -