Friedrich-Alexander-Universität Erlangen-Nürnberg
Refine
Year of publication
- 2020 (25) (remove)
Has Fulltext
- yes (25)
Keywords
- Mixed-Integer Nonlinear Programming (2)
- Robust Optimization (2)
- A posteriori error estimates (1)
- AC Optimal Power Flow (1)
- Adjustable Robustness (1)
- Averaged controllability, averaged observability, observability, random heat equation (1)
- Big-M (1)
- Bilevel optimization (1)
- Computational Complexity (1)
- Computational analysis (1)
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.
Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems
(2020)
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.
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.
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.
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.
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
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.
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.
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.
Boundary feedback stabilization of a semilinear model for the flow in star-shaped gas networks
(2020)
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.
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.
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.
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.
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.
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.
This contribution focuses on the analysis and control of friction-dominated flow of gas in pipes. The pressure in the gas flow is governed by a partial differential equation that is a doubly nonlinear parabolic equation of p-Laplace type, where p=2/3. Such equations exhibit positive solutions, finite speed of propagation and satisfy a maximum principle. The pressure is fixed on one end (upstream), and the flow is specified on the other end (downstream). These boundary conditions determine a unique steady equilibrium flow. We present a boundary feedback flow control scheme, that ensures local exponential stability of the equilibrium in an L2-sense. The analysis is done both for the pde system and an ode system that is obtained by a suitable spatial semi-discretization. The proofs are based upon suitably chosen Lyapunov functions.
While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas market. For this nontrivial class of games, we develop a solution algorithm that is able to compute the complete set of Nash equilibria instead of just individual solutions or a bigger set of stationary points. Additionally, we prove that for this class of games, the solution set is finite and provide examples for instances without any Nash equilibria in pure strategies. We apply the algorithm to a case study in which we compute strategic booking and nomination decisions in a model of the European entry-exit gas market system. Finally, we use our algorithm to provide a publicly available test library for the considered class of multi-leader multi-follower games. This library contains problem instances with different economic and mathematical properties so that other researchers in the field can test and benchmark newly developed methods for this challenging class of problems.
Liberalized gas markets in Europe are organized as entry-exit regimes so that gas trade and transport are decoupled. The decoupling is achieved via the announcement of technical capacities by the transmission system operator (TSO) at all entry and exit points of the network. These capacities can be booked by gas suppliers and customers in long-term contracts. Only traders who have booked capacities up-front can "nominate" quantities for injection or withdrawal of gas via a day-ahead market. To ensure feasibility of the nominations for the physical network, the TSO must only announce technical capacities for which all possibly nominated quantities are transportable. In this paper, we use a four-level model of the entry-exit gas market to analyze possible welfare losses associated with the decoupling of gas trade and transport. In addition to the multilevel structure, the model contains robust aspects to cover the conservative nature of the European entry-exit system. We provide several reformulations to obtain a single-level mixed-integer quadratic problem. The overall model of the considered market regime is extremely challenging and we thus have to make the main assumption that gas flows are modeled as potential-based linear flows. Using the derived single-level reformulation of the problem, we show that the feasibility requirements for technical capacities imply significant welfare losses due to unused network capacity. Furthermore, we find that the specific structure of the network has a considerable influence on the optimal choice of technical capacities. Our results thus show that trade and transport are not decoupled in the long term. As a further source of welfare losses and discrimination against individual actors, we identify the minimum prices for booking capacity at the individual nodes.
Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances.
We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this existing characterization of the literature to prove that FB is coNP-hard by reducing Partition to the infeasibility of a booking. We further prove that computing a potential-difference maximizing load flow scenario is NP-hard even if we can determine the flow direction a priori. From the literature, it is known that FB can be decided in polynomial time on trees and a single cycle. Thus, our hardness result draws the first line that separates the easy from the hard variants of FB and finally answers that FB is hard in general.