Refine
Year of publication
Keywords
- Bilevel optimization (16)
- Gas networks (8)
- Optimal control (8)
- Robust optimization (8)
- Uniqueness (7)
- optimal control (7)
- Mixed-Integer Nonlinear Optimization (6)
- Mixed-integer optimization (6)
- Convergence (5)
- Gas Networks (5)
We study the classic single-item auction setting of Myerson, but under the assumption that the buyers' values for the item are distributed over "finite" supports. Using strong LP duality and polyhedral theory, we rederive various key results regarding the revenue-maximizing auction, including the characterization through virtual welfare maximization and the optimality of deterministic mechanisms, as well as a novel, generic equivalence between dominant-strategy and Bayesian incentive compatibility.
Inspired by this, we abstract our approach to handle more general auction settings, where the feasibility space can be given by arbitrary convex constraints, and the objective is a linear combination of revenue and social welfare. We characterize the optimal auctions of such systems as generalized virtual welfare maximizers, by making use of their KKT conditions, and we present an analogue of Myerson's payment formula for general discrete single-parameter auction settings. Additionally, we prove that total unimodularity of the feasibility space is a sufficient condition to guarantee the optimality of auctions with integral allocation rules.
Finally, we demonstrate this KKT approach by applying it to a setting where bidders are interested in buying feasible flows on trees with capacity constraints, and provide a combinatorial description of the (randomized, in general) optimal auction.
The optimal control problems for the wave equation are considered on networks. The turnpike property is shown for the state equation, the adjoint state equation as well as the optimal cost. The shape and topology optimization is performed for the network with the shape functional given by the optimality system of the control problem. The set of admissible shapes for the network is compact in finite dimensions, thus the use of turnpike property is straightforward. The topology optimization is analysed for an example of nucleation of a small cycle at the internal node of network. The topological derivative of the cost is introduced and evaluated in the framework of domain decomposition technique. Numerical examples are provided.
We consider the Euler equations for a pipeline flow of a mixture of two gases. An important application is hydrogen blending. Existence and uniqueness of semi-global solutions is shown and possible boundary conditions are analyzed.
Secondly, we consider classes of associated optimal control problems and show existence of solutions.
In the operation of pipeline networks, compressors play a crucial role in ensuring the network’s functionality for various scenarios. In this contribution we address the important question of finding the optimal location of the compressors. This problem is of a novel structure, since it is related
with the gas dynamics that governs the network flow. That results in non-convex mixed integer stochastic optimization problems with probabilistic constraints.
Using a steady state model for the gas flow in pipeline networks including compressor control and uncertain loads given by certain probability distributions, the problem of finding the optimal location for the
control on the network, s.t. the control cost is minimal and the gas pressure stays within given bounds, is considered.
In the deterministic setting, explicit bounds for the pipe length and the inlet pressure, s.t. a unique optimal compressor location with minimal control cost exists, are presented. In the probabilistic setting,
an existence result for the optimal compressor location is presented and the uniqueness of the solution is discussed depending on the probability distribution. For Gaussian distributed loads a uniqueness result
for the optimal compressor location is presented.
Further the problem of finding the optimal compressor locations on networks including the number of compressor stations as variable is considered. Results for the existence of optimal locations on a graph in
both, the deterministic and the probabilistic setting, are presented and the uniqueness of the solutions is discussed depending on probability distributions and graph topology. The paper concludes with an illustrative example demonstrating that the compressor locations determined using a steady state approach are also admissible in transient settings.
On the Convergence of Optimization Problems with Kernel Density Estimated Probabilistic Constraints
(2024)
Uncertainty plays a significant role in applied mathematics and probabilistic constraints are widely used to model uncertainty in various fields, even if probabilistic constraints often demand computational challenges. Kernel density estimation (KDE) provides a data-driven approach for properly estimating probability density functions and efficiently evaluate corresponding probabilities.
In this paper, we investigate optimization problems with probabilistic constraints, where the probabilities are approximated using a KDE approach. We establish sufficient conditions under which the solution of the KDE approximated optimization problem converges to the solution of the original problem as the sample size goes to infinity.
The main results of this paper include three theorems: (1) For sufficiently large sample sizes, the solution of the original problem is also a solution of the approximated problem, if the probabilistic constraint is passive; (2) The limit of a convergent sequence of solutions of the approximated problems is a solution of the original problem, if the KDE uniformly converges; (3) We provide sufficient conditions for the existence of a convergent sequence of solutions of the approximated problems.
We present a feedback scheme for non-cooperative dynamic games and investigate its stabilizing properties. The dynamic games are modeled as generalized Nash equilibrium problems (GNEP), in which the shared constraint consists of linear time-discrete dynamic equations (e.g., sampled from a partial or ordinary differential equation), which are jointly controlled by the players’ actions. Further, the individual objectives of the players are interdependent and defined over a fixed time horizon. The feedback law is synthesized by moving-horizon model predictive control (MPC). We investigate the asymptotic stability of the resulting closed-loop dynamics. To this end, we introduce α-quasi GNEPs, a family of auxiliary problems based on a modification of the Nikaido–Isoda function, which approximate the original games. Basing the MPC scheme on these auxiliary problems, we derive conditions on the players’ objectives, which guarantee asymptotic stability of the closed-loop if stabilizing end constraints are enforced. This analysis is based on showing that the associated optimal-value function is a Lyapunov function. Additionally, we identify a suitable Lyapunov function for the MPC scheme based on the original GNEP, whose solution fulfills the stabilizing end constraints. The theoretical results are complemented by numerical experiments.
Outer approximation for generalized convex mixed-integer nonlinear robust optimization problems
(2024)
We consider mixed-integer nonlinear robust optimization problems with nonconvexities. In detail, the functions can be nonsmooth and generalized convex, i.e., f°-quasiconvex or f°-pseudoconvex. We propose a robust optimization method that requires no certain structure of the adversarial problem, but only approximate worst-case evaluations. The method integrates a bundle method, for continuous subproblems, into an outer approximation approach. We prove that our algorithm converges and finds an approximately robust optimal solution and propose robust gas transport as a suitable application.
We study network design problems for nonlinear and nonconvex flow models under demand uncertainties. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, demand scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we show that a given network design is robust feasible, i.e., it admits a feasible transport for all demand uncertainties, if and only if a finite number of worst-case demand scenarios can be routed through the network. We compute these worst-case scenarios by solving polynomially many nonlinear optimization problems. Embedding this result for robust feasibility in an adversarial approach leads to an exact algorithm that computes an optimal robust network design in a finite number of iterations. Since all of the results are valid for general potential-based flows, the approach can be applied to different utility networks such as gas, hydrogen, or water networks. We finally demonstrate the applicability of the method by computing robust gas networks that are protected from future demand fluctuations.
High-dimensional interpolation problems appear in various applications of uncertainty quantification, stochastic optimization and machine learning. Such problems are computationally expensive and request the use of adaptive grid generation strategies like anisotropic sparse grids to mitigate the curse of dimensionality. However, it is well known that the standard dimension-adaptive sparse grid method converges very slowly or even fails in the case of non-smooth functions. For piecewise smooth functions with kinks, we construct two novel hp-adaptive sparse grid collocation algorithms that combine low-order basis functions with local support in parts of the domain with less regularity and variable-order basis functions elsewhere. Spatial refinement is realized by means of a hierarchical multivariate knot tree which allows the construction of localised hierarchical basis functions with varying order. Hierarchical surplus is used as an error indicator to automatically detect the non-smooth region and adaptively refine the collocation points there. The local polynomial degrees are optionally selected by a greedy approach or a kink detection procedure. Three numerical benchmark examples with different dimensions are discussed and comparison with locally linear and highest degree basis functions are given to show the efficiency and accuracy of the proposed methods.
Method-of-lines discretizations are demanding test problems for stiff inte-
gration methods. However, for PDE problems with known analytic solution
the presence of space discretization errors or the need to use codes to compute
reference solutions may limit the validity of numerical test results. To over-
come these drawbacks we present in this short note a simple test problem with
boundary control, a situation where one-step methods may suffer from order
reduction. We derive exact formulas for the solution of an optimal boundary
control problem governed by a one-dimensional discrete heat equation and an
objective function that measures the distance of the final state from the target
and the control costs. This analytical setting is used to compare the numeri-
cally observed convergence orders for selected implicit Runge-Kutta and Peer
two-step methods of classical order four which are suitable for optimal control
problems.
Physics informed neural networks have been recently proposed and offer a new promising method to solve differential equations. They have been adapted to many more scenarios and different variations of the original method have been proposed. In this case study we review many of these variations. We focus on variants that can compensate for imbalances in the loss function and perform a comprehensive numerical comparison of these variants with application to gas transport problems. Our case study includes different formulations of the loss function, different algorithmic loss balancing methods, different optimization schemes and different numbers of parameters and sampling points. We conclude that the original PINN approach with specifically chosen constant weights in the loss function gives the best results in our tests. These weights have been obtained by a computationally expensive random-search scheme. We further conclude for our test case that loss balancing methods which were developed for other differential equations have no benefit for gas transport problems, that the control volume physics informed formulation has no benefit against the initial formulation and that the best optimization strategy is the L-BFGS method.
This paper is concerned with the construction and convergence analysis
of novel implicit Peer triplets of two-step nature with four stages for nonlinear
ODE constrained optimal control problems. We combine the property of superconvergence
of some standard Peer method for inner grid points with carefully
designed starting and end methods to achieve order four for the state variables
and order three for the adjoint variables in a first-discretize-then-optimize approach
together with A-stability. The notion triplets emphasizes that these
three different Peer methods have to satisfy additional matching conditions.
Four such Peer triplets of practical interest are constructed. Also as a benchmark
method, the well-known backward differentiation formula BDF4, which is
only A(73.35)-stable, is extended to a special Peer triplet to supply an adjoint
consistent method of higher order and BDF type with equidistant nodes. Within
the class of Peer triplets, we found a diagonally implicit A(84)-stable method
with nodes symmetric in [0,1] to a common center that performs equally well.
Numerical tests with three well established optimal control problems confirm
the theoretical findings also concerning A-stability.
With this overview we want to provide a compilation of different models for
the description of gas flow in networks in order to facilitate the introduction
to the topic. Special attention is paid to the hierarchical structure inherent
to the modeling, and the detailed description of individual components such
as valves and compressors. Also included are network model classes based
on purely algebraic relations, and energy-based port-Hamiltonian models. A
short overview of basic numerical methods and concepts for the treatment
of hyperbolic balance equations is also given. We do not claim completeness
and refer in many places to the existing literature.
Implicit Peer Triplets in Gradient-Based Solution Algorithms for ODE Constrained Optimal Control
(2024)
It is common practice to apply gradient-based optimization algorithms to
numerically solve large-scale ODE constrained optimal control problems. Gradients
of the objective function are most efficiently computed by approximate
adjoint variables. High accuracy with moderate computing time can be achieved
by such time integration methods that satisfy a sufficiently large number of adjoint
order conditions and supply gradients with higher orders of consistency. In
this paper, we upgrade our former implicit two-step Peer triplets constructed in
[Algorithms, 15:310, 2022] to meet those new requirements. Since Peer methods
use several stages of the same high stage order, a decisive advantage is their lack
of order reduction as for semi-discretized PDE problems with boundary control.
Additional order conditions for the control and certain positivity requirements
now intensify the demands on the Peer triplet. We discuss the construction of
4-stage methods with order pairs (4,3) and (3,3) in detail and provide three
Peer triplets of practical interest. We prove convergence for s-stage methods,
for instance, order s for the state variables even if the adjoint method and the
control satisfy the conditions for order s-1, only. Numerical tests show the
expected order of convergence for the new Peer triplets.
We propose a method to solve linear generalized Nash equilibrium problems (LGNEPs). For this purpose, a reformulation of the LGNEPs as piecewise linear problems is considered. This requires the calculation of all vertices for a special kind of unbounded convex polyhedra. Then the active signature method for constrained abs-linear problems can be used to determine the Nash equilibria. We analyse the computational effort for the resulting solution procedure. This includes also the verification of suitable optimality conditions. Finally, we present and analyse numerical results for some test problems.
The entropy-based moment method is a well-known discretization for the velocity variable in kinetic equations which has many desirable theoretical properties but is difficult to implement with high-order numerical methods. The regularized entropy-based moment method was recently introduced to remove one of the main challenges in the implementation of the entropy-based moment method, namely the requirement of the realizability of the numerical solution. In this work we use the method of relative entropy to prove the convergence of the regularized method to the original method as the regularization parameter goes to zero and give convergence rates. Our main assumptions are the boundedness of the velocity domain and that the original moment solution is Lipschitz continuous in space and bounded away from the boundary of realizability. We provide results from numerical simulations showing that the convergence rates we prove are optimal.
We study a finite volume scheme approximating a parabolic-elliptic Keller-Segel system with power law diffusion with exponent γ∈[1,3] and periodic boundary conditions. We derive conditional a posteriori bounds for the error measured in the L∞(0,T;H1(Ω)) norm for the chemoattractant and by a quasi-norm-like quantity for the density. These results are based on stability estimates and suitable conforming reconstructions of the numerical solution. We perform numerical experiments showing that our error bounds are linear in mesh width and elucidating the behaviour of the error estimator under changes of γ.
A posteriori error control for a Discontinuous Galerkin approximation of a Keller-Segel model
(2024)
We provide a posteriori error estimates for a discontinuous Galerkin scheme for the parabolic-elliptic Keller-Segel system in 2 or 3 space dimensions. The estimates are conditional, in the sense that an a posteriori computable quantity needs to be small enough - which can be ensured by mesh refinement - and optimal in the sense that the error estimator decays with the same order as the error under mesh refinement. A specific feature of our error estimator is that it can be used to prove existence of a weak solution up to a certain time based on numerical results.
In this paper, we develop reliable a posteriori error estimates for numerical approximations of scalar hyperbolic conservation laws in one space dimension.
Our methods have no inherent small-data limitations and are a step towards error control of numerical schemes for systems. We are careful not to appeal to the Kruzhkov theory for scalar conservation laws. Instead, we derive novel quantitative stability estimates that extend the theory of shifts, and in particular, the framework for proving stability first developed by the second author and Vasseur. This is the first time this methodology has been used for quantitative estimates.
We work entirely within the context of the theory of shifts and a-contraction, techniques which adapt well to systems. In fact, the stability framework by the second author and Vasseur has itself recently been pushed to systems [Chen-Krupa-Vasseur. Uniqueness and weak-BV stability for 2×2 conservation laws. Arch. Ration. Mech. Anal., 246(1):299--332, 2022].
Our theoretical findings are complemented by a numerical implementation in MATLAB and numerical experiments.
Regularity and long time behavior of a doubly nonlinear parabolic problem and its discretization
(2024)
We study a doubly nonlinear parabolic problem arising in the modeling of gas transport in pipelines. Using convexity arguments and relative entropy estimates we show uniform bounds and exponential stability of discrete approximations obtained by a finite element method and implicit time stepping. Due to convergence of the approximations to weak solutions of the problem, our results also imply regularity, uniqueness, and long time stability of weak solutions of the continuous problem.
An Observer for pipeline flow with hydrogen blending in gas networks: exponential synchronization
(2024)
We consider a state estimation problem for gas flows in pipeline networks where hydrogen is blended into the natural gas. The flow is modeled by the quasi-linear isothermal Euler equations coupled to an advection equation on a graph. The flow through the vertices where the pipes are connected is governed by algebraic node conditions. The state is approximated by an observer system that uses nodal measurements. We prove that the state of the observer system converges to the original system state exponentially fast in the L2-norm if the measurements are exact. If measurement errors are present we show that the observer state approximates the original system state up to an error that is proportional to the maximal measurement error. The proof of the synchronization result uses Lyapunov functions with exponential weights.
A Gradient-Based Method for Joint Chance-Constrained Optimization with Continuous Distributions
(2024)
The input parameters of an optimization problem are often affected by uncertainties. Chance constraints are a common way to model stochastic uncertainties in the constraints. Typically, algorithms for solving chance-constrained problems require convex functions or discrete probability distributions. In this work, we go one step further and allow non-convexities as well as continuous distributions. We propose a gradient-based approach to approximately solve joint chance-constrained models. We approximate the original problem by smoothing indicator functions. Then, the smoothed chance constraints are relaxed by penalizing their violation in the objective function. The approximation problem is solved with the Continuous Stochastic Gradient method that is an enhanced version of the stochastic gradient descent and has recently been introduced in the literature. We present a convergence theory for the smoothing and penalty approximations. Under very mild assumptions, our approach is applicable to a wide range of chance-constrained optimization problems. As an example, we illustrate its computational efficiency on difficult practical problems arising in the operation of gas networks. The numerical experiments demonstrate that the approach quickly finds nearly feasible solutions for joint chance-constrained problems with non-convex constraint functions and continuous distributions, even for realistically-sized instances.
In this paper, we discuss optimality conditions for optimization problems {involving} random state constraints, which are modeled in probabilistic or almost sure form. While the latter can be understood as the limiting case of the former, the derivation of optimality conditions requires substantially different approaches. We apply them to a linear elliptic partial differential equation (PDE) with random inputs.
In the probabilistic case, we rely on the spherical-radial decomposition of Gaussian random vectors in order to formulate fully explicit optimality conditions involving a spherical integral. In the almost sure case, we derive optimality conditions and compare them to a model based on robust constraints with respect to the (compact) support of the given distribution.
We consider the optimal control of a PDE with random source term subject to probabilistic or almost sure state constraints. In the main theoretical result, we provide an exact formula for the Clarke subdifferential of the probability function without a restrictive assumption made in an earlier paper. The focus of the paper is on numerical solution algorithms. As for probabilistic constraints, we apply the method of spherical radial decomposition. Almost sure constraints are dealt with a Moreau--Yosida smoothing of the constraint function accompanied by Monte Carlo sampling of the given distribution or its support or even just the boundary of its support. Moreover, one can understand the almost sure constraint as a probabilistic constraint with safety level one which offers yet another perspective. Finally, robust optimization can be applied efficiently when the support is sufficiently simple. A comparative study of these five different methodologies is carried out and illustrated.
Indirect methods for optimal control of hybrid PDE-dynamical / switching systems using relaxation
(2023)
We propose a novel algorithmic approach to computationally solve optimal control problems governed by linear evolution-type PDEs including a state-dependent control-regime switching mechanism. We introduce an equivalent mixed-integer formulation featuring vanishing constraints arising by methods of disjunctive programming. We embed the problem into the class of equilibrium constraints by introduction of an additional slack variable. Based on theoretical results associated with Sum-Up-Rounding strategies, we proceed with the solution of the related relaxed formulation by an indirect approach. In order to obtain a computationally tractable optimality system, we apply a Moreau-Yosida type penalty approach of the vanishing constraints. After the theoretical discussion, we introduce and exert the algorithmic framework founded on a semismooth Newton method. Finally, we communicate computational experiments based on our approach.
We propose a framework that allows to quantitatively analyze the interplay of the different agents involved in gas trade and transport in the context of the European entry-exit system. Previous contributions have focused on the case of perfectly competitive buyers and sellers of gas, which allows to replace the respective market equilibrium problem by a single welfare maximization problem. Our novel framework considers the mathematically more challenging case of a monopolistic and thus strategic gas seller. In this framework, the objective functions of the gas sellers and buyers cannot be aggregated into a common objective function, which is why a multilevel formulation is necessary to accurately capture the sequential nature of the decisions taken. For this setup, we derive sufficient conditions that allow for reformulating the challenging four-level model as a computationally tractable single-level reformulation. We prove the correctness of this reformulation and use it for solving several test instances to illustrate the applicability of our approach.
Design of foundations on an elastic base is carried out using the solution of three-dimensional problems of contact interaction. Improving the accuracy of engineering calculations is necessary to ensure economic efficiency and increase energy savings in green building. The problems of indentation of punches with a flat base bounded by doubly connected close to polygonal contact areas are researched in the present work. Small parameter method is used to obtain explicit analytical expressions for the contact pressure distribution and the punch displacement dependence in a simplified form, which is convenient for engineering practice. The found load-displacement dependence satisfies the known inequalities that are valid for an arbitrary contact domain. Also a numerical-analytical method is in consideration. It uses the simple layer potential expansion and successive approximations for the problems accounting roughness of the elastic half-space. Roughness coefficient is considered as a parameter of regularization of the integral equation for the smooth contact problem. The results of both methods coincide with sufficient accuracy.
Decomposition Methods for Time-Dependent Mixed-Integer Nonlinear Optimization Problems on Graphs
(2023)
Decomposition can be the method of choice to deal with optimization problems that contain hard to solve model structures or that are of large scale. The main idea is to decompose the problematic aspects of the problem into multiple smaller blocks that can be solved more easily. Here, the challenge is to combine the single pieces to a solution that is not only feasible but maybe even optimal for the original problem. In many cases, this can be done by introducing an iteration that eventually converges to a desired solution.
In this cumulative dissertation, we present several iterative decomposition methods that are tailored to different types of optimization models and use distinct approaches to split up the problems. Our main motivation for this originates from the optimization of gas transport networks, where we encounter partial differential equations as well as discrete control decisions. Additionally, we engage in the related field of district heating network optimization to study the challenges arising from large-scale and fully discretized systems as well as undesirable model features such as, e.g., complementarity constraints. Here, we introduce two temperature mixing models that are well suited for optimization and a number of techniques to speed up the solution process, which are applied in numerical experiments.
As a next step, we develop an iterative time-domain decomposition method that is applied to optimal control problems subject to semilinear hyperbolic systems of partial differential equations. For this, we derive first-order optimality conditions that are then split using a non-overlapping decomposition of the time horizon. We exploit the fact that the resulting systems have a primal interpretation as so-called virtual control problems. We prove the convergence of the iterative method and develop a posteriori error estimates. Later, we extend the scheme to systems of ordinary differential equations with mixed- integer controls by using Pontryagin’s maximum principle. We again show the convergence and conduct a numerical case study.
Moreover, we use a consensus-based version of the classic penalty alternating direction method to solve tailored reformulations of transient gas network problems that allow us to minimize the number of coupling constraints between sub-problems. Here, we utilize the quasi-separable structure of the network to decompose it into sub-networks with more desirable properties. We also discuss different decomposition strategies and test them in a numerical case study. Finally, we present a successive linear relaxation method for mixed-integer nonlinear problems with multivariate Lipschitz continuous nonlinearities. The distinguishing feature of this algorithm is that it exploits no properties of the nonlinearities besides the Lipschitz constants. Therefore, the method is
applicable for problems with non-convex or even non-differentiable constraints. The nonlinearities do not even need to be given in a closed form, which allows us to integrate black-box constraints into the model. We prove that the algorithm converges to an approximate global optimum and we provide a worst-case estimate for the number of iterations. The iterative method is applied to stationary gas transport problems, where implicitly given solutions of the differential equations are modeled via black-box constraints.
In this paper, we deal with a renewable-powered mini-grid, connected to an unreliable main grid, in a Joint Chance Constrained (JCC) programming setting.
In many countries with low energy access rates, grid-connected mini-grid system operators contend with four different types of uncertainties: stochastic solar
power and demand forecast errors; absolute uncertain national grid outage onset
times; and outages duration subjected to statistical analysis. These uncertainties
pose new challenges to the classical power system’s operation tasks. Two alternatives to the JCC problem are presented. In particular, we present an Individual
Chance Constraint (ICC) and a purely deterministic dispatch model. The JCC
model has the capability to address all four uncertainties, while the ICC covers only three of them, overlooking the uncertainty about the outage duration.
In contrast, the purely deterministic model completely ignores any uncertain
parameters. We illustrate the three models through a comparison of outcomes
attained from a real mini-grid in Lake Victoria, Tanzania. Results show how the
dispatch is modified across the models to plan the battery and diesel reserves in
the chance-constrained models, with the reserves in the JCC being larger than
in the ICC model. In comparison between all models, we prove that the JCC model offers the most robust results, since it can handle uncertainties about forecasting errors, on the one hand, and grid outages, on the other. The results also
show that the decrease in profits due to the hedging with reserves kept in the
MG is significantly small compared to the high level of reliability reached and
the potential load shedding that could be avoided in the case of an outage.
The objective is to optimize the pressure distribution under a rigid punch having a doubly connected contact domain close to a circular ring and interacting with an elastic half-space. The required design variable is the punch shape. The functional to be minimized is the root-mean-square deviation of the pressure distribution from some given distribution. An analytical technique is developed for solving the problem for the punches with doubly connected shape, by reducing to a sequence of similar problems for the circular ring punches using expansions of the simple layer potential. The method of expansion in terms of a small parameter is used. The simple layer potential expansion is proposed when mapping a doubly connected integration domain onto a circular ring by transforming the integration variables and transforming the coordinates of the pole of the kernel. As a result, a sequence of similar problems was obtained for a circular ring to determine the functions characterizing the distribution of normal pressure under the punch in the form of a non-circular ring, as well as the normal displacements, from where the optimal punch shape is determined.
Robust and bilevel optimization share the common feature that they involve a certain multilevel structure. Hence, although they model something rather different when used in practice, they seem to have a similar mathematical structure. In this paper, we analyze the connections between different types of robust problems (static robust problems with and without decision-dependence of their uncertainty sets, worst-case regret problems, and two-stage robust problems) as well as of bilevel problems (optimistic problems, pessimistic problems, and robust bilevel problems). It turns out that bilevel optimization seems to be more general in the sense that for most types of robust problems, one can find proper reformulations as bilevel problems but not necessarily the other way around. We hope that these results pave the way for a stronger connection between the two fields - in particular to use both theory and algorithms from one field in the other and vice versa.
The dynamical, boundary optimal control problems
on networks are considered. The domain of definition for the distributed parameter system is given by a graph G. The optimal cost function for control problem is further optimized with respect to the shape and topology of the graph Ω. The small cycle is introduced and the topological derivative of the cost with respect to the size of the cycle is determined. In this way, the singular perturbations of the graph can be analyzed in order to change the topology Ω. The topological derivative method in shape and topology optimization is a new tool which can be used to minimize the shape functionals under the Partial Differential
Equations (PDEs) constraints. The topological derivative is used as well for solution of optimum design problems for graphs. In optimal control problems the topological derivative is used for
optimum design of the domain of integration of the state equation. As an example, optimal control problems are considered on a cross with a small cycle. The state equation is the wave equation
on the graph. The boundary control problem by Neumann
conditions at a boundary vertex is solved for a tracking cost function. The shape functional is given by the optimal value of the control cost. The topological derivative of the shape functional is determined for the steady state model with the size of a cycle ε → 0. Numerical results for a model problem are presented.
We present an algorithmic approach for the computational solution of optimal control problems with hybrid nature governed by linear parabolic PDEs featuring implicit switches. We propose a stepwise reformulation of the original formulation into a more tractable setting via application of methods from disjunctive programming and a time transformation method.
After removal of the implicit switching rule at the cost of the introduction of explicit switching variables and vanishing constraints, the connection of the resulting formulation to problems with equilibrium constraints is established and studied. The previous steps in combination with smoothening and a Moreau-Yosida type penalty approach allow the derivation of necessary first order optimality conditions to characterize candidates for optimality to the original system. Following the discussion of each individual reformulation step, we introduce the algorithmic framework founded on a semismooth Newton method. Finally, we report on computational of the proposed framework.
Optimal control problems usually involve constraints which model physical states and their possible transitions. These are represented by ordinary or partial differential equations (ODEs/PDEs) which add a component of infinite dimension to the problem. In recent literature, one method to simulate such ODEs/PDEs are physics-informed neural networks. Typically, neural networks are highly non-linear which makes their addition to optimization problems challenging. Hence, we leverage their often available Lipschitz property on a compact domain. The respective Lipschitz constants have to be computed only once and are accessible thereafter.
We present a method that, based on this property, iteratively adds cuts involving the violation of the constraints by the current incumbent and the Lipschitz constant. Hereby, the “shape” of a cut depends on the norm used. We prove the correctness of the method by showing that it either returns an optimal solution when terminating or creates a sequence with optimal accumulation points. This is complemented by a discussion about the termination in the infeasible case, as well as an analysis of the problem complexity. For the analysis, we show that the lower and upper iteration bound asymptotically coincide when the relative approximation error goes to zero. In the end, we visualize the method on a small example based on a two-dimensional non-convex optimization problem, as well as stress the necessity of having a globally optimal oracle for the sub-problems by another example.
Optimal boundary control of the isothermal semilinear Euler equation for gas dynamics on a network
(2023)
The analysis and boundary optimal control of the nonlinear transport of gas on a network of pipelines is considered. The evolution of the gas distribution on a given pipe is modeled by an isothermal semilinear compressible Euler system in one space dimension. On the network, solutions satisfying (at nodes) the Kirchhoff flux continuity conditions are shown to exist in a neighborhood of an equilibrium state. The associated nonlinear optimization problem then aims at steering such dynamics to a given target distribution by means of suitable (network) boundary controls while keeping the distribution within given (state) constraints. The existence of local optimal controls is established and a corresponding Karush-Kuhn-Tucker (KKT) stationarity system with an almost surely non-singular Lagrange multiplier is derived.
In the transition to renewable energy sources, hydrogen will potentially play an important role for energy storage. The efficient transport of this gas is possible via pipelines. An understanding of the possibilities to control the gas flow in pipelines is one of the main building blocks towards the optimal use of gas.
For the operation of gas transport networks it is important to take into account the randomness of the consumers’ demand, where often information on the probability distribution is available.
Hence in an efficient optimal control model the corresponding probability should be included and the optimal control should be such that the state that is generated by the optimal control satisfies given state constraints with large probability. We comment on the modelling of gas pipeline flow and the problems of optimal nodal control with random demand, where the aim of the optimization is to determine controls that generate states that satisfy given pressure bounds with large probability. We include the H2 norm of the control as control cost, since this avoids large pressure fluctuations which are harmful in the transport of hydrogen since they can cause
embrittlement of the pipeline metal.
We analyse the turnpike properties for a general, infinite dimensional, linear-quadratic (LQ) optimal control problem, both in the deterministic and in the stochastic case.
The novelty of the paper is twofold. Firstly, it obtains positive turnpike results for
systems that are (partially) uncontrollable. Secondly, it provides turnpike results for averaged control associated to a family of problems that depend on a random parameter, which is the first turnpike type result in the averaged controllability framework.
In this paper we analyze the turnpike phenomenon for optimal boundary control problems with a linear transport equation with source term. The convex objective function depends on
the boundary traces of the transport equation and is strictly convex with respect to the boundary control. We show an integral turnpike result for an optimal Dirichlet boundary control problem in the sense that if the time horizon goes to infinity, then the dynamic optimal control converges to
the corresponding steady state optimal control.
The novelty of this work is two-sided. On the one hand, even if turnpike results for this kind of optimal boundary control problem already exist, we present a new direct proof without using adjoint calculus that leads to sharper estimates. On the other hand we consider uncertainty in
the initial data and/or in the source term. We show that the integral turnpike result also holds considering uncertainty. Throughout the paper we use numerical examples to illustrate the results.
We consider a state estimation problem for gas pipeline flow modeled by the one-dimensional barotropic Euler equations. In order to reconstruct the system state, we construct an observer system of Luenberger type based on distributed measurements of one state variable. First, we show the existence of Lipschitz-continuous semi-global solutions of the observer system and of the original system for initial and boundary data satisfying smallness and compatibility conditions for a single pipe and for general networks. Second, based on an extension of the relative energy method we prove that the state of the observer system converges exponentially in the long time limit towards the original system state. We show this for a single pipe and for star-shaped networks.
The economics of global green ammonia trade – "Shipping Australian wind and sunshine to Germany"
(2023)
This paper contributes to understanding the transformation of global energy trade to green energy carriers, focusing on green ammonia as the foreseeable first green hydrogen carrier. We provide a comprehensive overview of today's ammonia trade and assess scaling options for the trade of green ammonia. To that aim, we develop an optimization model for the integrated assessment of the green ammonia value chain that covers all steps from green ammonia production in an exporting country, up to delivery to a harbor in an importing country. The model endogenously chooses among different technology options and determines cost minimal operation. In a case study, we apply the model to the large-scale import of ammonia from Australia to Germany in a scenario for 2030. The results show that green ammonia can reach cost parity with gray ammonia even for moderate gas prices (but not necessarily with blue ammonia) if CO2 prices are high enough. We also provide a sensitivity analysis with respect to the interest rate and other key technical and economic parameters and show that cracking ammonia to provide pure hydrogen comes at a 45 % cost markup per MWh at the destination.
Although modern societies strive towards energy systems that are entirely based on renewable energy carriers, natural gas is still one of the most important energy sources. This became even more obvious in Europe with Russia's 2022 war against the Ukraine and the resulting stop of gas supplies from Russia. Besides that it is very important to use this scarce resource efficiently. To this end, it is also of significant relevance that its transport is organized in the most efficient, i.e., cost- or energy-efficient, way. The corresponding mathematical optimization models have gained a lot of attention in the last decades in different optimization communities. These models are highly nonlinear mixed-integer problems that are constrained by algebraic constraints and partial differential equations (PDEs), which usually leads to models that are not tractable. Hence, simplifications have to be made and in this chapter, we present a commonly accepted finite-dimensional stationary model, i.e., a model in which the steady-state solutions of the PDEs are approximated with algebraic constraints. For more details about the involved PDEs and the treatment of transient descriptions we refer to Hante and Schmidt (2023). The presented finite-dimensional as well as mixed-integer nonlinear and nonconvex model is still highly challenging if it needs to be solved for real-world gas transport networks. Hence, we also review some classic solution approaches from the literature.
The optimal control of gas transport networks was and still is a very important topic for modern economies and societies. Accordingly, a lot of research has been carried out on this topic during the last years and decades. Besides mixed-integer aspects in gas transport network optimization, one of the main challenges is that a physically and technically detailed modeling of transient gas dynamics leads to theoretically and computationally highly demanding models involving nonlinear partial differential equations (PDEs). For further background on the application, historical notes and a detailed discussion of mixed-integer aspects for stationary descriptions we refer to Hante and Schmidt (2023). In this chapter, we focus on the most common modeling approaches concerning transient descriptions, point out the challenges, and summarize important contributions concerning the optimization of the most relevant control parameters for this particular class of problems.
We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel and which may result in simpler classes of optimization problems since not every block necessarily contains mixed-integer or nonlinear aspects. For achieving feasibility at the interfaces of the several blocks, we employ a tailored consensus-based penalty alternating direction method. Our numerical results show that such decomposition techniques can outperform the baseline approach of just solving the overall MINLP from scratch. However, a complete answer to the question of how to decompose MINLPs on graphs in dependence of the given model is still an open topic for future research.
We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower's problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing the load shed by solving a transport problem in the interdicted network. We develop an exact algorithm consisting of lower and upper bounding schemes that computes an optimal interdiction under the assumption that the interdicted network remains weakly connected. The main challenge consists of computing valid upper bounds for the maximal load shed, whereas lower bounds can directly be derived from the follower's problem. To compute an upper bound, we propose solving a specific bilevel problem, which is derived from restricting the flexibility of the follower when adjusting the load flow. This bilevel problem still has a nonlinear and nonconvex follower's problem, for which we then prove necessary and sufficient optimality conditions. Consequently, we obtain equivalent single-level reformulations of the specific bilevel model to compute upper bounds. Our numerical results show the applicability of this exact approach using the example of gas networks.
Contact problems arise in a variety of industrial processes, engineering and biomechanical systems. 3-D contact problem for a rigid punch with a doubly connected base bounded by the lines close to rectangles is in consideration. An analytic-numerical technique is developed for its solving. The problem contains Fredholm integral equations of the first kind, which are transformed into the second kind by means of regularization. Using the simple layer potential expansion, the kernels of the integrals are presented in the form of expansions in the powers of the polar radius. The difference between the values of the desired function at different points and the subsequent interpolation of the terms are proposed to smooth the kernels and eliminate singularities. The integral equations are reduced to one-dimension and then solved using quadrature formulas. Subsequently a punch shape is taken as a desired function, and as a minimizing functional is considered the root-mean-square deviation of the pressure distribution arising under the punch from some optimal distribution. In this case, the values of the total forces and moments applied to the punch are assumed to be given, which leads to restrictions imposed on the distributions by the equilibrium conditions. The normal displacements are determined which arising under the action of the found contact pressure on the elastic half-space. The desired punch shape is found using the simple layer potential. A solution to the problem is obtained for the punch with the doubly connected base bounded by lines close to rectangles.
We propose an algorithm which appears to be the first bridge between the fields of conditional gradient methods and abs-smooth optimization. Our nonsmooth nonconvex problem setting is motivated by machine learning, since the broad class of abs-smooth functions includes, for instance, the squared $\ell_2$-error of a neural network with ReLU or hinge Loss activation. To overcome the nonsmoothness in our problem, we propose a generalization to the traditional Frank-Wolfe gap and prove that first-order minimality is achieved when it vanishes. We derive a convergence rate for our algorithm which is identical to the smooth case. Although our algorithm necessitates the solution of a subproblem which is more challenging than the smooth case, we provide an efficient numerical method for its partial solution, and we identify several applications where our approach fully solves the subproblem. Numerical and theoretical convergence is demonstrated, yielding several conjectures.
We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt et al. (2018, 2021) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems.
We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of branching on constraints as usual, suitably chosen penalty terms are added to the objective function in order to create new subproblems in the tree. We prove the correctness of the method and present its applicability by some first numerical results.
Stochastic Optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. As the latter is often unknown, Distributionally Robust Optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy which converges at a rate of $ O(\log T / \sqrt{T})$, where $T$ is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.