TY - THES A1 - Kleinert, Thomas T1 - Algorithms for Mixed-Integer Bilevel Problems with Convex Followers N2 - Bilevel problems are optimization problems for which a subset of variables is constrained to be an optimal solution of another optimization problem. As such, bilevel problems are capable of modeling hierarchical decision processes. This is required by many real-world problems from a broad spectrum of applications such as energy markets, traffic planning, or critical infrastructure defense, to name only a few. However, the hierarchy of decisions makes bilevel optimization problems also very challenging to solve—both in theory and practice. This cumulative PhD thesis is concerned with computational bilevel optimization. In the first part, we summarize several solution approaches that we developed over the last years and highlight the significant computational progress that these methods provide. For linear bilevel problems, we review branch-and-bound methods, critically discuss their practical use, and propose valid inequalities to extend the methods to branch-and-cut approaches. Further, we demonstrate on a large test set that it is no longer necessary to use the well-known but error-prone big-M reformulation to solve linear bilevel problems. We also present a bilevel-specific heuristic that is based on a penalty alternating direction method. This heuristic is applicable to a broad class of bilevel problems, e.g., linear or mixed-integer quadratic bilevel problems. In a computational study, we show that the method computes optimal or close-to-optimal feasible points in a very short time and that it outperforms a state-of-the-art local method from the literature. Finally, we review global approaches for mixed-integer quadratic bilevel problems. In addition to a Benders-like decomposition, we present a multi-tree and a single-tree outer-approximation approach. A computational evaluation demonstrates that both variants outperform known benchmark algorithms. The second part of this thesis consists of reprints of our original articles and preprints. These articles contain all details and are referenced throughout the first part of the thesis. Y1 - 2021 ER - TY - JOUR A1 - Ruiz-Balet, Domenec A1 - Zuazua, Enrique T1 - Neural ODE Control for Classification, Approximation and Transport N2 - We analyze Neural Ordinary Differential Equations (NODEs) from a control theoretical perspective to address some of the main properties and paradigms of Deep Learning (DL), in particular, data classification and universal approximation. These objectives are tackled and achieved from the perspective of the simultaneous control of systems of NODEs. For instance, in the context of classification, each item to be classified corresponds to a different initial datum for the control problem of the NODE, to be classified, all of them by the same common control, to the location (a subdomain of the euclidean space) associated to each label. Our proofs are genuinely nonlinear and constructive, allowing us to estimate the complexity of the control strategies we develop. The nonlinear nature of the activation functions governing the dynamics of NODEs under consideration plays a key role in our proofs, since it allows deforming half of the phase space while the other half remains invariant, a property that classical models in mechanics do not fulfill. This very property allows to build elementary controls inducing specific dynamics and transformations whose concatenation, along with properly chosen hyperplanes, allows achieving our goals in finitely many steps. The nonlinearity of the dynamics is assumed to be Lipschitz. Therefore, our results apply also in the particular case of the ReLU activation function. We also present the counterparts in the context of the control of neural transport equations, establishing a link between optimal transport and deep neural networks. KW - data classification KW - Neural ODEs KW - Optimal Transport KW - simultaneous control KW - deep learning Y1 - 2021 ER - TY - INPR A1 - Egerer, Jonas A1 - Grimm, Veronika A1 - Grübel, Julia A1 - Zöttl, Gregor T1 - Long-run market equilibria in coupled energy sectors: A study of uniqueness N2 - We propose an equilibrium model for coupled markets of multiple energy sectors. The agents in our model are operators of sector-specific production and sector-coupling technologies, as well as price-sensitive consumers with varying demand. We analyze long-run investment in production capacity in each sector and investment in coupling capacity between sectors, as well as production decisions determined at repeated spot markets. We show that in our multi-sector model, multiplicity of equilibria may occur, even if all assumptions hold that would be sufficient for uniqueness in a single-sector model. We then contribute to the literature by deriving sufficient conditions for the uniqueness of short- and long-run market equilibrium in coupled markets of multiple energy sectors. We illustrate via simple examples that these conditions are indeed required to guarantee uniqueness in general. The uniqueness result is an important step to be able to incorporate the proposed market equilibrium problem in more complex computational multilevel equilibrium models, in which uniqueness of lower levels is a prerequisite for obtaining meaningful solutions. Our analysis also paves the way to understand and analyze more complex sector coupling models in the future. KW - Energy Markets KW - Sector Coupling KW - Regional Pricing KW - Uniqueness KW - Short- and Long-Run Market Equilibrium Y1 - 2021 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Manns, Julian A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Presolving Linear Bilevel Optimization Problems JF - EURO Journal on Computational Optimization N2 - Linear bilevel optimization problems are known to be strongly NP-hard and the computational techniques to solve these problems are often motivated by techniques from single-level mixed-integer optimization. Thus, during the last years and decades many branch-and-bound methods, cutting planes, or heuristics have been proposed. On the other hand, there is almost no literature on presolving linear bilevel problems although presolve is a very important ingredient in state-of-the-art mixed-integer optimization solvers. In this paper, we carry over standard presolve techniques from single-level optimization to bilevel problems and show that this needs to be done with great caution since a naive application of well-known techniques does often not lead to correctly presolved bilevel models. Our numerical study shows that presolve can also be very beneficial for bilevel problems but also highlights that these methods have a more heterogeneous effect on the solution process compared to what is known from single-level optimization. As a side result, our numerical experiments reveal that there is an urgent need for better and more heterogeneous test instance libraries to further propel the field of computational bilevel optimization. KW - Linear Bilevel Optimization KW - Presolve KW - Computational Analysis Y1 - 2021 U6 - https://doi.org/10.1016/j.ejco.2021.100020 IS - 9 ER - TY - JOUR A1 - Domschke, Pia A1 - Kolb, Oliver A1 - Lang, Jens T1 - Fast and Reliable Transient Simulation and Continuous Optimization of Large-Scale Gas Networks N2 - We are concerned with the simulation and optimization of large-scale gas pipeline systems in an error-controlled environment. The gas flow dynamics is locally approximated by sufficiently accurate physical models taken from a hierarchy of decreasing complexity and varying over time. Feasible work regions of compressor stations consisting of several turbo compressors are included by semiconvex approximations of aggregated characteristic fields. A discrete adjoint approach within a first-discretize-then-optimize strategy is proposed and a sequential quadratic programming with an active set strategy is applied to solve the nonlinear constrained optimization problems resulting from a validation of nominations. The method proposed here accelerates the computation of near-term forecasts of sudden changes in the gas management and allows for an economic control of intra-day gas flow schedules in large networks. Case studies for real gas pipeline systems show the remarkable performance of the new method. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s00186-021-00765-7 PB - Mathematical Methods of Operations Research ER - TY - JOUR A1 - Frenzel, David A1 - Lang, Jens T1 - A Third-Order Weighted Essentially Non-Oscillatory Scheme in Optimal Control Problems Governed by Nonlinear Hyperbolic Conservation Laws N2 - The weighted essentially non-oscillatory (WENO) methods are popular and effective spatial discretization methods for nonlinear hyperbolic partial differential equations. Although these methods are formally first-order accurate when a shock is present, they still have uniform high-order accuracy right up to the shock location. In this paper, we propose a novel third-order numerical method for solving optimal control problems subject to scalar nonlinear hyperbolic conservation laws. It is based on the first-disretize-then-optimize approach and combines a discrete adjoint WENO scheme of third order with the classical strong stability preserving three-stage third-order Runge-Kutta method SSPRK3. We analyze its approximation properties and apply it to optimal control problems of tracking-type with non-smooth target states. Comparisons to common first-order methods such as the Lax-Friedrichs and Engquist-Osher method show its great potential to achieve a higher accuracy along with good resolution around discontinuities. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s10589-021-00295-2 VL - Computational Optimization and Applications IS - 80 SP - 301 EP - 320 ER - TY - JOUR A1 - Lang, Jens A1 - Domschke, Pia A1 - Strauch, Elisa T1 - Adaptive Single- and Multilevel Stochastic Collocation Methods for Uncertain Gas Transport in Large-Scale Networks N2 - In this paper, we are concerned with the quantification of uncertainties that arise from intra-day oscillations in the demand for natural gas transported through large-scale networks. The short-term transient dynamics of the gas flow is modelled by a hierarchy of hyperbolic systems of balance laws based on the isentropic Euler equations. We extend a novel adaptive strategy for solving elliptic PDEs with random data, recently proposed and analysed by Lang, Scheichl, and Silvester [J. Comput. Phys., 419:109692, 2020], to uncertain gas transport problems. Sample-dependent adaptive meshes and a model refinement in the physical space is combined with adaptive anisotropic sparse Smolyak grids in the stochastic space. A single-level approach which balances the discretization errors of the physical and stochastic approximations and a multilevel approach which additionally minimizes the computational costs are considered. Two examples taken from a public gas library demonstrate the reliability of the error control of expectations calculated from random quantities of interest, and the further use of stochastic interpolants to, e.g., approximate probability density functions of minimum and maximum pressure values at the exits of the network. Y1 - 2021 VL - In: Mesh Generation and Adaptation, Cutting-Edge Techniques. R. Sevilla, S. Perotto, K. Morgan (eds.), SEMA-SIMAI Springer Series IS - Vol. 30 SP - 113 EP - 135 ER - TY - JOUR A1 - Gräßle, Carmen A1 - Hinze, Michael A1 - Lang, Jens A1 - Ullmann, Sebastian T1 - POD model order reduction with space-adapted snapshots for incompressible flows N2 - We consider model order reduction based on proper orthogonal decomposition (POD) for unsteady incompressible Navier-Stokes problems, assuming that the snapshots are given by spatially adapted finite element solutions. We propose two approaches of deriving stable POD-Galerkin reduced-order models for this context. In the first approach, the pressure term and the continuity equation are eliminated by imposing a weak incompressibility constraint with respect to a pressure reference space. In the second approach, we derive an inf-sup stable velocity-pressure reduced-order model by enriching the velocity reduced space with supremizers computed on a velocity reference space. For problems with inhomogeneous Dirichlet conditions, we show how suitable lifting functions can be obtained from standard adaptive finite element computations. We provide a numerical comparison of the considered methods for a regularized lid-driven cavity problem. Y1 - 2019 U6 - https://doi.org/doi:10.1007/s10444-019-09716-7 VL - Advances in Computational Mathematics IS - 45 SP - 2401 EP - 2428 ER - TY - JOUR A1 - Lang, Jens A1 - Schmitt, Bernhard A. T1 - Discrete Adjoint Implicit Peer Methods in Optimal Control N2 - It is well known that in the first-discretize-then-optimize approach in the control of ordinary differential equations the adjoint method may converge under additional order conditions only. For Peer two-step methods we derive such adjoint order conditions and pay special attention to the boundary steps. For $s$-stage methods, we prove convergence of order s for the state variables if the adjoint method satisfies the conditions for order s-1, at least. We remove some bottlenecks at the boundaries encountered in an earlier paper of the first author et al. [J. Comput. Appl. Math., 262:73--86, 2014] and discuss the construction of 3-stage methods for the order pair (3,2) in detail including some matrix background for the combined forward and adjoint order conditions. The impact of nodes having equal differences is highlighted. It turns out that the most attractive methods are related to BDF. Three 3-stage methods are constructed which show the expected orders in numerical tests. Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1016/j.cam.2022.114596 VL - Journal of Computational and Applied Mathematics IS - 416:114596 ER - TY - JOUR A1 - Lang, Jens A1 - Scheichl, Robert A1 - Silvester, David T1 - A Fully Adaptive Multilevel Stochastic Collocation Strategy for Solving Elliptic PDEs with Random Data N2 - We propose and analyse a fully adaptive strategy for solving elliptic PDEs with random data in this work. A hierarchical sequence of adaptive mesh refinements for the spatial approximation is combined with adaptive anisotropic sparse Smolyak grids in the stochastic space in such a way as to minimize the computational cost. The novel aspect of our strategy is that the hierarchy of spatial approximations is sample dependent so that the computational effort at each collocation point can be optimised individually. We outline a rigorous analysis for the convergence and computational complexity of the adaptive multilevel algorithm and we provide optimal choices for error tolerances at each level. Two numerical examples demonstrate the reliability of the error control and the significant decrease in the complexity that arises when compared to single level algorithms and multilevel algorithms that employ adaptivity solely in the spatial discretisation or in the collocation procedure. Y1 - 2021 U6 - https://doi.org/doi:10.1016/j.jcp.2020.109692 VL - Journal of Computational Physics IS - 419 ER - TY - INPR A1 - Heitsch, Holger A1 - Henrion, René A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - On Convex Lower-Level Black-Box Constraints in Bilevel Optimization with an Application to Gas Market Models with Chance Constraints N2 - Bilevel optimization is an increasingly important tool to model hierarchical decision making. However, the ability of modeling such settings makes bilevel problems hard to solve in theory and practice. In this paper, we add on the general difficulty of this class of problems by further incorporating convex black-box constraints in the lower level. For this setup, we develop a cutting-plane algorithm that computes approximate bilevel-feasible points. We apply this method to a bilevel model of the European gas market in which we use a joint chance constraint to model uncertain loads. Since the chance constraint is not available in closed form, this fits into the black-box setting studied before. For the applied model, we use further problem-specific insights to derive bounds on the objective value of the bilevel problem. By doing so, we are able to show that we solve the application problem to approximate global optimality. In our numerical case study we are thus able to evaluate the welfare sensitivity in dependence of the achieved safety level of uncertain load coverage. KW - Bilevel optimization KW - Black-box constraints KW - Chance constraints KW - Cutting planes KW - European gas market Y1 - 2021 ER - TY - INPR A1 - Spürkel, Kai A1 - Claus, Matthias T1 - Improving constants of strong convexity in linear stochastic programming N2 - We derive formulas for constants of strong convexity (CSCs) of risk functions encountered in two-stage stochastic programs with linear recourse. One of them yields a CSC as the optimal value of a certain QCQP, another one in terms of the thickness of the feasibility polytope of the dual problem associated to the recourse problem. CSCs appear in Hoelder-type estimates relating the distance of optimal solution sets of stochastic programs to a suitable distance of underlying probability distributions. KW - Strong Convexity KW - Stochastic Programming KW - Linear Recourse Y1 - 2021 ER - TY - JOUR A1 - Gugat, Martin T1 - On the turnpike property with interior decay for optimal control problems JF - Mathematics of Control, Signals, and Systems N2 - In this paper the turnpike phenomenon is studied for problems of optimal control where both pointwise-in-time state and control constraints can appear. We assume that in the objective function, a tracking term appears that is given as an integral over the time-interval [0, T] and measures the distance to a desired stationary state. In the optimal control problem, both the initial and the desired terminal state are prescribed. We assume that the system is exactly controllable in an abstract sense if the time horizon is long enough. We show that that the corresponding optimal control problems on the time intervals [0, T] give rise to a turnpike structure in the sense that for natural numbers n if T is su� ciently large, the contribution of the objective function from subintervals of [0, T] of the form [t - t/2^n, t + (T-t)/2^n] is of the order 1/min{t^n, (T-t)^n}. We also show that a similar result holds for epsilon-optimal solutions of the optimal control problems if epsilon > 0 is chosen suffciently small. At the end of the paper we present both systems that are governed by ordinary differential equations and systems governed by partial differential equations where the results can be applied. KW - Optimal control KW - Turnpike KW - Control Constraint KW - State constraint KW - Exact controllability Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s00498-021-00280-4 ER - TY - INPR A1 - Gugat, Martin A1 - Sokolowski, Jan T1 - On Problems of Dynamic Optimal Nodal control for Gas Networks N2 - We consider a dynamic ptimal control problem for gas pipeline systems. The flow is governed by a quasilinear hyperbolic model. Since in the operation of the gas networks regular solutions without shocks are desirable, we impose appropriate state and control constraint in order to guarantee that a classical solution is generated. Due to a W^{2;inf}-regularization term in the objective function, we can show the existence of an optimal control. Moreover, we give conditions that guarantee that the control becomes constant a the end of the control time interval if the weight of the regularization term is suffciently large. KW - optimal nodal control KW - gas network KW - turnpike property KW - quasilinear hyperbolic problem KW - dynamic control Y1 - 2021 ER - TY - JOUR A1 - Plein, Fränk A1 - Thürauf, Johannes A1 - Labbé, Martine A1 - Schmidt, Martin T1 - A Bilevel Optimization Approach to Decide the Feasibility of Bookings in the European Gas Market JF - Mathematical Methods of Operations Research N2 - The European gas market is organized as a so-called entry-exit system with the main goal to decouple transport and trading. To this end, gas traders and the transmission system operator (TSO) sign so-called booking contracts that grant capacity rights to traders to inject or withdraw gas at certain nodes up to this capacity. On a day-ahead basis, traders then nominate the actual amount of gas within the previously booked capacities. By signing a booking contract, the TSO guarantees that all nominations within the booking bounds can be transported through the network. This results in a highly challenging mathematical problem. Using potential-based flows to model stationary gas physics, feasible bookings on passive networks, i.e., networks without controllable elements, have been characterized in the recent literature. In this paper, we consider networks with linearly modeled active elements such as compressors or control valves. Since these active elements allow the TSO to control the gas flow, the single-level approaches for passive networks from the literature are no longer applicable. We thus present a bilevel model to decide the feasibility of bookings in networks with active elements. While this model is well-defined for general active networks, we focus on the class of networks for which active elements do not lie on cycles. This assumption allows us to reformulate the original bilevel model such that the lower-level problem is linear for every given upper-level decision. Consequently, we derive several single-level reformulations for this case. Besides the classic Karush-Kuhn-Tucker reformulation, we obtain three problem-specific optimal-value-function reformulations. The latter also lead to novel characterizations of feasible bookings in networks with active elements that do not lie on cycles. We compare the performance of our methods by a case study based on data from the GasLib. KW - Gas networks KW - Bilevel optimization KW - European entry-exit market KW - Bookings KW - Active elements Y1 - 2021 U6 - https://doi.org/10.1007/s00186-021-00752-y ER - TY - JOUR A1 - Sarac, Yesim A1 - Zuazua, Enrique T1 - Sidewise control of 1-d waves N2 - We analyze the sidewise controllability for the variable coefficients one-dimensional wave equation. The control is acting on one extreme of the string with the aim that the solution tracks a given path at the otherfree end. This sidewise control problem is also often referred to as nodal profile or tracking control. First, the problem is reformulated as a dual observability property for the corresponding adjoint system. Using sidewiseenergy propagation arguments the sidewise observability is shown to hold, ina sufficiently large time, in the class of BV-coefficients. We also present a number of open problems and perspectives for further research. KW - 1-d wave equations KW - BV-coefficients KW - nodal profile con-trol Y1 - 2021 ER - TY - JOUR A1 - Beck, Yasmine A1 - Schmidt, Martin T1 - A Robust Approach for Modeling Limited Observability in Bilevel Optimization JF - Operations Research Letters N2 - Many applications of bilevel optimization contain a leader facing a follower whose reaction deviates from the one expected by the leader due to some kind of bounded rationality. We consider bilinear bilevel problems with follower's response uncertainty due to limited observability regarding the leader's decision and exploit robust optimization to model the decision making of the follower. We show that the robust counterpart of the lower level allows to tackle the problem via the lower level's KKT conditions. KW - Bilevel optimization KW - Robust optimization KW - Bounded rationality KW - Limited observability KW - Reformulations Y1 - 2021 IS - 49(5) SP - 752 EP - 758 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Labbé, Martine A1 - Ljubić, Ivana A1 - Schmidt, Martin T1 - A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization JF - EURO Journal on Computational Optimization N2 - Bilevel optimization is a field of mathematical programming in which some variables are constrained to be the solution of another optimization problem. As a consequence, bilevel optimization is able to model hierarchical decision processes. This is appealing for modeling real-world problems, but it also makes the resulting optimization models hard to solve in theory and practice. The scientific interest in computational bilevel optimization increased a lot over the last decade and is still growing. Independent of whether the bilevel problem itself contains integer variables or not, many state-of-the-art solution approaches for bilevel optimization make use of techniques that originate from mixed-integer programming. These techniques include branch-and-bound methods, cutting planes and, thus, branch-and-cut approaches, or problem-specific decomposition methods. In this survey article, we review bilevel-tailored approaches that exploit these mixed-integer programming techniques to solve bilevel optimization problems. To this end, we first consider bilevel problems with convex or, in particular, linear lower-level problems. The discussed solution methods in this field stem from original works from the 1980's but, on the other hand, are still actively researched today. Second, we review modern algorithmic approaches to solve mixed-integer bilevel problems that contain integrality constraints in the lower level. Moreover, we also briefly discuss the area of mixed-integer nonlinear bilevel problems. Third, we devote some attention to more specific fields such as pricing or interdiction models that genuinely contain bilinear and thus nonconvex aspects. Finally, we sketch a list of open questions from the areas of algorithmic and computational bilevel optimization, which may lead to interesting future research that will further propel this fascinating and active field of research. KW - Bilevel optimization KW - Mixed-integer programming KW - Applications KW - Branch-and-bound KW - Branch-and-cut Y1 - 2021 ER - TY - INPR A1 - Giesselmann, Jan A1 - Egger, Herbert T1 - Stability and asymptotic analysis for instationary gas transport via relative energy estimates N2 - We consider the transport of gas in long pipes and pipeline networks for which the dynamics are dominated by friction at the pipe walls. The governing equations can be formulated as an abstract dissipative Hamiltonian system which allows us to derive perturbation bounds by means of relative energy estimates. As particular consequences, we obtain stability with respect to initial conditions and model parameters and quantitative estimates in the high friction limit. Our results are established in detail for the flow in a single pipe and through the energy-based modelling they naturally generalize also to pipe networks. KW - gas transport on networks KW - asymptotic limits KW - hyperbolic balance laws KW - relative energy estimates KW - singular perturbations Y1 - 2020 ER - TY - JOUR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems JF - SIAM Journal on Control and Optimization N2 - In this article, we extend the time-domain decomposition method described by Lagnese and Leugering (2003) to semilinear optimal control problems for hyperbolic balance laws with spatio-temporal varying coefficients. We provide the design of the iterative method applied to the global first-order optimality system, prove its convergence, and derive an a posteriori error estimate. The analysis is done entirely on the continuous level. A distinguishing feature of the method is that the decomposed optimality system can be interpreted as an optimality system of a local "virtual" optimal control problem. Thus, the iterative time-domain decomposition of the optimality system can be interpreted as an iterative parallel scheme for virtual optimal control problems on the subintervals. A typical example and further comments are given to show the range of potential applications. Moreover, we provide some numerical experiments to give a first interpretation of the role of the parameters involved in the iterative process. KW - Time-domain decomposition KW - Optimal control KW - Semilinear hyperbolic systems KW - Convergence KW - A posteriori error estimates Y1 - 2020 ER - TY - JOUR A1 - Esteve, Carlos A1 - Geshkovski, Borjan A1 - Pighin, Dario A1 - Zuazua, Enrique T1 - Turnpike in Lipschitz-nonlinear optimal control N2 - We present a new proof of the turnpike property for nonlinear optimal control problems, when the running target is a steady control-state pair of the underlying dynamics. Our strategy combines the construction of suboptimal quasi-turnpike trajectories via controllability, and a bootstrap argument, and does not rely on analyzing the optimality system or linearization techniques. This in turn allows us to address several optimal control problems for finite-dimensional, control-affine systems with globally Lipschitz (possibly nonsmooth) nonlinearities, without any smallness conditions on the initial data or the running target. These results are motivated by the large-layer regime of residual neural networks, commonly used in deep learning applications. We show that our methodology is applicable to controlled PDEs as well, such as the semilinear wave and heat equation with a globally Lipschitz nonlinearity, once again without any smallness assumptions. Y1 - ER - TY - JOUR A1 - Gontran, Lance A1 - Trélat, Emmanuel A1 - Zuazua, Enrique T1 - Shape turnpike for linear parabolic PDE models N2 - We introduce and study the turnpike property for time-varying shapes, within the viewpoint of optimal control. We focus here on second-order linear parabolic equations where the shape acts as a source term and we seek the optimal time-varying shape that minimizes a quadratic criterion. We first establish existence of optimal solutions under some appropriate sufficient conditions. We then provide necessary conditions for optimality in terms of adjoint equations and, using the concept of strict dissipativity, we prove that state and adjoint satisfy the measure-turnpike property, meaning that the extremal time-varying solution remains essentially close to the optimal solution of an associated static problem. We show that the optimal shape enjoys the exponential turnpike property in term of Hausdorff distance for a Mayer quadratic cost. We illustrate the turnpike phenomenon in optimal shape design with several numerical simulations. Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1016/j.sysconle.2020.104733 VL - 142 PB - Syst. Control. Lett. ER - TY - JOUR A1 - Biccari, Umberto A1 - Navarro-Quiles, Ana A1 - Zuazua, Enrique T1 - Stochastic optimization methods for the simultaneous control of parameter-dependent systems N2 - We address the application of stochastic optimization methods for the simultaneous control of parameter-dependent systems. In particular, we focus on the classical Stochastic Gradient Descent (SGD) approach of Robbins and Monro, and on the recently developed Continuous Stochastic Gradient (CSG) algorithm. We consider the problem of computing simultaneous controls through the minimization of a cost functional defined as the superposition of individual costs for each realization of the system. We compare the performances of these stochastic approaches, in terms of their computational complexity, with those of the more classical Gradient Descent (GD) and Conjugate Gradient (CG) algorithms, and we discuss the advantages and disadvantages of each methodology. In agreement with well-established results in the machine learning context, we show how the SGD and CSG algorithms can significantly reduce the computational burden when treating control problems depending on a large amount of parameters. This is corroborated by numerical experiments. KW - Parameter-dependent systems KW - simultaneous controllability KW - stochastic optimization KW - computational cost Y1 - 2020 ER - TY - JOUR A1 - Esteve, Carlos A1 - Kouhkouh, H A1 - Pighin, Dario A1 - Zuazua, Enrique T1 - The Turnpike property and the long-time behavior of the Hamilton-Jacobi equation N2 - In this work, we analyze the consequences that the so-called turnpike property has on the long-time behavior of the value function corresponding to an optimal control problem. As a by-product, we obtain the long-time behavior of the solution to the associated Hamilton-Jacobi-Bellman equation. In order to carry out our study, we use the setting of a finite-dimensional linear-quadratic optimal control problem, for which the turnpike property is well understood. We prove that, when the time horizon T tends to infinity, the value function converges to a travelling-front like solution of the form W(x) + c T + λ. In addition, we provide a control interpretation of each of these three terms in the spirit of the turnpike theory. Finally, we compare this asymptotic decomposition with the existing results on long-time behavior for Hamilton-Jacobi equations. We stress that in our case, the Hamiltonian is not coercive in the momentum variable, a case rarely considered in the classical literature about Hamilton-Jacobi equations. KW - Optimal control problems KW - long-time behavior KW - the turnpike property KW - Hamilton-Jacobi-Bellman equations KW - linear-quadratic Y1 - 2020 ER - TY - JOUR A1 - Ruiz-Balet, Domenec A1 - Zuazua, Enrique T1 - Control under constraints for multi-dimensional reaction-diffusion monostable and bistable equations N2 - Dynamic phenomena in social and biological sciences can often be modeled employing reaction diffusion equations. Frequently in applications, their control plays an important role when avoiding population extinction or propagation of infectious diseases, enhancing multicultural features, etc. When addressing these issues from a mathematical viewpoint one of the main challenges is that, because of the intrinsic nature of the models under consideration, the solution, typically a proportion or a density function, needs to preserve given lower and upper bounds (taking values in [0; 1])). Controlling the system to the desired final configuration then becomes complex, and sometimes even impossible. In the present work, we analyze the controllability to constant steady states of spatially homogeneous semilinear heat equations, with constraints in the state, and using boundary controls, which is indeed a natural way of acting on the system in the present context. The nonlinearities considered are among the most frequent: monostable and bistable ones. We prove that controlling the system to a constant steadystate may become impossible when the diffusivity is too small (or when the domain is large), due to the existence of barrier functions. When such an obstruction does not arise, we build sophisticated control strategies combining the dissipativity of the system, the existence of traveling waves, some connectivity of the set of steady states. This connectivity allows building paths that the controlled trajectories can follow, in a long time, with small oscillations, preserving the natural constraints of the system. This kind of strategy was successfully implemented in one space dimension, where phase plane analysis techniques allowed to decode the nature of the set of steady states. These techniques fail in the present multidimensional setting. We employ a fictitious domain technique, extending the system to a larger ball, and building paths of radially symmetric solution that can then be restricted to the original domain. The results are illustrated by numerical simulations of these models that find several applications, such as the extinction of minority languages or the survival of rare species in sufficiently large reserved areas. KW - Constraints KW - Controllability KW - Mathematical biology KW - Reaction-diffusion Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1016/j.matpur.2020.08.006 VL - 143 SP - 345 EP - 375 ER - TY - JOUR A1 - Ko, Dongnam A1 - Zuazua, Enrique T1 - Model predictive control with random batch methods for a guiding problem N2 - We model, simulate and control the guiding problem for a herd of evaders under the action of repulsive drivers. The problem is formulated in an optimal control framework, where the drivers (controls) aim to guide the evaders (states) to a desired region of the Euclidean space. The numerical simulation of such models quickly becomes unfeasible for a large number of interacting agents. To reduce the computational cost, we use the Random Batch Method (RBM), which provides a computationally feasible approximation of the dynamics. At each time step, the RBM randomly divides the set of particles into small subsets (batches), considering only the interactions inside each batch. Due to the averaging effect, the RBM approximation converges to the exact dynamics as the time discretization gets finer. We propose an algorithm that leads to the optimal control of a fixed RBM approximated trajectory using a classical gradient descent. The resulting control is not optimal for the original complete system, but rather for the reduced RBM model. We then adopt a Model Predictive Control (MPC) strategy to handle the error in the dynamics. While the system evolves in time, the MPC strategy consists in periodically updating the state and computing the optimal control over a long-time horizon, which is implemented recursively in a shorter time-horizon. This leads to a semi-feedback control strategy. Through numerical experiments we show that the combination of RBM and MPC leads to a significant reduction of the computational cost, preserving the capacity of controlling the overall dynamics. KW - Agent-based models KW - Guiding problem KW - large scale complex systems KW - Random Batch Method KW - Model Predictive Control Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1142/S0218202521500329 N1 - Ko Dongnam, Zuazua Enrique. Model predictive control with random batch methods for a guiding problem (2021). Math. Models Methods Appl. Sci., Vol. 31, No. 8, pp. 1569-1592. (2021) DOI: https://doi.org/10.1142/S0218202521500329 VL - 31 IS - 8 SP - 1569 EP - 1592 PB - Math. Models Methods Appl. Sci. ER - TY - JOUR A1 - Zuazua, Enrique T1 - Asymptotic behavior of scalar convection-diffusion equations N2 - In these lecture notes, we address the problem of large-time asymptotic behaviour of the solutions to scalar convection-diffusion equations set in [katex]\mathbb{R}^N[/katex]. The large-time asymptotic behaviour of the solutions to many convection-diffusion equations is strongly linked with the behavior of the initial data at infinity. In fact, when the initial datum is integrable and of mass [katex]M[/katex], the solutions to the equations under consideration oftentimes behave like the associated self-similar profile of mass [katex]M[/katex], thus emphasising the role of scaling variables in these scenarios. However, these equations can also manifest other asymptotic behaviors, including weakly non-linear, linear or strongly non-linear behavior depending on the form of the convective term. We give an exhaustive presentation of several results and techniques, where we clearly distinguish the role of the spatial dimension and the form of the nonlinear convective term. Y1 - 2020 ER - TY - JOUR A1 - Biccari, Umberto A1 - Zuazua, Enrique T1 - A Stochastic Approach to the Synchronization of Coupled Oscillators N2 - This paper deals with an optimal control problem associated with the Kuramoto model describing the dynamical behavior of a network of coupled oscillators. Our aim is to design a suitable control function allowing us to steer the system to a synchronized configuration in which all the oscillators are aligned on the same phase. This control is computed via the minimization of a given cost functional associated with the dynamics considered. For this minimization, we propose a novel approach based on the combination of a standard Gradient Descent (GD) methodology with the recently-developed Random Batch Method (RBM) for the efficient numerical approximation of collective dynamics. Our simulations show that the employment of RBM improves the performances of the GD algorithm, reducing the computational complexity of the minimization process and allowing for a more efficient control calculation. KW - coupled oscillators KW - gradient descent KW - Kuramoto model KW - optimal control KW - random batch method Y1 - 2020 U6 - https://doi.org/10.3389/fenrg.2020.00115 VL - 8 ER - TY - JOUR A1 - Heiland, Jan A1 - Zuazua, Enrique T1 - Classical system theory revisited for Turnpike in standard state space systems and impulse controllable descriptor systems N2 - The concept of turnpike connects the solution of long but finite time horizon optimal control problems with steady state optimal controls. A key ingredient of the analysis of the turnpike is the linear quadratic regulator problem and the convergence of the solution of the associated differential Riccati equation as the terminal time approaches infinity. This convergence has been investigated in linear systems theory in the 1980s. We extend classical system theoretic results for the investigation of turnpike properties of standard state space systems and descriptor systems. We present conditions for turnpike in the nondetectable case and for impulse controllable descriptor systems. For the latter, in line with the theory for standard linear systems, we establish existence and convergence of solutions to a generalized differential Riccati equation. KW - descriptor systems KW - linear systems KW - long time behavior KW - optimal control KW - Riccati equations Y1 - 2020 ER - TY - JOUR A1 - Esteve, Carlos A1 - Geshkovski, Borjan A1 - Pighin, Dario A1 - Zuazua, Enrique T1 - Large-time asymptotics in deep learning N2 - It is by now well-known that practical deep supervised learning may roughly be cast as an optimal control problem for a specific discrete-time, nonlinear dynamical system called an artificial neural network. In this work, we consider the continuous-time formulation of the deep supervised learning problem, and study the latter’s behavior when the final time horizon increases, a fact that can be interpreted as increasing the number of layers in the neural network setting. When considering the classical regularized empirical risk minimization problem, we show that, in long time, the optimal states converge to zero training error, namely approach the zero training error regime, whilst the optimal control parameters approach, on an appropriate scale, minimal norm parameters with corresponding states precisely in the zero training error regime. This result provides an alternative theoretical underpinning to the notion that neural networks learn best in the overparametrized regime, when seen from the large layer perspective. We also propose a learning problem consisting of minimizing a cost with a state tracking term, and establish the well-known turnpike property, which indicates that the solutions of the learning problem in long time intervals consist of three pieces, the first and the last of which being transient short-time arcs, and the middle piece being a long-time arc staying exponentially close to the optimal solution of an associated static learning problem. This property in fact stipulates a quantitative estimate for the number of layers required to reach the zero training error regime. Both of the aforementioned asymptotic regimes are addressed in the context of continuous-time and continuous space-time neural networks, the latter taking the form of nonlinear, integro-differential equations, hence covering residual neural networks with both fixed and possibly variable depths. KW - deep learning KW - Neural ODEs KW - optimal control KW - Residual Neural Networks KW - Supervised Learning Y1 - 2020 ER - TY - JOUR A1 - Esteve, C A1 - Zuazua, Enrique T1 - The Inverse Problem for Hamilton-Jacobi equations and Semiconcave Envelopes N2 - We study the inverse problem, or inverse design problem, for a time-evolution Hamilton-Jacobi equation. More precisely, given a target function [katex]u_T[/katex] and a time horizon [katex]T > 0[/katex], we aim to construct all the initial conditions for which the viscosity solution coincides with [katex]u_T[/katex] at time [katex]T[/katex]. As it is common in this kind of nonlinear equations, the target might not be reachable. We first study the existence of at least one initial condition leading the system to the given target. The natural candidate, which indeed allows determining the reachability of [katex]u_T[/katex] , is the one obtained by reversing the direction of time in the equation, considering [katex]u_T[/katex] as terminal condition. In this case, we use the notion of backward viscosity solution, that provides existence and uniqueness for the terminal-value problem. We also give an equivalent reachability condition based on a differential inequality, that relates the reachability of the target with its semiconcavity properties. Then, for the case when [katex]u_T[/katex] is reachable, we construct the set of all initial conditions for which the solution coincides with [katex]u_T[/katex] at time [katex]T[/katex]. Note that in general, such initial conditions are not unique. Finally, for the case when the target [katex]u_T[/katex] is not necessarily reachable, we study the projection of [katex]u_T[/katex] on the set of reachable targets, obtained by solving the problem backward and then forward in time. This projection is then identified with the solution of a fully nonlinear obstacle problem, and can be interpreted as the semiconcave envelope of [katex]u_T[/katex] , i.e. the smallest reachable target bounded from below by [katex]u_T[/katex] . KW - Remove term: Hamilton-Jacobi equation Hamilton-Jacobi equation KW - inverse design problem KW - obstacle problems KW - semiconcave envelopes Y1 - 2020 ER - TY - JOUR A1 - Bárcena, J.A. A1 - Zuazua, Enrique T1 - Averaged dynamics and control for heat equations with random diffusion N2 - Abstract. This paper deals with the averaged dynamics for heat equations in the degenerate case where the diffusivity coefficient, assumed to be constant, is allowed to take the null value. First we prove that the averaged dynamics is analytic. This allows to show that, most often, the averaged dynamics enjoys the property of unique continuation and is approximately controllable. We then determine if the averaged dynamics is actually null controllable or not depending on how the density of averaging behaves when the diffusivity vanishes. In the critical density threshold the dynamics of the average is similar to the $\frac{1}{2}$-fractional Laplacian, which is wellknown to be critical in the context of the controllability of fractional diffusion processes. Null controllability then fails (resp. holds) when the density weights more (resp. less) in the null diffusivity regime than in this critical regime. KW - Averaged controllability, averaged observability, observability, random heat equation Y1 - 2020 ER - TY - INPR A1 - Gabriel, Steven A. A1 - Leal, Marina A1 - Schmidt, Martin T1 - On Linear Bilevel Optimization Problems with Complementarity-Constrained Lower Levels N2 - We consider a novel class of linear bilevel optimization models with a lower level that is a linear program with complementarity constraints (LPCC). We present different single-level reformulations depending on whether the linear complementarity problem (LCP) as part of the lower-level constraint set depends on the upper-level decisions or not as well as on whether the LCP matrix is positive definite or positive semidefinite. Moreover, we illustrate the connection to linear trilevel models that can be reduced to bilevel problems with LPCC lower levels having positive (semi)definite matrices. Finally, we provide two generic and illustrative bilevel models from the fields of transportation and energy to show the practical relevance of the newly introduced class of bilevel problems and show related theoretical results. KW - Bilevel optimization KW - Linear programs with complementarity constraints KW - Linear complementarity problems KW - Reformulations KW - Spatial price equilibria Y1 - 2020 ER - TY - INPR A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - Why there is no need to use a big-M in linear bilevel optimization: A computational study of two ready-to-use approaches N2 - Linear bilevel optimization problems have gained increasing attention both in theory as well as in practical applications of Operations Research (OR) during the last years and decades. The latter is mainly due to the ability of this class of problems to model hierarchical decision processes. However, this ability makes bilevel problems also very hard to solve. Since no general-purpose solvers are available, a "best-practice" has developed in the applied OR community, in which not all people want to develop tailored algorithms but "just use" bilevel optimization as a modeling tool for practice. This best-practice is the big-M reformulation of the Karush-Kuhn-Tucker (KKT) conditions of the lower-level problem - an approach that has been shown to be highly problematic by Pineda and Morales (2019). Choosing invalid values for M yields solutions that may be arbitrarily bad. Checking the validity of the big-Ms is however shown to be as hard as solving the original bilevel problem in Kleinert et al. (2019). Nevertheless, due to its appealing simplicity, especially w.r.t. the required implementation effort, this ready-to-use approach still is the most popular method. Until now, there has been a lack of approaches that are competitive both in terms of implementation effort and computational cost. In this note we demonstrate that there is indeed another competitive ready-to-use approach: If the SOS-1 technique is applied to the KKT complementarity conditions, adding the simple additional root-node inequality developed by Kleinert et al. (2020) leads to a competitive performance - without having all the possible theoretical disadvantages of the big-M approach. KW - Bilevel optimization KW - Big-M KW - SOS-1 KW - Valid inequalities KW - Computational analysis Y1 - 2020 ER - TY - JOUR A1 - Egger, Herbert A1 - Philippi, Nora T1 - On the transport limit of singularly perturbed convection-diffusion problems on networks N2 - We consider singularly perturbed convection-diffusion equations on one-dimensional networks (metric graphs) as well as the transport problems arising in the vanishing diffusion limit. Suitable coupling condition at inner vertices are derived that guarantee conservation of mass as well as dissipation of a mathematical energy which allows us to prove stability and well-posedness. For single intervals and appropriately specified initial conditions, it is well-known that the solutions of the convection-diffusion problem converge to that of the transport problem with order O(sqrt(eps)) in the L1(L2)- norm with diffusion eps -> 0. In this paper, we prove a corresponding result for problems on one-dimensional networks. The main difficulty in the analysis is that the number and type of coupling conditions changes in the singular limit which gives rise to additional boundary layers at the interior vertices of the network. Since the values of the solution at these network junctions are not known a-priori, the asymptotic analysis requires a delicate choice of boundary layer functions that allows to handle these interior layers. Y1 - 2020 ER - TY - JOUR A1 - Egger, Herbert A1 - Philippi, Nora T1 - A hybrid discontinuous Galerkin method for transport equations on networks JF - Finite Volumes for Complex Applications IX - Methods, Theoretical Aspects, Examples N2 - We discuss the mathematical modeling and numerical discretization of 5 transport problems on one-dimensional networks. Suitable coupling conditions are derived that guarantee conservation of mass across network junctions and dissipation of a mathematical energy which allows us to prove existence of unique solutions. We then consider the space discretization by a hybrid discontinuous Galerkin method which provides a suitable upwind mechanism to handle the transport prob10 lem and allows to incorporate the coupling conditions in a natural manner. In addition, the method inherits mass conservation and stability of the continuous problem. Order optimal convergence rates are established and illustrated by numerical tests. Y1 - 2020 ER - TY - INPR A1 - Gugat, Martin A1 - Herty, Michael T1 - Limits of stabilizabilizy for a semilinear model for gas pipeline flow N2 - We present a positive and a negative stabilization result for a semilinear model of gas flow in pipelines. For feedback boundary conditions we obtain an unconditional stabilization result in the absence and conditional instability in the presence of the source term. We also obtain unconditional instability for the corresponding quasilinear model given by the isothermal Euler equations Y1 - 2020 ER - TY - INPR A1 - Gugat, Martin A1 - Herty, Michael T1 - Modeling, Control and Numerics of Gas Networks N2 - In this article we survey recent progress on mathematical results on gas flow in pipe networks with a special focus on questions of control and stabilization. We briefly present the modeling of gas flow and coupling conditions for flow through vertices of a network. Our main focus is on gas models for spatially one-dimensional flow governed by hyperbolic balance laws. We survey results on classical solutions as well as weak solutions. We present results on well–posedness, controllability, feedback stabilization, the inclusion of uncertainty in the models and numerical methods. KW - Hyperbolic Balance Laws, Stabilization, Exact Controllability, Modeling of Gas Flow, Finite-Volume Schemes, Optimal control, Uncertainty Y1 - 2020 ER - TY - JOUR A1 - Branda, Martin A1 - Henrion, René A1 - Pistek, Miroslav T1 - Producer’s Best Response in Pay-as-clear Day-ahead Electricity Market with Uncertain Demand N2 - We deal with several sources of uncertainty in electricity markets. The independent system operator (ISO) maximizes the social welfare using chance constraints to hedge against discrepancies between the estimated and real electricity demand. We find an explicit solution of the ISO problem, and use it to tackle the problem of a producer. In our model, production as well as income of a producer are determined based on the estimated electricity demand predicted by the ISO, that is unknown to producers. Thus, each producer is hedging against the uncertainty of prediction of the demand using the value-at-risk approach. To illustrate our results, a numerical study of a producer’s best response given a historical distribution of both estimated and real electricity demand is provided. KW - electricity market KW - multi-leader-common-follower game KW - stochastic demand KW - day-ahead bidding KW - chance constraints Y1 - 2020 ER - TY - JOUR A1 - Adam, Lukas A1 - Branda, Martin A1 - Heitsch, Holger A1 - Henrion, René T1 - Solving joint chance constrained problems using regularization and Benders' decomposition JF - Annals of Operations Research N2 - In this paper we investigate stochastic programs with joint chance constraints. We consider discrete scenario set and reformulate the problem by adding auxiliary variables. Since the resulting problem has a difficult feasible set, we regularize it. To decrease the dependence on the scenario number, we propose a numerical method by iteratively solving a master problem while adding Benders cuts. We find the solution of the slave problem (generating the Benders cuts) in a closed form and propose a heuristic method to decrease the number of cuts. We perform a numerical study by increasing the number of scenarios and compare our solution with a solution obtained by solving the same problem with continuous distribution. KW - chance constrained programming KW - optimality conditions KW - regularization KW - Benders cuts KW - gas networks Y1 - U6 - https://doi.org/10.1007/s10479-018-3091-9 VL - 292 SP - 683 EP - 709 ER - TY - INPR A1 - Bohlayer, Markus A1 - Bürger, Adrian A1 - Fleschutz, Markus A1 - Braun, Marco A1 - Zöttl, Gregor T1 - Multi-period investment pathways - Modeling approaches to design distributed energy systems under uncertainty N2 - Multi-modal distributed energy system planning is applied in the context of smart grids, industrial energy supply,and in the building energy sector. In real-world applications, these systems are commonly characterized by existing system structures of different age where monitoring and investment are conducted in a closed-loop, with the iterative possibility to invest. The literature contains two main approaches to approximate this computationally intensive multiperiod investment problem. The first approach simplifies the temporal decision-making process collapsing the multistage decision to a two-stage decision, considering uncertainty in the second stage decision variables. The second approach considers multi-period investments under the assumption of perfect foresight. In this work, we propose a multi-stage stochastic optimization problem that captures multi-period investment decisions under uncertainty and solves the problem to global optimality, serving as a first-best benchmark to the problem. To evaluate the performance of conventional approaches applied in a multi-year setup and to solve the multi-period problem at lower computational effort, we propose a rolling horizon heuristic that on the one hand reveals the performance of conventional approaches applied in a multi-period set-up and on the other hand enables planners to identify approximate solutions to the original multi-stage stochastic problem. Additionally, we consider an open-loop version of the rolling horizon algorithm to evaluate how single-period investments perform with respect to the entire scenario tree and compared to multi-period investments. We conduct a real-world case study and investigate solution quality as well as the computational performance of the proposed approaches. Our findings indicate that the approximation of multi-period investments by two-stage stochastic approaches yield the best results regarding constraint satisfaction, while deterministic multi-period approximations yield better economic and computational performance. Y1 - 2020 ER - TY - INPR A1 - Runge, Philipp A1 - Sölch, Christian A1 - Albert, Jakob A1 - Wasserscheid, Peter A1 - Zöttl, Gregor A1 - Grimm, Veronika T1 - Economic comparison of electric fuels produced at excellent locations for renewable energies: A Scenario for 2035 N2 - The use of electric fuels (e-fuels) enables CO2-neutral mobility and opens therefore an alternative to fossil-fuel-fired engines or battery-powered electric motors. This paper compares the cost-effectiveness of Fischer-Tropsch diesel, methanol, and hydrogen stored as cryogenic liquid (LH2) or in form of liquid organic hydrogen carriers (LOHCs). The production cost of those fuels are to a large extent driven by the energy-intensive electrolytic water splitting. The option of producing e-fuels in Germany competes with international locations with excellent conditions for renewable energy harvesting and thus very low levelized cost of electricity. We developed a mathematical model that covers the entire process chain. Starting with the production of the required resources such as fresh water, hydrogen, carbon dioxide, carbon monoxide, electrical and thermal energy, the subsequent chemical synthesis, the transport to filling stations in Germany and finally the energetic utilization of the fuels in the vehicle. We found that the choice of production site can have a major impact on the mobility cost using the respective fuels. Especially in case of diesel production, the levelized cost of electricity driven by the full load hours of the applied renewable energy source have a huge impact. An LOHC-based system is shown to be less dependent on the kind of electricity source compared to other technologies due to its comparatively low electricity consumption and the low cost for the hydrogenation units. The length of the transportation route and the price of the filling station infrastructure, on the other hand, clearly increase mobility cost for LOHC and LH2. KW - Electric fuels, Hydrogen Utilization, Hydrogen Import, LOHC, Mobility Y1 - 2020 ER - TY - JOUR A1 - Burger, Martin T1 - Network structured kinetic models of social interactions N2 - The aim of this paper is to study the derivation of appropriate meso- and macroscopic models for interactions as appearing in social processes. There are two main characteristics the models take into account, namely a network structure of interactions, which we treat by an appropriate mesoscopic description, and a different role of interacting agents. The latter differs from interactions treated in classical statistical mechanics in the sense that the agents do not have symmetric roles, but there is rather an active and a passive agent. We will demonstrate how a certain form of kinetic equations can be obtained to describe such interactions at a mesoscopic level and moreover obtain macroscopic models from monokinetics solutions of those. The derivation naturally leads to systems of nonlocal reaction-diffusion equations (or in a suitable limit local versions thereof), which can explain spatial phase separation phenomena found to emerge from the microscopic interactions. We will highlight the approach in three examples, namely the evolution and coarsening of dialects in human language, the construction of social norms, and the spread of an epidemic. Y1 - 2021 U6 - https://doi.org/10.1007/s10013-021-00505-8 ET - Vietnam Journal of Mathematics ER - TY - JOUR A1 - Gugat, Martin A1 - Giesselmann, Jan T1 - Boundary feedback stabilization of a semilinear model for the flow in star-shaped gas networks N2 - The flow of gas through a pipeline network can be modelled by a coupled system of 1-d quasilinear hyperbolic equations. In this system, the influence of certain source terms that model friction effects is essential. Often for the solution of control problems it is convenient to replace the quasilinear model by a simpler semilinear model. In this paper, we analyze the behavior of such a semilinear model on a star-shaped network. The model is derived from the diagonal form of the quasilinear model by replacing the eigenvalues by the sound speed multiplied by 1 or -1 respectively. Thus in the corresponding eigenvalues the influence of the gas velocity is neglected, which is justified in the applications since it is much smaller than the sound speed in the gas. For a star-shaped network of horizontal pipes for suitable coupling conditions we present boundary feedback laws that stabilize the system state exponentially fast to a position of rest for sufficiently small initial data. We show the exponential decay of the $H^1$-norm for arbitrarily long pipes. This is remarkable since in general even for linear systems, for certain source terms the system can become exponentially unstable if the space interval is too long. Our proofs are based upon observability inequalities for the $L^2$ and the $H^1$-norm. Y1 - 2020 U6 - https://doi.org/10.1051/cocv/2021061 CY - ESAIM:COCV ER - TY - JOUR A1 - Gugat, Martin A1 - Schuster, Michael A1 - Zuazua, Enrique T1 - M. Gugat, M. Schuster, E. Zuazua. The Finite-Time Turnpike Phenomenon for Optimal Control Problems: Stabilization by Non-Smooth Tracking Terms, in “Stabilization of Distributed Parameter Systems: Design Methods and Applications”. Grigory Sklyar Alexander Zuyev Eds., ICIAM 2019 SEMA SIMAI Springer Series 2, p. 17-42. ISSN 2199-3041 N2 - In this paper, problems of optimal control are considered where in the objective function, in addition to the control cost, there is a tracking term that measures the distance to a desired stationary state. The tracking term is given by some norm, and therefore it is in general not differentiable. In the optimal control problem, the initial state is prescribed. We assume that the system is either exactly controllable in the classical sense or nodal profile controllable. We show that both for systems that are governed by ordinary differential equations and for infinite-dimensional systems, for example, for boundary control systems governed by the wave equation, under certain assumptions, the optimal system state is steered exactly to the desired state after finite time. Y1 - 2020 VL - SEMA SIMAI Springer Series 2 SP - 17 EP - 42 PB - Springer International Publishing ET - Grigory Sklyar Alexander Zuyev Eds., ICIAM 2019 ER - TY - INPR A1 - Sarna, Neeraj A1 - Giesselmann, Jan A1 - Benner, Peter T1 - Data-Driven Snapshot Calibration via Monotonic Feature Matching N2 - Snapshot matrices of hyperbolic equations have a slow singular value decay, resulting in inefficient reduced-order models. We develop on the idea of inducing a faster singular value decay by computing snapshots on a transformed spatial domain, or the so-called snapshot calibration/transformation. We are particularly interested in problems involving shock collision, shock rarefaction-fan collision, shock formation, etc. For such problems, we propose a realizable algorithm to compute the spatial transform using monotonic feature matching. We consider discontinuities and kinks as features, and by carefully partitioning the parameter domain, we ensure that the spatial transform has properties that are desirable both from a theoretical and an implementation standpoint. We use these properties to prove that our method results in a fast $m$-width decay of a so-called calibrated manifold. A crucial observation we make is that due to calibration, the $m$-width does not only depend on $m$ but also on the accuracy of the full order model, which is in contrast to elliptic and parabolic problems that do not need calibration. The method we propose only requires the solution snapshots and not the underlying partial differential equation (PDE) and is therefore, data-driven. We perform several numerical experiments to demonstrate the effectiveness of our method. Y1 - 2020 ER - TY - JOUR A1 - Schuster, Michael A1 - Strauch, Elisa A1 - Gugat, Martin A1 - Lang, Jens T1 - Probabilistic Constrained Optimization on Flow Networks N2 - Uncertainty often plays an important role in dynamic flow problems. In this paper, we consider both, a stationary and a dynamic flow model with uncertain boundary data on networks. We introduce two different ways how to compute the probability for random boundary data to be feasible, discussing their advantages and disadvantages. In this context, feasible means, that the flow corresponding to the random boundary data meets some box constraints at the network junctions. The first method is the spheric radial decomposition and the second method is a kernel density estimation. In both settings, we consider certain optimization problems and we compute derivatives of the probabilistic constraint using the kernel density estimator. Moreover, we derive necessary optimality conditions for the stationary and the dynamic case. Throughout the paper, we use numerical examples to illustrate our results by comparing them with a classical Monte Carlo approach to compute the desired probability. KW - Probabilistic Constraints KW - Flow Networks KW - Gas Networks KW - Spheric Radial Decomposition KW - Kernel Density Estimator Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1007/s11081-021-09619-x VL - Optimization and Engineering ER - TY - INPR A1 - Aigner, Kevin-Martin A1 - Burlacu, Robert A1 - Liers, Frauke A1 - Martin, Alexander T1 - Solving AC Optimal Power Flow with Discrete Decisions to Global Optimality N2 - We present a solution framework for general alternating current optimal power flow (AC OPF) problems that include discrete decisions. The latter occur, for instance, in the context of the curtailment of renewables or the switching of power generation units and transmission lines. Our approach delivers globally optimal solutions and is provably convergent. We model AC OPF problems with discrete decisions as mixed-integer nonlinear programs. The solution method starts from a known framework that uses piecewise linear relaxations. These relaxations are modeled as as mixed-integer linear programs and adaptively refined until some termination criterion is fulfilled. In this work, we extend and complement this approach by problem-specific as well as very general algorithmic enhancements. In particular, these are mixed-integer second-order cone programs as well as primal and dual cutting planes. For example objective cuts and no-good-cuts help to compute good feasible solutions as where outer approximation constraints tighten the relaxations. We present extensive numerical results for various AC OPF problems where discrete decisions play a major role. Even for hard instances with a large proportion of discrete decisions, the method is able to generate high quality solutions efficiently. Furthermore, we compare our approach with state-of-the-art MINLP. Our method outperforms all other algorithms. KW - Mixed-Integer Nonlinear Programming KW - Second-Order Cone Programming KW - AC Optimal Power Flow KW - Discrete Decisions KW - Piecewise Linear Relaxation Y1 - 2020 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Global Optimization for the Multilevel European Gas Market System with Nonlinear Flow Models on Trees JF - Journal of Global Optimization N2 - The European gas market is implemented as an entry-exit system, which aims to decouple transport and trading of gas. It has been modeled in the literature as a multilevel problem, which contains a nonlinear flow model of gas physics. Besides the multilevel structure and the nonlinear flow model, the computation of so-called technical capacities is another major challenge. These lead to nonlinear adjustable robust constraints that are computationally intractable in general. We provide techniques to equivalently reformulate these nonlinear adjustable constraints as finitely many convex constraints including integer variables in the case that the underlying network is tree-shaped. We further derive additional combinatorial constraints that significantly speed up the solution process. Using our results, we can recast the multilevel model as a single-level nonconvex mixed-integer nonlinear problem, which we then solve on a real-world network, namely the Greek gas network, to global optimality. Overall, this is the first time that the considered multilevel entry-exit system can be solved for a real-world sized network and a nonlinear flow model. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-021-01099-8 ER - TY - THES A1 - Manns, Julian T1 - Presolve of Linear Bilevel Programs N2 - Bilevel programs are complex optimization problems that can be used to model hierarchical decision processes, which occur e.g. in energy markets, critical infrastructure defense or pricing models. Even the most simple bilevel programs, where only linear objective functions and constraints appear, are non-convex optimization problems and equivalent single level formulations replace the lower level problem by its non-convex optimality constraints. This makes linear bilevel programs inherently difficult so solve. The simplification of mixed-integer linear programs before solving them, called presolve, significantly accelerated the solving of these problems. However, there is only very few literature on the topic of presolve of bilevel programs. In this thesis we review said literature on presolve of bilevel programs in the context of linear bilevel programming, derive new theoretical foundations for presolve of linear bilevel programs and then apply these results to analyze how common presolve techniques for linear and mixed integer programs can be used to presolve linear bilevel programs. Y1 - 2020 ER - TY - INPR A1 - Biefel, Christian A1 - Liers, Frauke A1 - Rolfes, Jan A1 - Schmidt, Martin T1 - Affinely Adjustable Robust Linear Complementarity Problems N2 - Linear complementarity problems are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many sub-areas of mathematics like game theory, optimization, and matrix theory. Despite their close relation to optimization, the protection of LCPs against uncertainties - especially in the sense of robust optimization - is still in its infancy. During the last years, robust LCPs have only been studied using the notions of strict and Γ-robustness. Unfortunately, both concepts lead to the problem that the existence of robust solutions cannot be guaranteed. In this paper, we consider affinely adjustable robust LCPs. In the latter, a part of the LCP solution is allowed to adjust via a function that is affine in the uncertainty. We show that this notion of robustness allows to establish strong characterizations of solutions for the cases of uncertain matrix and vector, separately, from which existence results can be derived. Our main results are valid for the case of an uncertain LCP vector. Here, we additionally provide sufficient conditions on the LCP matrix for the uniqueness of a solution. Moreover, based on characterizations of the affinely adjustable robust solutions, we derive a mixed-integer programming formulation that allows to solve the corresponding robust counterpart. If, in addition, the certain LCP matrix is positive semidefinite, we prove polynomial-time solvability and uniqueness of robust solutions. If the LCP matrix is uncertain, characterizations of solutions are developed for every nominal matrix, i.e., these characterizations are, in particular, independent of the definiteness of the nominal matrix. Robust solutions are also shown to be unique for positive definite LCP matrix but both uniqueness and mixed-integer programming formulations still remain open problems if the nominal LCP matrix is not positive definite. KW - Linear Complementarity Problems KW - Adjustable Robustness KW - Robust Optimization KW - Existence KW - Uniqueness Y1 - 2020 ER -