The 10 most recently published documents
We present domain decomposition techniques for efficient and scalable simulation and optimization of partial differential equations on network domains. Motivated by transient gas network applications, the state-of-the-art of space-and-time decompositions for systems derived from Euler's equations are presented. Moreover, combinatorial aspects of switching valves are addressed in a decomposition framework for mixed-integer and ODE-constrained problems and a convergence analysis is presented. Motivated by stochastic approximation, we also propose and explore randomized decomposition approaches. Some of these advanced solution strategies can be combined and regarded as variants of certain penalty alternating direction methods. We present the potential applications of these techniques by summarizing numerical results from the literature for transient GasLib instances modeling a realistic gas transport network.
We derive an adjoint gradient representation for the objective functional of an optimal control problem of the unique entropy solution to the Generalized Riemann Problem (GRP) for strictly hyperbolic systems of conservation or balance laws.
The GRP is an initial value problem where the initial state is piecewise C^1 with exactly one discontinuity. In a recent work, differentiability properties of the solution operator of the GRP were derived. In particular, the differentiability of a class of tracking-type functionals was shown. We build on these results to derive an adjoint gradient representation for such functionals.
The adjoint problem is a system of linear transport equations with a discontinuous coefficient and discontinuous terminal state. We prove the existence and uniqueness of a piecewise Lipschitz continuous solution to the adjoint problem which satisfies suitable interior boundary conditions along all shock curves. The adjoint state generally contains infinitely many discontinuities but its total variation remains uniformly bounded in time.
The notion of dissipative dynamical systems provides a formal description of processes that cannot generate energy internally. For these systems, changes in energy can only occur due to an external energy supply or dissipation effects. Unfortunately, dissipative properties tend to deteriorate in numerical computations, especially in nonlinear systems. Discrete gradient methods can help mitigate this problem. In this paper, we present a class of structure-preserving time discretization schemes based on discrete gradients for a special class of systems that are dissipative with respect to a quadratic supply rate.
We investigate discretization strategies for a recently introduced class of energy-based models. The model class encompasses classical port-Hamiltonian systems, generalized gradient flows, and certain systems with algebraic constraints. Our framework combines existing ideas from the literature and systematically addresses temporal discretization, spatial discretization, and model order reduction, ensuring that all resulting schemes are dissipation-preserving in the sense of a discrete dissipation inequality. For this, we use a Petrov-Galerkin ansatz together with appropriate projections. Numerical results for a nonlinear circuit model and the Cahn-Hilliard equation illustrate the effectiveness of the approach.
Dynamical systems consist of ordinary and partial differential equations and are among the most prominent approaches to model physical processes. They describe the evolution of the system in terms of the current system state and external control inputs. To improve model accuracy, it can be beneficial to explicitly include properties such as energy conservation or energy dissipation, which are usually present in the real-world phenomena, in the mathematical problem description. Ideally, these properties should be kept in mind whenever one interacts with the model. The focus of this thesis is on two kinds of interactions: the discretization of such models, and their control. Discretization techniques are necessary whenever the system evolution is to be approximated using computational methods. Similarly fundamental is the numerical realization of control inputs that lead to desired outcomes. Both aspects require special attention to retain an energy-based perspective. For this, the first step is usually to encode the energy properties in the algebraic description of the model. This description must strike a balance between general applicability and its corresponding benefits. The next step is to leverage the algebraic description in further analysis. While the field is well-developed for linear systems, the nonlinear case often poses additional difficulties. First, there seems to be no clear consensus about what model class to use to describe nonlinear physical phenomena. Second, many discretization methods that preserve the energy-based viewpoint in the linear case are not trivial to generalize to nonlinear systems. Third, studying the behavior of energy-optimal controls and finding control laws that can be realized via energy-based models is usually more difficult. In this thesis, these points are addressed. We give an overview of energy-based model classes used for nonlinear phenomena in both finite and infinite dimensions and investigate their relationship. Moreover, using a modified Petrov--Galerkin method and discrete gradients, we present multiple structure-preserving discretization schemes. Furthermore, we show that similar to the linear case, energy-optimal controls steer the associated trajectories to the submanifold of the state space where no dissipation is present. Finally, we combine an optimal feedback law characterized by the Hamilton--Jacobi--Bellman equation with output feedback to state an energy-based feedback controller. Our theoretical results are illustrated using numerical experiments.
The 121 real schemes, i.e., ambient isotopy classes, of smooth real plane algebraic curves of degree seven were classified by Viro (1984). By constructing one patchwork of the dilated triangle 7⋅Δ2 for each real scheme, we provide an explicit method for constructing polynomials realizing each real scheme. In particular, every real scheme of degree seven can be realized as a T-curve; this settles a question raised by Itenberg and Viro (1996).
A T-curve of degree d is given by a regular unimodular triangulation of d⋅Δ2 together with a sign distribution on its lattice points. By Viro's Patchworking Theorem, this determines the ambient isotopy type (a.k.a. real scheme) of a smooth real plane projective algebraic curve of the same degree. We present a near-quadratic time algorithm for extracting that isotopy type from the triangulation and the signs. Through a GPU-accelerated implementation, this allows one to compute billions of real schemes per second, enabling exhaustive enumeration at scale. This algorithm was essential for our recent construction of all 121 real schemes of degree seven by T-curves.
Solving mixed-integer nonlinear programs (MINLPs) typically relies on constructing relaxations that are easier to tackle than the original problem. Recently, global parabolic (PARA) relaxations were introduced, featuring separable quadratic functions – paraboloids – as global under- or overestimators of general nonlinear constraint functions. So far, the paraboloids are all computed at once by solving a mixed-integer linear program (MIP). For small tolerances or wide function domains, the corresponding MIP grows in size and is eventually intractable, preventing a meaningful comparison with established relaxation techniques.
We therefore propose a novel iterative method to compute PARA approximations that succeeds on all tolerance-domain combinations where the original one has failed. The computational study is preceded by a thorough theoretical explanation and analysis. Finally, the improved method enables a computational comparison with piecewise linear (PWL) relaxations in terms of runtime on general MINLP instances.
The results show that the modern solver SCIP can solve PWL relaxations faster when the olerance is high, shifting strongly in favor of PARA for tighter tolerances. We attribute the effect to the difference in the corresponding problem size: PWL relaxations introduce binary variables to identify the active linear piece and their number grows with decreasing tolerance. PARA, on
the other hand, does not require additional variables such that the dimension is maintained. For problems with at least one (co)sine constraint, the effect significantly amplifies. Thereby, for medium tolerances, PARA relaxations outperform SCIP stand-alone. Applied problems like alternating current optimal power flow (AC-OPF) feature such constraint types, leaving PARA a viable relaxation strategy.
We develop efficient algorithms for a fundamental network design problem arising in potential-based flow models, which are central to many energy transport networks (e.g., hydrogen and electricity). In contrast to classical network flow problems, the nonlinearities inherent in potential-based networks introduce significant new challenges. We address these challenges through intricate reductions to classical combinatorial optimization problems, such as (constrained) shortest path problems, enabling the application of well-established algorithmic techniques to compute exact and approximate solutions efficiently. Finally, we complement these algorithmic results with matching complexity results concerning the hardness and non-approximability of the considered problem variants.
We present two novel six-colorings of the Euclidean plane that avoid monochromatic pairs of points at unit distance in five colors and monochromatic pairs at another specified distance $d$ in the sixth color. Such colorings have previously been known to exist for $0.41 < \sqrt{2} - 1 \le d \le 1 / \sqrt{5} < 0.45$. Our results significantly expand that range to $0.354 \le d \le 0.657$, the first improvement in 30 years. Notably, the constructions underlying this were derived by formalizing colorings suggested by a custom machine learning approach.
