Refine
Year of publication
Language
- English (1103)
- German (10)
- Multiple languages (1)
Keywords
- optimal control (27)
- stability (14)
- integer programming (11)
- Stochastic programming (9)
- finite elements (9)
- mixed integer programming (9)
- Hamiltonian matrix (8)
- finite element method (8)
- model reduction (8)
- state constraints (8)
We consider quickest flows within a new model that is based on transportation applications. In contrast to other models, it is forbidden to store flow in nodes and to cross nodes with more than one flow unit simultaneously. We work on undirected graphs. Grid graphs are of special interest because they typically arise in practice. Our model allows to close edges temporarily by time windows, and considers waiting on edges.
We solve several quickest s,t–flow problems without time windows polynomially. We prove that time windows make these problems NP–hard and even not approximable. In a multicommodity environment, all quickest flow variants are shown to be NP–hard even in grid graphs with uniform edge transit times. An alternative proof shows NP-hardness already for a small number of commodities in the case that waiting is not allowed and transit times are edge–specific. Finally, we propose two approximation algorithms in the case that time windows do not occur.
Quasistatic small-strain plasticity in the limit of small hardening and its numerical approximation
(2011)
The quasistatic rate-independent evolution of the Prager-Ziegler-type model of linearized plasticity with hardening is shown to converge to the rate-independent evolution of the Prandtl-Reuss elastic/perfectly plastic model. Based on the concept of energetic solutions we study the convergence of the solutions in the limit for hardening coefficients converging to 0 by using the abstract method of Gamma-convergence for rate-independent systems. An unconditionally convergent numerical scheme is devised and 2D and 3D numerical experiments are presented. A two-sided energy inequality is a posteriori verified to document experimental convergence rates.
Mixed-integer two-stage stochastic programs with fixed recourse matrix, random recourse costs, technology matrix, and right-hand sides are considered. Quantitative continuity properties of its optimal value and solution set are derived when the underlying probability distribution is perturbed with respect to an appropriate probability metric.
We consider the solution of a system of stochastic generalized equations (SGE) where the underlying functions are mathematical expectation of random set-valued mappings. SGE has many applications such as characterizing optimality conditions of a nonsmooth stochastic optimization problem and a stochastic equilibrium problem. We derive quantitative continuity of expected value of the set-valued mapping with respect to the variation of the underlying
probability measure in a metric space. This leads to the subsequent qualitative and quantitative stability analysis of solution set mappings of the SGE. Under some metric regularity conditions, we derive Aubin's property of the solution set mapping with respect to the change of probability measure. The established results are
applied to stability analysis of stationary points of classical one stage and two stage stochastic minimization problems, two stage stochastic mathematical programs with equilibrium constraints and stochastic programs with second order dominance constraints.
Flux coupling analysis (FCA) has become a useful tool for aiding metabolic reconstructions and guiding genetic manipulations. Originally, it was introduced for constraint-based models of metabolic networks that are based on the steady-state assumption. Recently, we have shown that the steady-state assumption can be replaced by a much weaker lattice-theoretic property related to the supports of metabolic fluxes. In this paper, we further extend our approach and delevelop an efficient algorithm for general qualitative flux coupling analysis (QFCA). We illustrate our method by thermodynamic flux coupling analysis (tFCA), which allows studying steady-state metabolic models with loop-law thermodynamic constraints. These models do not satisfy the lattice-theoretic properties required in our previous work. For a selection of genome-scale metabolic network reconstructions, we discuss both theoretically and practically, how thermodynamic constraints strengthen the coupling results that can be obtained with classical FCA.
The extent to which catastrophic weather events occur strongly depends on global climate conditions such as average sea surface temperatures (SST) or sea level pressures. Some of the factors can be predicted up to a year in advance, and should therefore be taken into account in any reasonable management of weather related risk. In this paper we first set up a risk model that integrates climate factors. The we show how variance minimizing hedging strategies explicitly depend on the factors' prediction. Our analysis is based on a detailed study of the predictable representation property on the combined Poisson and Wiener spaces. Using tools of the stochastic calculus of variations we derive a representation formula of the Clark-Ocone type. Finally, we exemplify the theory developed in a case study of US hurricane risk. We derive hedging strategies taking into account that US hurricane activity strongly depends on the SST of the Pacific Ocean.
In this paper, we propose and investigate numerical methods based on QR factorization for computing all or some Lyapunov or Sacker-Sell spectral intervals for
linear differential-algebraic equations.
Furthermore, a perturbation and error analysis for these methods is presented. We
investigate how errors in the data and in the numerical integration affect the
accuracy of the approximate spectral intervals. Although we need to integrate
numerically some differential-algebraic systems on usually very long
time-intervals, under certain assumptions, it is shown that the error of the
computed spectral intervals can be controlled by the local error of numerical
integration and the error in solving the algebraic constraint.
Some numerical examples are presented to illustrate the theoretical results.
Can OR methods help the public transport industry to break even?
How would you build a public transport system? For example, have a look at
Berlin. The BVG, Berlin's public transport company, maintains a network
of 2,423 km, operates 197 lines with 3,286 stops, using 1,554 busses, 1,391
subway cars, and 599 trams from 12 depots, and has 13,409 employees [7].
The BVG currently transports about 800 million passengers per year and
covers about 40% of the total non-pedestrian traffic volume of the city [18].
Does Berlin have a "reasonable" public transportation network? Does
the BVG run a "good" transportation system? Is it "efficient"?
These are difficult questions. In fact, politicians, transportation managers,
customers, taxpayers, etc. frequently employ judgments such as "good"
and "efficient", but nobody can give a defiition what this exactly means.
Since almost every public transportation system in the world is in the red,
the cheapest system is no public transportation at all. On the other hand,
the most convenient system for the passenger - a stop in front of every house
with direct connections to everywhere - is much too expensive. What is the
right compromise? Operations Research has no good answer either - so far.
But OR can improve aspects of public transportation significantly, as we
want to demonstrate in the following.
One-shot optimization aims at attaining feasibility and optimality simultane-
ously, especially on problems where even the linearized constraint equations
cannot be resolved economically. Here we consider a scenario where forming
and factoring the active Jacobian is out of the question, as is for example the
case when the constraints represent some discretization of the Navier Stokes
equation. Assuming that the 'user' provides us with a linearly converging solver
that gradually restores feasibility after each change in the design variables, we
derive a corresponding adjoint iteration and attach an optimization (sub)step.
The key question addressed is how the approximate reduced gradient generated
by the adjoint iteration should be preconditioned in order to achieve overall
convergence at a reasonable speed. An eigenvalue analysis yields necessary
conditions on the preconditioning matrix, which are typically not satised by
the familiar reduced Hessian. Some other projection of the Lagrangian Hessian
appears more promising and is found to work very satisfactorily on a nonlinear
test problem.
The analyzed approach is one-step in that the normal, dual and design variables
are always updated simultaneously on the basis of one function evaluation and
its adjoint. Multi-step variants are promising but remain to be investigated.
Markov (state) models (MSMs) have attracted a lot of interest recently as they (1) can probe
long-term molecular kinetics based on short-time simulations, (2) offer a way to analyze great
amounts of simulation data with relatively little subjectivity of the analyst, (3) provide insight into
microscopic quantities such as the ensemble of transition pathways, and (4) allow simulation data
to be reconciled with measurement data in a rigorous and explicit way. Here we sketch our current
perspective of Markov models and explain in short their theoretical basis and assumptions. We
describe transition path theory which allows the entire ensemble of protein folding pathways to be
investigated and that combines naturally with Markov models. Experimental observations can be
naturally linked to Markov models with the dynamical fingerprint theory, by which experimentally
observable timescales can be equipped with an understanding of the structural rearrangement
processes that take place at these timescales. The concepts of this paper are illustrated by a
simple kinetic model of protein folding.
Discrete-state Markov (or master equation) models provide a useful simplified representation for
characterizing the long-time statistical evolution of biomolecules in a manner that allows direct
comparison with experiments as well as the elucidation of mechanistic pathways for an inherently
stochastic process. A vital part of meaningful comparison with experiment is the characterization of
the statistical uncertainty in the predicted experimental measurement, which may take the form of
an equilibrium measurement of some spectroscopic signal, the time-evolution of this signal following
a perturbation, or the observation of some statistic (such as the correlation function) of the equilib-
rium dynamics of a single molecule. Without meaningful error bars (which arise due to the finite
quantity of data used to construct the model), there is no way to determine whether the deviations
between model and experiment are statistically meaningful. Previous work has demonstrated that
a Bayesian method that enforces microscopic reversibility can be used to characterize the correlated
uncertainties in state-to-state transition probabilities (and functions thereof) for a model inferred from
molecular simulation data. Here, we extend this approach to include the uncertainty in observables
that are functions of molecular conformation (such as surrogate spectroscopic signals) characteriz-
ing each state, permitting the full statistical uncertainty in computed spectroscopic experiments to be
assessed. We test the approach in a simple model system to demonstrate that the computed uncer-
tainties provide a useful indictor of statistical variation, and then apply it to the computation of the
fluorescence autocorrelation function measured for a dye-labeled peptide previously studied by both
experiment and simulation.
Large-scale stochastic models are relevant in many different fields such as com- putational biology, finance, social sciences, communication and traffic networks. In order to both efficiently simulate and analyze such models and to understand the essential properties of the sys- tem, it is desirable to have model reduction techniques that much reduce the dimensionality of the model while at the same time preserving the system’s essential dynamical properties. In this paper, a general model reduction technique for the class of discrete space and time Hidden Markov Models is presented, thereby also including the more special class discrete Markov Chains. The method is illustrated on some model applications.
Primal-dual linear Monte Carlo algorithm for multiple stopping - An application to flexible caps
(2012)
In this paper we consider the valuation of Bermudan callable derivatives with
multiple exercise rights. We present in this context a new primal-dual linear
Monte Carlo algorithm that allows for ecient simulation of lower and upper price
bounds without using nested simulations (hence the terminology). The algorithm
is essentially an extension of a primal{dual Monte Carlo algorithm for standard
Bermudan options proposed in Schoenmakers et al. (2011), to the case of multiple
exercise rights. In particular, the algorithm constructs upwardly a system of dual
martingales to be plugged into the dual representation of Schoenmakers (2010).
At each level the respective martingale is constructed via a backward regression
procedure starting at the last exercise date. The thus constructed martingales are
nally used to compute an upper price bound. At the same time, the algorithm
also provides approximate continuation functions which may be used to construct
a price lower bound. The algorithm is applied to the pricing of
exible caps
in a Hull and White (1990) model setup. The simple model choice allows for
comparison of the computed price bounds with the exact price which is obtained
by means of a trinomial tree implementation. As a result, we obtain tight price
bounds for the considered application. Moreover, the algorithm is generically
designed for multi-dimensional problems and is tractable to implement.
Primal heuristics are an important component of state-of-the-art codes for mixed integer nonlinear programming (MINLP). In this article we give a compact overview of primal heuristics for MINLP that have been suggested in the literature of recent years. We sketch the fundamental concepts of different classes of heuristics and discuss specific implementations. A brief computational experiment shows that primal heuristics play a key role in achieving feasibility and finding good primal bounds within a global MINLP solver.
We present two approximation methods for pricing of CMS spread options in Libor market models. Both approaches are based on approximating the underlying swap rates with lognormal processes under suitable measures. The first method is derived straightforwardly from the Libor market model. The second one uses a convexity adjustment technique under a linear swap model assumption. A numerical study demonstrates that both methods provide satisfactory approximations of spread option prices and can be used for calibration of a Libor market model to the CMS spread option market.
We show that pricing a big class of relevant options by hedging
and no-arbitrage can be extended beyond semimartingale models. To
this end we construct a subclass of self-financing portfolios that
contains hedges for these options, but does not contain arbitrage
opportunities, even if the stock price process is a
non-semimartingale of some special type.
Moreover, we show that the option prices depend
essentially only on a path property of the stock price process,
viz. on the quadratic variation. As a consequence, we can
incorporate many stylized facts to a pricing model without
changing the option prices.
This paper is concerned with the study of insurance related derivatives on financial markets that are based on non-tradable underlyings, but are correlated with tradable assets. We calculate exponential utility-based indifference prices, and corresponding derivative hedges. We use the fact that they can be represented in terms of solutions of forward-backward stochastic differential equations (FBSDE) with quadratic growth generators. We derive the Markov property of such FBSDE and generalize results on the differentiability relative to the initial value of their forward components. In this case the optimal hedge can be represented by the price gradient multiplied with the correlation coefficient. This way we obtain a generalization of the classical ‘delta hedge’ in complete markets.
Expected suprema of a function f observed along the paths of a nice Markov process define an excessive function, and in
fact a potential if f vanishes at the boundary. Conversely, we show under mild regularity conditions that any
potential admits a representation in terms of expected suprema. Moreover, we identify the maximal and the minimal
representing function in terms of probabilistic potential theory. Our results are motivated by the work of El Karoui and
Meziou on the max-plus decomposition of supermartingales, and they provide a singular analogue to
the non-linear Riesz representation in El Karoui and Föllmer.
We propose a model reduction method for positive systems that ensures the positivity of the reduced-order model. In the standard as well as in the descriptor case, for continuous-time and discrete-time systems, our approach is based on constructing diagonal solutions of Lyapunov inequalities. These are linear matrix inequalities (LMIs), which are shown to be feasible. Positivity and stability are preserved and an error bound in the $\mathcal{H}_\infty$-norm is provided.