Refine
Year of publication
- 2012 (153) (remove)
Keywords
- Robust Optimization (4)
- primal heuristic (4)
- Large Neighborhood Search (3)
- Navier-Stokes equations (3)
- molecular dynamics (3)
- stochastic programming (3)
- ANOVA decomposition (2)
- FPTAS (2)
- Knapsack Problem (2)
- Markov models (2)
Optimal dual martingales, their analysis and application to new algorithms for Bermudan products
(2012)
In this paper we introduce and study the concept of optimal and surely
optimal dual martingales in the context of dual valuation of Bermudan
options, and outline the development of new algorithms in this context.
We provide a characterization theorem, a theorem which gives conditions
for a martingale to be surely optimal, and a stability theorem concerning martingales which are near to be surely optimal in a sense. Guided
by these results we develop a framework of backward algorithms for constructing such a martingale. In turn this martingale may then be utilized
for computing an upper bound of the Bermudan product. The methodology is pure dual in the sense that it doesn't require certain (input)
approximations to the Snell envelope.
In an Ito-Levy environment we outline a particular regression based
backward algorithm which allows for computing dual upper bounds with-
out nested Monte Carlo simulation. Moreover, as a by-product this algorithm also provides approximations to the continuation values of the
product, which in turn determine a stopping policy. Hence, we may obtain lower bounds at the same time.
In a first numerical study we demonstrate a backward dual regression algorithm in a Wiener environment that is easy to implement and
is regarding accuracy comparable with the method of Belomestny et. al.
(2009).
The LIBOR market model is very popular for pricing inter-
est rate derivatives, but is known to have several pitfalls. In addition, if
the model is driven by a jump process, then the complexity of the drift
term is growing exponentially fast (as a function of the tenor length). In
this work, we consider a Levy-driven LIBOR model and aim at developing accurate and efficient log-Levy approximations for the dynamics of
the rates. The approximations are based on truncation of the drift term
and Picard approximation of suitable processes. Numerical experiments
for FRAs, caps and swaptions show that the approximations perform
very well. In addition, we also consider the log-Levy approximation of
annuities, which offers good approximations for high volatility regimes.
With an emphasis on generators with quadratic growth in the control variable we consider
measure solutions of BSDE, a solution concept corresponding to the notion of risk neutral
measure in mathematical finance. In terms of measure solutions, solving a BSDE reduces
to martingale representation with respect to an underlying filtration. Measure solutions
related to measures equivalent to the historical one provide classical solutions. We derive
the existence of measure solutions in scenarios in which the generating functions are just
continuous, of at most linear growth in the control variable (corresponding to generators of
at most quadratic growth in the usual sense), and with a random bound in the time parameter
whose stochastic integral is a BMO martingale. Our main tools include a stability property
of sequences of measure solutions, for which a limiting solution is obtained by means of the
weak convergence of measures.
Existence result for a class of generalized standard materials with thermomechanical coupling
(2012)
This paper deals with the study of a three-dimensional model of thermomechanical coupling for viscous solids exhibiting hysteresis effects. This model is written in accordance with the formalism of generalized standard materials. It is composed by the momentum equilibrium equation combined with the flow rule, which describes some stress-strain dependance, and the heat-transfer equation. An existence result for this thermodynamically consistent problem is obtained by using a fixed-point argument and some qualitative properties of the solutions are established.
While studies of protein-ligand association have mostly focused on the native complex and its
stability (binding affinity), relatively little attention has been paid on the association process
that precedes the formation of the complex. Here we review approaches to study the kinet-
ics of association and association mechanisms, i.e. the probability distribution of association
pathways. Selected methods are described that allow these properties to be calculated quan-
titatively from simulation models. We summarize some applications of these methods and
finally propose a model mechanism by which proteins may efficiently screen potential ligands
for those that can be natively bound.
Protein-ligand interactions are essential for nearly all biological processes, and yet the bio-
physical mechanism that enables potential binding partners to associate before specific binding
occurs remains poorly understood. Fundamental questions include which factors influence the
formation of protein-ligand encounter complexes, and whether designated association path-
ways exist. In this article we introduce a computational approach to systematically analyze
the complete ensemble of association pathways and to thus investigate these questions. This
approach is employed here to study the binding of a phosphate ion to the Escherichia coli
Phosphate Binding Protein. Various mutants of the protein are considered and their effects
on binding free energy profiles, association rates and association pathway distributions are
quantified. The results reveal the existence of two anion attractors, i.e. regions that initially
attract negatively charged particles and allow them to be efficiently screened for phosphate
which is specifically bound subsequently. Point mutations that affect the charge on these
attractors modulate their attraction strength and speed up association to a factor of 10 of
the diffusion limit and thus change the association pathways of the phosphate ligand. It is
demonstrated that a phosphate that pre-binds to such an attractor neutralizes its attraction
effect to the environment, making the simultaneous association of a second phosphate ion
unlikely. Our study suggests ways how structural properties can be used to tune molecular
association kinetics so as to optimize the efficiency of binding, and highlights the importance
of kinetic properties.
Dynamical fingerprints of macromolecules obtained from experiments often seem to indicate two- or
three state kinetics while simulations typically reveal a more complex picture. Markov state models of
molecular conformational dynamics can be used to predict these dynamical fingerprints and to reconcile
experiment with simulation. This is illustrated on two model systems: a one-dimensional energy surface
and a four-state model of a protein folding equilibrium. We show that (i) there might be no process
which corresponds to our notion of folding, (ii) often the experiment will be insensitive to some of the
processes present in the system, (iii) with a suitable combination the observable and initial conditions in
a relaxation experiment one can selectively measure specific processes. Furthermore, our method can be
used to design experiments such that specific processes appear with large amplitudes. We demonstrate
that for a fluorescence quenching experiment of the MR121-G9-W peptide.
Dynamical averages based on functionals of dynamical trajectories, such as time-correlation func-
tions, play an important role in determining kinetic or transport properties of matter. At temperatures
of interest, the expectations of these quantities are often dominated by contributions from rare events,
making the precise calculation of these quantities by molecular dynamics simulation difficult. Here,
we present a reweighting method for combining simulations from multiple temperatures (or from
simulated or parallel tempering simulations) to compute an optimal estimate of the dynamical prop-
erties at the temperature of interest without the need to invoke an approximate kinetic model (such as
the Arrhenius law). Continuous and differentiable estimates of these expectations at any temperature
in the sampled range can also be computed, along with an assessment of the associated statistical
uncertainty. For rare events, aggregating data from multiple temperatures can produce an estimate
of the desired precision at greatly reduced computational cost compared with simulations conducted
at a single temperature. Here, we describe use of the method for the canonical (NVT) ensemble us-
ing four common models of dynamics (canonical distribution of Hamiltonian trajectories, Andersen
thermostatting, Langevin, and overdamped Langevin or Brownian dynamics), but it can be applied to
any thermodynamic ensemble provided the ratio of path probabilities at different temperatures can be
computed. To illustrate the method, we compute a time-correlation function for solvated terminally-
blocked alanine peptide across a range of temperatures using trajectories harvested using a modified
parallel tempering protocol.
Markov state models of molecular kinetics (MSMs), in which the long-time statistical dynamics
of a molecule is approximated by a Markov chain on a discrete partition of configuration space, have
seen widespread use in recent years. This approach has many appealing characteristics compared
to straightforward molecular dynamics simulation and analysis, including the potential to mitigate
the sampling problem by extracting long-time kinetic information from short trajectories and the
ability to straightforwardly calculate expectation values and statistical uncertainties of various
stationary and dynamical molecular observables. In this article, we summarize the current state of
the art in generation and validation of MSMs and give some important new results. We describe
an upper bound for the approximation error made by modeling molecular dynamics with an MSM
and we show that this error can be made arbitrarily small with surprisingly little effort. In contrast
to previous practice, it becomes clear that the best MSM is not obtained by the most metastable
discretization, but the MSM can be much improved if non-metastable states are introduced near
the transition states. Moreover, we show that it is not necessary to resolve all slow processes
by the state space partitioning, but individual dynamical processes of interest can be resolved
separately. We also present an efficient estimator for reversible transition matrices and a robust
test to validate that an MSM reproduces the kinetics of the molecular dynamics data.
Markov State Models (MSMs) have become the tool of choice to analyze large amounts of molec-
ular dynamics data by approximating them as a Markov jump process between suitably predefined
states. Here we investigate ”Core Set MSMs”, a new type of MSMs that builds on metastable core
sets acting as milestones for tracing the rare event kinetics. We present a thorough analysis of Core
Set MSMs based on the existing milestoning framework, Bayesian estimation methods and Transi-
tion Path Theory (TPT). As a result, Core Set MSMs can now be used to extract phenomenological
rate constants between the metastable sets of the system and to approximate the evolution of certain
key observables. The performance of Core Set MSMs in comparison to standard MSMs is analyzed
and illustrated on a model potential and the torsion angle dynamics of Alanine dipeptide.
Resolving the apparent gap in complexity between
simulated and measured kinetics of biomolecules
(2012)
Molecular simulations of biomolecules often reveal a complex picture of the their kinetics,
whereas kinetic experiments typically seem to indicate considerably simpler two- or three-state
kinetics. Markov state models (MSM) provide a tool to link between simulation and experi-
ment, and to resolve this apparent contradiction.
In many fields of physics, chemistry and biology the characterization of dynamical processes
between states or species is of fundamental interest. The central mathematical function in such sit-
uations is the committor probability - a generalized reaction coordinate that measures the progress
of the process of interest as the probability of proceeding towards the target state rather than re-
lapsing to the source state. Here, we present methodology for the efficient computation of com-
mittor probabilities for large-scale systems, such as, for example simuations of biomolecular fold-
ing. A method is derived for computing the committor for discrete state spaces using eigenvectors
with expressions for the sensitivity and a Bayesian error model for the committor. The concepts
are illustrated on two examples of diffusive dynamics with a very large number of states: a two-
dimensional model potential with three minima, and a three-dimensional model representing
protein-ligand binding. The method can finally be used to compute committor probabilities in-
cluding error estimations for medium and large system sizes allowing access to the apparatus of
transition path theory and its applications.
Diffusion processes are relevant for a variety of phenomena in the natural sciences, including
diffusion of cells or biomolecules within cells, diffusion of molecules on a membrane or surface,
diffusion of a molecular conformation within a complex energy landscape. Many experimental
tools exist now to track such diffusive motions in single cells or molecules, including high-resolution
light microscopy, optical tweezers, fluorescence quenching, and Förster resonance energy transfer
(FRET). Experimental observations are most often indirect and incomplete: (1) They do not
directly reveal the potential or diffusion constants that govern the diffusion process, (2) they have
limited time and space resolution, and (3) the highest-resolution experiments do not track the
motion directly but rather probe it stochastically by recording single events, such as photons,
whose properties depend on the state of the system under investigation.
Here, we propose a general Bayesian framework to model diffusion processes with nonlinear
drift based on incomplete observations as generated by various types of experiments. A maximum
penalized likelihood estimator is given as well as a Gibbs sampling method that allows to estimate
the trajectories that have caused the measurement, the nonlinear drift or potential function and
the noise or diffusion matrices, as well as uncertainty estimates of these properties. The approach
is illustrated on numerical simulations of FRET experiments where it is shown that trajectories,
potentials and diffusion constants can be efficiently and reliably estimated even in cases with little
statistics or non-equilibrium measurement conditions.
Logical modeling of biological regulatory networks gives rise to a representation of the system's dynamics as a so-called state transition graph. Analysis of such a graph in its entirety allows for a comprehensive understanding of the functionalities and behavior of the modeled system. However, the size of the vertex set of the graph is exponential in the number of the network components making analysis costly, motivating development of reduction methods. In this paper, we present results allowing for a complete description of an asynchronous state transition graph of a Thomas network solely based on the analysis of the subgraph induced by certain extremal states. Utilizing this notion, we compare the behavior of a simple multi-valued network and a corresponding Boolean network and analyze the conservation of dynamical properties between them. Understanding the relation between such coarser and finer models is a necessary step towards meaningful network reduction as well as model refinement methods.
We consider convex optimization problems with $k$th order stochastic dominance constraints for $k\ge 2$. We discuss distances of random variables that are relevant for the dominance relation and establish quantitative stability results for optimal values and solution sets in terms of a suitably selected probability metrics.Moreover, we provide conditions ensuring that the optimal value function is Hadamard directionally differentiable. Finally, we discuss some implications of the results for empirical (Monte Carlo,
sample average) approximations of dominance constrained optimization models.
Piecewise linear convex functions arise as integrands in stochastic programs. They are Lipschitz continuous on their domain, but do not belong to tensor product Sobolev spaces. Motivated by applying Quasi-Monte Carlo methods we show that all terms of their ANOVA decomposition, except the one of highest order, are smooth if the underlying densities are smooth and certain geometric condition is satisfied. The latter condition is generically satisfied in the normal case.
We consider discretizations for reaction-diffusion systems with nonlinear
diffusion in two space dimensions. The applied model allows to handle heterogeneous
materials and uses the chemical potentials of the involved species as primary variables.
We propose an implicit Voronoi finite volume discretization on regular Delaunay
meshes that allows to prove uniform, mesh-independent global upper and lower L1
bounds for the chemical potentials. These bounds provide the main step for a convergence
analysis for the full discretized nonlinear evolution problem. The fundamental
ideas are energy estimates, a discrete Moser iteration and the use of discrete
Gagliardo-Nirenberg inequalities. For the proof of the Gagliardo-Nirenberg inequalities
we exploit that the discrete Voronoi finite volume gradient norm in 2d coincides
with the gradient norm of continuous piecewise linear finite elements.
Recent research has shown that
in some practically relevant situations like multi-physics flows[11]
divergence-free mixed finite elements may have a significantly
smaller discretization error than standard non-divergence-free
mixed finite elements. In order to judge the overall performance of
divergence-free mixed finite elements, we
investigate linear solvers for the saddle point linear systems arising in $((P_k)^d,P_{k-1}^{disc})$ Scott-Vogelius finite element implementations of the incompressible Navier-Stokes equations. We investigate both direct and iterative solver methods.
Due to discontinuous pressure elements in the case of Scott-Vogelius elements, considerably more solver strategies seem to deliver promising results than in the case of standard mixed finite elements like
Taylor-Hood elements. For direct methods, we extend recent preliminary work using sparse banded solvers on the penalty method formulation to finer meshes, and discuss extensions. For iterative methods, we test augmented Lagrangian and H-LU preconditioners with GMRES, on both full and statically condensed systems.
Several numerical experiments are provided that show these classes of solvers are well suited for use with Scott-Vogelius elements, and could deliver an interesting overall performance in several applications.
Mathematical modeling often helps to provide a systems perspective on gene regulatory networks. In particular, qualitative approaches are useful when detailed kinetic information is lacking. Multiple methods have been developed that implement qualitative information in different ways, e.g., in purely discrete or hybrid discrete/continuous models. In this paper, we compare the discrete asynchronous logical modeling formalism for gene regulatory networks due to R. Thomas with piecewise affine differential equation models.
We provide a local characterization of the qualitative dynamics of a piecewise affine differential equation model using the discrete dynamics of a corresponding Thomas model. Based on this result, we investigate the consistency of higher-level dynamical properties such as attractor characteristics and reachability. We show that although the two approaches are based on equivalent information, the resulting qualitative dynamics are different. In particular, the dynamics of the piecewise affine differential equation model is not a simple refinement of the dynamics of the Thomas model.
The authors propose a recycling MINRES scheme for a solution of subsequent self-adjoint linear systems as appearing, for example, in the Newton process for solving nonlinear equations. Ritz vectors are automatically extracted from one MINRES run and then used for self-adjoint deflation in the next. The method is designed to work with a preconditioner and arbitrary inner products. Numerical experiments with nonlinear Schrödinger equations indicate a substantial decrease in computation time when recycling is used.
We formulate the static mechanical coupling of a geometrically exact Cosserat rod
to a nonlinearly elastic continuum. In this setting, appropriate coupling conditions have
to connect a one-dimensional model with director variables to a three-dimensional
model without directors.
Two alternative coupling conditions are proposed,
which correspond to two different configuration trace spaces.
For both we show existence of solutions of the coupled problems, using the direct
method of the calculus of variations. From the first-order optimality conditions
we also derive the corresponding conditions for the dual variables. These are
then interpreted in mechanical terms.
A novel Finite Element Method (FEM) for the computational simulation in particle reinforced composite materials with many inclusions is presented. It is based on an adapted mesh which consists of triangles and parametric quadrilaterals in 2D. The number of elements and, hence, the number of degrees of freedom are proportional to the number of inclusions. The error of the method is independent of the distance of the neighboring inclusions. While being related to network methods, the approach can tackle more general settings. We present an efficient residual a posteriori error estimator which enables to compute reliable upper and lower error bounds. Several numerical examples illustrate the performance of the method and the error estimator. Moreover, it is demonstrated that the assumption of a lattice structure of inclusions can easily lead to incorrect predictions about material properties.
This paper discusses adaptive finite element methods (AFEMs) for the solution of elliptic eigenvalue problems associated with partial differential operators. An adaptive method based on nodal-patch refinement leads to an asymptotic error reduction property for the computed sequence of simple eigenvalues and eigenfunctions. This justifies the use of the proven saturation property for a class of reliable and efficient hierarchical a posteriori error estimators. Numerical experiments confirm that the saturation property is present even for very coarse meshes for many examples; in other cases the smallness assumption on the initial mesh may be severe.
The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.
In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.
Mathematical modeling of Czochralski type growth processes for semiconductor bulk single crystals
(2012)
This paper deals with the mathematical modeling and simulation of
crystal growth processes by the so-called Czochralski method and related methods,
which are important industrial processes
to grow large
bulk single crystals of semiconductor materials such as, e.g., gallium arsenide
(GaAs) or silicon (Si) from the melt.
In particular, we investigate a recently developed
technology in which traveling magnetic fields are applied in order to
control
the behavior of the turbulent melt flow. Since numerous different physical effects
like electromagnetic fields, turbulent melt flows, high temperatures, heat transfer via
radiation, etc., play an important role in the process, the corresponding mathematical
model leads to an extremely difficult system of initial-boundary value problems for
nonlinearly coupled partial differential equations. In this paper, we describe a mathematical
model that is under use for the simulation of real-life growth scenarios, and we give an overview
of mathematical results and numerical simulations that have been obtained for it in recent years.
Rapid Branching
(2012)
We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning.
This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers.
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.
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.
Optimal Identification of Semi-Rigid Domains in Macromolecules from Molecular Dynamics Simulation
(2012)
Biological function relies on the fact that biomolecules can switch between different conformations and aggregation states.
Such transitions involve a rearrangement of parts of the biomolecules involved that act as dynamic domains. The reliable
identification of such domains is thus a key problem in biophysics. In this work we present a method to identify semi-rigid
domains based on dynamical data that can be obtained from molecular dynamics simulations or experiments. To this end
the average inter-atomic distance-deviations are computed. The resulting matrix is then clustered by a constrained
quadratic optimization problem. The reliability and performance of the method are demonstrated for two artificial peptides.
Furthermore we correlate the mechanical properties with biological malfunction in three variants of amyloidogenic
transthyretin protein, where the method reveals that a pathological mutation destabilizes the natural dimer structure of the
protein. Finally the method is used to identify functional domains of the GroEL-GroES chaperone, thus illustrating the
efficiency of the method for large biomolecular machines.
In this paper, we present a Gaussian Markov random field (GMRF) model for the transition
matrices (TMs) of Markov chains (MCs) by assuming the existence of a neighborhood relationship
between states, and develop the maximum a posteriori (MAP) estimators under different obser-
vation conditions. Unlike earlier work on TM estimation, our method can make full use of the
similarity between different states to improve the estimated accuracy, and the estimator can be
performed very efficiently by solving a convex programming problem. In addition, we discuss the
parameter choice of the proposed model, and introduce a Monte Carlo cross validation (MCCV)
method. The numerical simulations of a diffusion process are employed to show the effectiveness
of the proposed models and algorithms.
We characterize the Smith form of skew-symmetric matrix polynomials
over an arbitrary field $\F$,
showing that all elementary divisors occur with even multiplicity.
Restricting the class of equivalence transformations to unimodular congruences,
a Smith-like skew-symmetric canonical form
for skew-symmetric matrix polynomials is also obtained.
These results are used to analyze the eigenvalue and elementary divisor structure
of matrices expressible as products of two skew-symmetric matrices,
as well as the existence of structured linearizations
for skew-symmetric matrix polynomials.
By contrast with other classes of structured matrix polynomials
(e.g., alternating or palindromic polynomials),
every regular skew-symmetric matrix polynomial
is shown to have a structured strong linearization.
While there are singular skew-symmetric polynomials of even degree
for which a structured linearization is impossible,
for each odd degree we develop a skew-symmetric companion form
that uniformly provides a structured linearization
for every regular and singular skew-symmetric polynomial
of that degree.
Finally, the results are applied to the construction of minimal
symmetric factorizations of skew-symmetric rational matrices.
Flows over time generalize classical ``static'' network flows by introducing a temporal dimension. They can thus be used to model non-instantaneous travel times for flow and variation of flow values over time, both of which are crucial characteristics in many real-world routing problems. There exist two different models of flows over time with respect to flow conservation: one where flow might be stored temporarily at intermediate nodes and a stricter model where flow entering an intermediate node must instantaneously progress to the next arc. While the first model is in general easier to handle, the second model is often more realistic since in applications like, e.\,g., road traffic, storage of flow at intermediate nodes is undesired or even prohibited. The main contribution of this paper is a fully polynomial time approximation scheme (FPTAS) for (min-cost) multi-commodity flows over time without intermediate storage. This improves upon the best previously known $(2+\varepsilon)$-approximation algorithm presented 10 years ago by Fleischer and Skutella (IPCO~2002).
Some mathematical problems related to the 2nd order optimal shape of a crystallization interface
(2012)
We consider the problem to optimize the stationary temperature distribution and the equilibrium shape of the solid-liquid interface in a two-phase system subject to a temperature gradient. The interface satisfies the minimization principle of the free energy, while the temperature is solving the heat equation with a radiation boundary conditions at the outer wall. Under the condition that the temperature gradient is uniformly negative in the direction of crystallization, the interface is expected to have a global graph representation. We reformulate this condition as a pointwise constraint on the gradient of the state, and we derive the first order optimality system for a class of objective functionals that account for the second surface derivatives, and for the surface temperature gradient.
We develop a model for the dynamic evolution of default-free and defaultable interest rates in a LIBOR framework. Utilizing the class of affine processes, this model produces positive LIBOR rates and spreads, while the dynamics are analytically tractable under defaultable forward measures. This leads to explicit formulas for CDS spreads, while semi-analytical formulas are derived for other credit derivatives. Finally, we give an application to counterparty risk.
A robust implementation of a Dupire type local volatility model is an important issue for every option trading floor. In the present note we provide new analytic insights into the asymptotic behavior of local volatility in the wings. We present a general approximation formula and specialize it to the Heston model, showing that local variance is linear in the wings. This further justifies the choice of certain local volatility parametrizations.
Density expansions for hypoelliptic diffusions (X1^,...,X^d) are revisited. In particular, we are interested in density expansions of the projection (X^1_T,...,X^l_T) at time $T>0$, with $l \le d$. Global conditions are found which replace the well-known ”not-in-cutlocus” condition known from heat-kernel asymptotics; cf. G. Ben Arous (88). Our small noise expansion allows for a ”second order” exponential factor. Applications include tail and implied volatility asymptotics in some correlated stochastic volatility models; in particular, we solve a problem left open by A. Gulisashvili and E.M. Stein (2009).
Cubature methods, a powerful alternative to Monte Carlo due to Kusuoka [Adv. Math. Econ. 6, 69–83, 2004] and Lyons–Victoir [Proc. R. Soc. Lond. Ser. A 460, 169–198, 2004], involve the solution to numerous auxiliary ordinary differential equations. With focus on the Ninomiya-Victoir algorithm [Appl. Math. Fin. 15, 107–121, 2008], which corresponds to a concrete level 5 cubature method, we study some parametric diffusion models motivated from financial applications, and exhibit structural conditions under which all involved ODEs can be solved explicitly and efficiently. We then enlarge the class of models for which this technique applies, by introducing a (model-dependent) variation of the Ninomiya-Victoir method. Our method remains easy to implement; numerical examples illustrate the savings in computation time.
A mathematical model for instationary magnetization
processes is considered, where the underlying spatial domain
includes electrically conducting and nonconducting regions. The
model accounts for the magnetic induction law that couples the given
electrical voltage with the induced electrical current in the
induction coil. By a theorem of Showalter on degenerate parabolic
equations, theorems on existence, uniqueness, and regularity of the
solution to the associated Maxwell integrodifferential system are
proved.
Scalable Frames
(2012)
Tight frames can be characterized as those frames which possess optimal numerical stability properties. In this paper, we consider the question of modifying a general frame to generate a tight frame by rescaling its frame vectors; a process which can also be regarded as perfect preconditioning of a frame by a diagonal operator. A frame is called scalable, if such a diagonal operator exists. We derive various characterizations of scalable frames, thereby including the infinite-dimensional situation. Finally, we provide a geometric interpretation of scalability in terms of conical surfaces.
In this paper, we study the influence of technology, traffic properties and price trends on optimized
design of a reference IP-over-WDM network with rich underlying fiber topology. In each network node,
we investigate the optimal degree of traffic switching in an optical (lambda) domain versus an electrical
(packet) domain, also known as measure of \emph{node transparency}. This measure is studied in connection to changes in
traffic volume,
demand affinity, optical circuit speeds and equipment cost. By applying variable design constraints,
we assess the relative roles of the two distinct equipment groups, IP routers and optical
cross-connects, with respect to resulting changes in cost-sensitive network architectures
Persistence of rogue waves in extended nonlinear Schrödinger equations: Integrable Sasa-Satsuma case
(2012)
We present the lowest order rogue wave solution of the Sasa-Satsuma equation (SSE) which is one of the integrable extensions of the nonlinear Schrödinger equation (NLSE). In contrast to the Peregrine solution of the NLSE, it is significantly more involved and contains polynomials of fourth order rather than second order in the corresponding expressions. The correct limiting case of Peregrine solution appears when the extension parameter of the SSE is reduced to zero.
RENS – the optimal rounding
(2012)
This article introduces RENS, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programming (MINLP) that uses a sub-MINLP to explore the set of feasible roundings of an optimal solution x' of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables x_j with x'_j in Z and bounding the remaining integer variables to x_j in {floor(x'_j), ceil(x'_j)}. We describe two different applications of RENS: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver.
We use the former to compare different kinds of relaxations and the impact of cutting planes on the roundability of the corresponding optimal solutions. We further utilize RENS to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework SCIP. Finally, we study the impact of RENS when it is applied as a primal heuristic inside SCIP.
All experiments were performed on three publically available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLPs, using solely software which is available in source code.
It turns out that for these problem classes 60% to 70% of the instances have roundable relaxation optima and that the success rate of RENS does not depend on the percentage of fractional variables. Last but not least, RENS applied as primal heuristic complements nicely with existing root node heuristics in SCIP and improves the overall performance.
We present a time-dependent finite element model of the human knee joint of full 3D geometric complexity together with advanced numerical algorithms needed for its simulation. The model comprises bones, cartilage and the major ligaments, while patella and menisci are still missing. Bones are modeled by linear elastic materials, cartilage by linear viscoelastic materials, and ligaments by one-dimensional nonlinear Cosserat rods. In order to capture the dynamical contact problems correctly, we solve the full PDEs of elasticity with strict contact inequalities. The spatio--temporal discretization follows a time layers approach (first time, then space discretization). For the time discretization of the elastic and viscoelastic parts we use a new contact-stabilized Newmark method, while for the Cosserat rods we choose an energy--momentum method. For the space discretization, we use linear finite elements for the elastic and viscoelastic parts and novel geodesic finite elements for the Cosserat rods. The coupled system is solved by a Dirichlet--Neumann method. The large algebraic systems of the bone--cartilage contact problems are solved efficiently by the truncated non-smooth Newton multigrid method.
We consider risk-averse formulations of multistage stochastic linear programs. For these formulations, based on convex combinations of spectral risk measures, risk-averse dynamic programming equations can be written. As a result, the Stochastic Dual Dynamic Programming
(SDDP) algorithm can be used to obtain approximations of
the corresponding risk-averse recourse functions. This allows us to define a risk-averse nonanticipative feasible policy for thestochastic linear program. Formulas for the cuts that approximate the recourse functions are given.
Quasi-Monte Carlo algorithms are studied for designing discrete approximations of two-stage linear stochastic programs. Their integrands are piecewise linear, but neither smooth nor of bounded variation in the sense of Hardy and Krause. We show that under some weak geometric condition on the two-stage model all terms of their
ANOVA decomposition, except the one of highest order, are smooth and, hence, certain Quasi-Monte Carlo algorithms may achieve the optimal rate of convergence $O(n^{-1+\delta})$ with $\delta\in(0,\frac{1}{2})$ and a constant not depending on the dimension if the integrands belong to weighted tensor product Sobolev spaces with properly selected weights. The geometric condition is generically (i.e., almost everywhere) satisfied if the underlying distribution is normal. We also discuss sensitivity
indices and efficient dimensions of two-stage integrands, and suggest a dimension reduction heuristic for such integrands.
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.
Hybrid systems are often used to describe many complex dynamic phenomena by combining multiple modes of
dynamics into whole systems. In this paper, we present a flat Dirichlet process switching (FDPS) model that defines
a prior on mode switching dynamics of hybrid systems. Compared with the classical Markovian jump system (MJS)
models, the FDPS model is nonparametric and can be applied to the hybrid systems with an unbounded number of
potential modes. On the other hand, the probability structure of the new model is simpler and more flexible than the
recently proposed hierarchical Dirichlet process (HDP) based MJS. Furthermore, we develop a Markov chain Monte
Carlo (MCMC) method for estimating the states of hybrid systems with FDPS prior. And the numerical simulations
of a hybrid system in different conditions are employed to show the effectiveness of the proposed approach.
Actin is a major structural protein of the eukaryotic cytoskeleton and enables cell motility.
Here, we present a model of the actin filament (F-actin) that incorporates the global structure
of the recently published model by Oda et al. but also conserves internal stereochemistry. A
comparison is made using molecular dynamics simulation of the model with other recent F-
actin models. A number of structural determents such as the protomer propeller angle, the
number of hydrogen bonds and the structural variation among the protomers are analyzed.
The MD comparison is found to reflect the evolution in quality of actin models over the last
six years. In addition, simulations of the model are carried out in states with both ADP or
ATP bound and local hydrogen-bonding differences characterized. The results point to the
significance of a direct interaction of Gln137 with ATP for activation of ATPase activity after
the G-to-F-actin transition.
We consider a shape implant design problem that arises in the context of facial surgery. We introduce a reformulation as an optimal control problem, where the control acts as a boundary force. The state is modelled as a minimizer of a polyconvex hyperelastic energy functional. We show existence of optimal solutions and derive - on a formal level - first order optimality conditions. Finally, preliminary numerical results are presented.
The hypergraph assignment problem (HAP) is the generalization of assignments
from directed graphs to directed hypergraphs. It serves, in particular,
as a universal tool to model several train composition rules in vehicle rotation
planning for long distance passenger railways. We prove that even for problems
with a small hyperarc size and hypergraphs with a special partitioned structure
the HAP is NP-hard and APX-hard. Further, we present an extended integer
linear programming formulation which implies, e. g., all clique inequalities.
An optimal control problem arising in the context of 3D electromagnetic induction heating is investigated. The state equation is given by a quasilinear stationary heat equation coupled with a semilinear time-harmonic eddy current equation. The temperature-dependent electrical conductivity and the presence of pointwise inequality state-constraints represent the main challenge of the paper. In the first part of the paper, the existence and regularity of the state are addressed. The second part of the paper deals with the analysis of the corresponding linearized equation. Some sufficient conditions are presented which guarantee the solvability of the linearized system. The final part of the paper is concerned with the optimal control. The aim of the optimization is to find the optimal voltage such that a desired temperature can be achieved optimally. The corresponding first-order necessary optimality condition is presented.
This paper is concerned with a PDE-constrained optimization problem of induction heating, where the state equations consist of 3D time--dependent heat equations coupled with 3D time--harmonic eddy current equations. The control parameters are given by finite real numbers representing applied alternating voltages which enter the eddy current equations via impressed current. The optimization problem is to find optimal voltages so that, under certain constraints on the voltages and the temperature, a desired temperature can be optimally achieved. As there are finitely many control parameters but the state constraint has to be satisfied in an infinite number of points, the problem belongs to a class of semi--infinite programming problems. We present a rigorous analysis of the optimization problem and a numerical strategy based on our theoretical result.
This paper is devoted to an optimal control problem of Maxwell's equations in the presence of pointwise state constraints. The control is given by a divergence--free three--dimensional vector function representing an applied current density. To cope with the divergence--free constraint on the control, we consider a vector potential ansatz. Due to the lack of regularity of the control--to--state mapping, existence of Lagrange multipliers cannot be guaranteed. We regularize the optimal control problem by penalizing the pointwise state constraints. Optimality conditions for the regularized problem can be derived straightforwardly. It also turns out that the solution of the regularized problem enjoys higher regularity which then allows us to establish its convergence towards the solution of the unregularized problem. The second part of the paper focuses on the numerical analysis of the regularized optimal control problem. Here the state and the control are discretized by N\'ed\'elec's curl--conforming edge elements. Employing the higher regularity property of the optimal control, we establish an a priori error estimate for the discretization error in the $\boldsymbol{H}(\bold{curl})$--norm. The paper ends by numerical results including a numerical verification of our theoretical results.
The pole condition approach for deriving transparent boundary conditions is extended to the time-dependent, two-dimensional case. Non-physical modes of the solution are identified by the position of poles of the solution's spatial Laplace transform in the complex plane. By requiring the Laplace transform to be analytic on some
problem dependent complex half-plane, these modes can be
suppressed. The resulting algorithm computes a finite number of coefficients of a series expansion of the Laplace transform, thereby providing an approximation to the exact boundary condition. The resulting error decays super-algebraically with the number of coefficients, so relatively few additional degrees of freedom are
sufficient to reduce the error to the level of the discretization error in the interior of the computational domain. The approach shows good results for the Schroedinger and the drift-diffusion equation
but, in contrast to the one-dimensional case, exhibits instabilities for the wave and Klein-Gordon equation. Numerical examples are shown that demonstrate the good performance in the former and the instabilities in the latter case.
We investigate a nonstandard phase field
model of Cahn-Hilliard type. The model, which was introduced in
[16], describes two-species phase segregation and consists of a
system of two highly nonlinearly coupled PDEs. It has been studied
recently in
[5], [6] for the case of homogeneous Neumann
boundary conditions. In this paper, we investigate the case that the
boundary condition for one of the unknowns of the system is of third
kind and nonhomogeneous. For the resulting system, we show
well-posedness, and we study optimal boundary control
problems. Existence of optimal controls is shown, and the first-order
necessary optimality conditions are derived. Owing to the strong
nonlinear couplings in the PDE system, standard arguments of optimal
control theory do not apply directly, although the control constraints
and the cost functional will be of standard type.
This paper is concerned with a diffusion model of phase-field type, consisting
of a {parabolic} system of two partial differential equations{,} interpreted as balances
of microforces and microenergy{, for two unknowns: the problem's order parameter $\rho$}
and the chemical potential $\mu$; each equation includes a viscosity term -- respectively, $\varepsilon \,\partial_t\mu$ and $\delta\,\partial_t\rho$ -- with $\varepsilon$ and $\delta$ two positive parameters; the field equations are complemented by Neumann homogeneous boundary conditions and suitable initial conditions. In a recent paper \cite{CGPS3}, we proved that this problem is \wepo\ and investigated the \loti\ \bhv\ of its $(\varepsilon,\delta)-$solutions. Here we discuss the asymptotic limit of the system as $\eps$
tends to $0$. We prove convergence of
$(\varepsilon,\delta)-$solutions to the corresponding solutions for
the case $\eps =0$, whose long-time behavior we characterize; in the
proofs, we employ compactness and monotonicity arguments.
A nonlocal quasilinear multi-phase system with nonconstant specific heat and heat conductivity
(2012)
In this paper, we prove the existence
and global boundedness from above for a solution to an
integrodifferential model for nonisothermal multi-phase
transitions under nonhomogeneous third type boundary conditions.
The system couples a quasilinear internal energy balance
ruling the evolution of the absolute temperature with a vectorial
integro-differential inclusion governing the vectorial
phase-parameter dynamics. The specific heat and the heat
conductivity k are allowed to depend both on the order parameter
$\chi$ and on the absolute temperature $\teta$ of the system, and
the convex component of the free energy may or may not be
singular. Uniqueness and continuous data dependence are
also proved under additional assumptions.
We investigate a distributed optimal control problem for a phase field
model of Cahn-Hilliard type. The model describes two-species phase segregation
on an atomic lattice under the presence of diffusion; it has been introduced recently in
[4], on the basis of the theory developed in [15], and consists of a system of two
highly nonlinearly coupled PDEs. For this reason, standard arguments of optimal control theory do not apply
directly, although the control constraints and the cost functional are of standard type.
We show that the problem admits a solution, and we derive the first-order
necessary conditions of optimality.
We consider a semilinear parabolic equation subject to a nonlinear dynamical boundary condition that is related to the so-calles Wentzell boundary condition. First, we prove the existence and uniqueness of global solutions as well as the existence of a global attractor. Then we derive a suitable Lojasiewicz-Simon-type inequality to show the convergence of global solutions to single steady states as time tends to infinity under the assumption that the nonlinear terms $f$, $g$ are real analytic. Moreover, we provide an estimate for the convergence rate.
Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially.
We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the "regularity" of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.
Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data.
In incompressible flows with vanishing
normal velocities at the boundary, irrotational forces in the momentum
equations should be balanced
completely by the pressure gradient.
Unfortunately, nearly all available discretization methods for incompressible flows violate this property.
The origin of the problem is that discrete velocity approximations
of incompressible flows are usually not
divergence-free. Hence, the use of divergence-free velocity reconstructions is
proposed wherever an $L^2$ scalar product appears in the discrete
variational formulation.
The approach is illustrated and applied to a nonconforming MAC-like discretization for unstructured Delaunay grids.
It is numerically demonstrated that a divergence-free velocity reconstruction based on the lowest-order Raviart-Thomas element
increases the robustness and accuracy of an existing convergent discretization, when irrotational forces appear in the momentum equations.
Optimal Thickness of a Cylindrical Shell -- An Optimal Control Problem in Linear Elasticity Theory
(2012)
In this paper we discuss optimization problems for cylindrical tubes which are loaded by an applied force. This is a problem of optimal control in linear elasticity theory (shape optimization). We are looking for an optimal thickness minimizing the deflection (deformation) of the tube under the influence of an external force.
From basic equations of mechanics, we derive the equation of deformation. We apply the displacement approach from shell theory and make use of the hypotheses of
Mindlin and Reissner. A corresponding optimal control problem is formulated and first order necessary conditions for the optimal solution (optimal thickness) are derived.
We present numerical examples which were solved by the finite element method.
We discuss shape optimization problems for cylindrical tubes that are loaded by time-dependent applied force. This is a problem of shape optimization that leads to optimal control in linear elasticity theory. We determine the optimal thickness of a cylindrical tube minimizing the deformation of the tube under the influence of the external force. The main difficulty is that the state equation is a hyperbolic partial differential equation of 4th order. First order necessary conditions for the optimal solution are derived. Based on them, a numerical method is set up and numerical examples are presented.
In this paper we propose and analyze a new Multiscale Method for solving semi-linear elliptic problems with heterogeneous and highly variable coeffcient functions. For this purpose we construct a generalized finite element basis that spans a low dimensional multiscale space. The basis is assembled by performing localized linear finescale computations in small patches that have a diameter of order H |log(H)| where H is the coarse mesh size. Without any assumptions on the type of the oscillations in the coeffcients, we give a rigorous proof for a linear convergence of the H1-error with respect to the coarse mesh
size. To solve the arising equations, we propose an algorithm that is based on a damped Newton scheme in the multiscale space.
We discuss the possibility of computing eigenpairs of some prototypical linear second-order self-adjoint elliptic partial differential operator (or its high-resolution finite element discretization) by numerical upscaling techniques. We compute a low-dimensional generalized finite element space that preserves small eigenvalues in a superconvergent way. The approximate eigenpairs are then obtained by solving the corresponding low-dimensional algebraic eigenvalue problem. The rigorous error bounds are based on two-scale decompositions of H1 by means of a certain Clement-type quasi-interpolation operator.
We present a discretization for dynamic large deformation contact problems without friction. Our model is based on Hamilton’s principle, which avoids the explicit appearance of the contact forces. The resulting differential inclusion is discretized in time using a modified midpoint rule. This modification, which concerns the evaluation of the generalized gradient, allows to achieve energy dissipativity. For the space discretization we use a dual-basis mortar method. The resulting spatial algebraic
problems are nonconvex minimization problems with nonconvex inequality constraints. These can be solved efficiently using a trust-region SQP framework with a monotone multigrid inner solver.
Flux variability analysis (FVA) is an important tool to further analyze the results obtained by flux balance analysis (FBA) on genome-scale metabolic networks. Standard FVA may predict unbounded fluxes through some reactions in the network even if the nutrient uptake rate is bounded. These fluxes violate the second law of thermodynamics. They may be eliminated by extending flux variability analysis with thermodynamic constraints.
We present a new algorithm for efficient flux variability (and flux balance) analysis with thermodynamic constraints, suitable for analyzing genome-scale metabolic networks. We first show that flux balance analysis with thermodynamic constraints is NP-hard. Then we derive a theoretical tractability result, which can be applied to metabolic networks in practice. We use this result to develop a new constraint programming algorithm Fast-tFVA for fast flux variability analysis with thermodynamic constraints (tFVA). Computational comparisons with previous methods demonstrate the efficiency of the new method. For tFVA, a speed-up of factor 30-300 is achieved.
In an analysis of genome-scale metabolic networks in the BioModels database, we found that in 485 out of 716 networks additional irreversible or fixed reactions could be detected.
Optimal dual martingales, their analysis and application to new algorithms for Bermudan products
(2012)
In this paper we introduce and study the concept of optimal and surely
optimal dual martingales in the context of dual valuation of Bermudan
options, and outline the development of new algorithms in this context.
We provide a characterization theorem, a theorem which gives conditions
for a martingale to be surely optimal, and a stability theorem concerning martingales which are near to be surely optimal in a sense. Guided
by these results we develop a framework of backward algorithms for constructing such a martingale. In turn this martingale may then be utilized
for computing an upper bound of the Bermudan product. The methodology is pure dual in the sense that it doesn’t require certain (input)
approximations to the Snell envelope.
In an Ito-Levy environment we outline a particular regression based
backward algorithm which allows for computing dual upper bounds without nested Monte Carlo simulation. Moreover, as a by-product this algorithm also provides approximations to the continuation values of the
product, which in turn determine a stopping policy. Hence, we may obtain lower bounds at the same time.
In a first numerical study we demonstrate a backward dual regression algorithm in a Wiener environment that is easy to implement and
is regarding accuracy comparable with the method of Belomestny et. al.
(2009).
In this paper, we study the dual representation for generalized multiple stopping problems,
hence the pricing problem of general multiple exercise options. We derive a dual representation which allows for cashflows which are subject to volume constraints modeled by
integer valued adapted processes and refraction periods modeled by stopping times. As
such, this extends the works by Schoenmakers (2010), Bender (2011a), Bender (2011b),
Aleksandrov and Hambly (2010), and Meinshausen and Hambly (2004) on multiple exercise
options, which either take into consideration a refraction period or volume constraints, but
not both simultaneously. We also allow more flexible cashflow structures than the additive
structure in the above references. For example some exponential utility problems are covered
by our setting. We supplement the theoretical results with an explicit Monte Carlo algorithm
for constructing confidence intervals for the price of multiple exercise options and exemplify
it by a numerical study on the pricing of a swing option in an electricity market.
In this article we propose a novel approach to reduce the computational complexity
of the dual method for pricing American options. We consider a sequence of
martingales that converges to a given target martingale and decompose the original
dual representation into a sum of representations that correspond to dierent levels
of approximation to the target martingale. By next replacing in each representation
true conditional expectations with their Monte Carlo estimates, we arrive at what
one may call a multilevel dual Monte Carlo algorithm. The analysis of this algorithm
reveals that the computational complexity of getting the corresponding target upper
bound, due to the target martingale, can be signicantly reduced. In particular, it
turns out that using our new approach, we may construct a multilevel version of the
well-known nested Monte Carlo algorithm of Andersen and Broadie (2004) that is,
regarding complexity, virtually equivalent to a non-nested algorithm. The performance
of this multilevel algorithm is illustrated by a numerical example.
The article investigates the relation between global solutions of hyperbolic balance laws and viscous balance laws on the circle. It is thematically located at the crossroads of hyperbolic and parabolic partial differential equations with one-dimensional space variable and periodic boundary conditions. The two equations are given by:
u_t+f(u)_x=g(u)
and
u_t+f(u)_x=e u_{xx}+g(u).
The main result of the paper corrects a result on the persistence of heteroclinic connections by Fan and Hale from 1995 when viscosity vanishes: The "Connection Lemma" states that a connection can only persist if the zero number of the source state is a multiple of the zero number of the target state. The "Cascading Theorem" then yields convergence of heteroclinic connections to a sequence of heteroclinic connections and stationary solutions in case of non-persistence.
In addition a full description of the connection problem of rotating waves on the parabolic attractor is given.
A capillary surface in a negative gravitational field describes the shape of the surface of a hanging drop in a capillary tube with wetting material on the bottom. Mathematical modeling leads to the volume- and obstacle-constrained minimization of a nonconvex nonlinear energy functional of mean curvature type which is unbounded from below. In 1984 Huisken proved the existence and regularity of local minimizers of this energy under the condition on gravitation being sufficiently weak. We prove convergence of a first order finite element approximation of these minimizers. Numerical results demonstrating the theoretic convergence order are given.
Recently, Khuller, Moss and Naor presented a greedy algorithm for the budgeted maximum coverage problem. In this note, we observe that this algorithm also approximates a special case of set-union knapsack problem within a constant factor. In the special case, an element is a member of less than a constant number of subsets. This guarantee naturally extends to densest k-subgraph problem on graphs of bounded degree.
Deformable surface models are often represented as triangular meshes in image segmentation applications. For a fast and easily regularized deformation onto the target object boundary, the vertices of the mesh are commonly moved along line segments (typically surface normals). However, in case of high mesh curvature, these lines may intersect with the target boundary at “non-corresponding” positions, or may not intersect at all. Consequently, certain deformations cannot be achieved. We propose omnidirectional displacements for deformable surfaces (ODDS) to overcome this limitation. ODDS allow each vertex to move not only along a line segment but within a surrounding sphere, and achieve globally optimal deformations subject to local regularization con-
straints. However, allowing a ball-shaped instead of a linear range of motion per vertex significantly increases runtime and memory. To alleviate this drawback, we propose a hybrid approach, fastODDS, with improved runtime and reduced memory requirements. Furthermore, fastODDS can also cope with simultaneous segmentation of multiple objects. We show the theoretical benefits of ODDS with experiments on synthetic data, and evaluate ODDS and fastODDS quantitatively on clinical image data of the mandible and the hip bones. There, we assess both the global segmentation accuracy as well as local accuracy in high curvature regions, such as the tip-shaped mandibular coronoid processes and the ridge-shaped acetabular rims of
the hip bones.
In this paper we investigate two different recoverable robust models to deal with cost uncertainties in a shortest path problem. Recoverable robustness extends the classical concept of robustness to deal with uncertainties by incorporating limited recovery actions after the
full data are revealed. Our first model focuses on the case where the recovery actions are quite restricted: after a simple path is fixed in the first stage, in the second stage, after all data are revealed, any path containing at most k new arcs may be chosen.
Thus, the parameter k can be interpreted as a mediator between
robust optimization - no changes allowed - and optimization
on the fly - an arbitrary solution can be chosen. Considering three
classical scenario sets, which model uncertainties in the cost function,
we show that this new problem is strongly NP-hard in all
these cases and is not approximable, unless P=NP.
This is in contrast to the robust shortest path problem, where, for
example, an optimal solution can be computed efficiently for interval
and Gamma-scenarios. For series-parallel graphs and interval scenarios,
we present a polynomial time algorithm for this recoverable robust
setting.
In our second model the recovery set, i.e., the set of paths selectable
in the second stage is not limited, but deviating from the previous
choice comes at extra cost. Thus, a path chosen in the first stage
produces renting costs modeled as an alpha-fraction of the scenario
cost. For an arc taken in the second stage the remaining cost needs
to be paid in addition to some extra inflation cost modeled by a beta-fraction
of the scenario cost, if the arc was not reserved beforehand. The
complexity status of this problem is similar to the robust case. Yet,
for Gamma-scenarios the problem is again strongly NP-hard,
but can be approximated.
In multicriteria optimization, a compromise solution is a feasible solution whose
cost vector minimizes the distance to the ideal point w.r.t. a given norm. The coor-
dinates of the ideal point are given by the optimal values for the single optimization
problem for each criterion.
We show that the concept of compromise solutions ts nicely into the existing
notion of Pareto optimality: For a huge class of norms, every compromise solution
is Pareto optimal, and under certain conditions on the norm all Pareto optimal so-
lution are also a compromise solution, for an appropriate weighting of the criteria.
Furthermore, under similar conditions on the norm, the existence of an FPTAS for
compromise solutions guarantees the approximability of the Pareto set.
These general results are completed by applications to classical combinatorial
optimization problems. In particular, we study approximation algorithms for the
multicriteria shortest path problem and the multicriteria minimum spanning tree
problem. On the one hand, we derive approximation schemes for both problems, on
the other hand we show that for the latter problem simple approaches like local search
and greedy techniques do not guarantee good approximation factors.
We investigate different dynamical regimes of neuronal network in the CA3 area of the hippocampus.
The proposed neuronal circuit includes two fast- and two slowly-spiking cells which are interconnected by means of dynamical synapses. On the individual level, each neuron is modeled by FitzHugh-Nagumo equations. Three basic rhythmic patterns are observed: gamma-rhythm in which the fast neurons are uniformly spiking, theta-rhythm in which the individual spikes are separated by quiet epochs, and theta/gamma rhythm with repeated patches of spikes. We analyze the influence of asymmetry of synaptic strengths on the synchronization in the network and demonstrate that
strong asymmetry reduces the variety of available dynamical states. The model network exhibits multistability; this results in occurrence of hysteresis in dependence on the conductances of individual connections. We show that switching between different rhythmic patterns in the network
depends on the degree of synchronization between the slow cells.
We consider the problem of numerical approximation for forward-backward stochastic
differential equations with drivers of quadratic growth (qgFBSDE). To illustrate the significance
of qgFBSDE, we discuss a problem of cross hedging of an insurance related financial
derivative using correlated assets. For the convergence of numerical approximation schemes for
such systems of stochastic equations, path regularity of the solution processes is instrumental.
We present a method based on the truncation of the driver, and explicitly exhibit error estimates
as functions of the truncation height. We discuss a reduction method to FBSDE with globally
Lipschitz continuous drivers, by using the Cole-Hopf exponential transformation. We finally
illustrate our numerical approximation methods by giving simulations for prices and optimal
hedges of simple insurance derivatives.
We consider backward stochastic differential equations with drivers of quadratic growth (qgBSDE). We prove several statements concerning path regularity and stochastic smooth-
ness of the solution processes of the qgBSDE, in particular we prove an extension of Zhang's path regularity theorem to the quadratic growth setting. We give explicit convergence rates for the difference between the solution of a qgBSDE and its truncation, filling an important gap in numerics for qgBSDE. We give an alternative proof of second order Malliavin differentiability for BSDE with drivers that are Lipschitz continuous (and differentiable), and
then derive the same result for qgBSDE.
In this paper, we deal with a hydraulic reservoir optimization problem with uncertainty on
inflows in a joint chance constrained programming setting. In particular, we will consider inflows with
a persistency effect, following a causal time series model, and examine the impact of the ”Gaussian”
assumption for such inflows. We present an iterative algorithm for solving similarly structured joint
chance constrained programming problems that requires a Slater point and the computation of gradients.
Several alternatives to the joint chance constraint problem are presented. In particular, we present an
individual chance constraint problem and a robust model. We illustrate the interest of joint chance
constrained programming by comparing results obtained on a realistic hydro-valley with those obtained
from the alternative models. Despite the fact that the alternative models often require less hypothesis
on the law of the inflows, we show that they yield conservative and costly solutions. The simpler models,
such as the individual chance constraint one, are shown to yield insufficient robustness and are therefore
not useful. We therefore conclude that Joint Chance Constrained programming appears as a technique
offering a good trade-off between cost and robustness and can be tractable for complex realistic models.
Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks,
operators highly overestimate the traffic volume during network planning. In this paper we consider
telecommunication network design under traffic uncertainty, adapting the robust optimization approach
of Bertsimas and Sim [21]. We present three different mathematical formulations for this problem, provide valid inequalities,
study the computational implications, and evaluate the realized robustness.
To enhance the performance of the mixed-integer programming solver we derive robust cutset inequalities generalizing their deterministic counterparts. Instead of a single cutset inequality for every
network cut, we derive multiple valid inequalities by exploiting the extra variables available in the robust formulations. We show that these inequalities define facets under certain conditions and that they
completely describe a projection of the robust cutset polyhedron if the cutset consists of a single edge.
For realistic networks and live traffic measurements we compare the formulations and report on the
speed up by the valid inequalities. We study the “price of robustness” and evaluate the approach by
analyzing the real network load. The results show that the robust optimization approach has the potential
to support network planners better than present methods.
We introduce an algorithm for
diffusion weighted magnetic resonance imaging data enhancement based on structural adaptive smoothing in both space and diffusion direction.
The method, called POAS, does not refer to a specific model for the data, like the diffusion tensor or higher order models.
It works by embedding the measurement space into a space with defined metric and group operations, in this case the Lie group of three-dimensional Euclidean motion SE(3).
Subsequently, pairwise comparisons of the values of the diffusion
weighted signal are used for adaptation.
The position-orientation adaptive smoothing preserves the edges of the observed fine and anisotropic structures.
The POAS-algorithm is designed to reduce noise directly in the diffusion weighted images and consequently also to reduce bias and
variability of quantities derived from the data for specific models.
We evaluate the algorithm on simulated and experimental data and demonstrate that it can be used to reduce the number of applied diffusion gradients and
hence acquisition time while achieving similar quality of data, or to improve the quality of data acquired in a clinically feasible scan time setting.
We derive and study a dynamical model for suspensions of negatively buoyant particles on an incline. Our theoretical model includes the settling/sedimentation due to gravity as well as the resuspension of particles induced by shear-induced migration, leading to disaggregation of the dense sediment layer. Out of the three different regimes observed in the experiments, we focus on the so-called settled case, where the particles settle out of the flow, and two distinct fronts, liquid and particle, form. Using an approach relying on asymptotics, we systematically connect our dynamic model with the previously developed equilibrium theory for particle-laden flows. We show that the resulting transport equations for the liquid and the particles are of hyperbolic type, and study the dilute limit, for which we derive the analytic solution. We also carry out a systematic experimental study of the settled regime, focusing on the motion of the liquid and the particle fronts. Finally, we carry out numerical simulations of our transport equations. We show that the model predictions for small to moderate values of the particle volume fraction and the inclination angle of the solid substrate agree well with the experimental data.
In the paradigm of VON N EUMANN AND M ORGENSTERN, a representation of affine pref-
erences in terms of an expected utility can be obtained under the assumption of weak continu-
ity. Since the weak topology is coarse, this requirement is a priori far from being negligible.
In this work, we replace the assumption of weak continuity by monotonicity. More precisely,
on the space of lotteries on an interval of the real line, it is shown that any affine preference
order which is monotone with respect to the first stochastic order admits a representation in
terms of an expected utility for some nondecreasing utility function. As a consequence, any
affine preference order on the subset of lotteries with compact support, which is monotone
with respect to the second stochastic order, can be represented in terms of an expected util-
ity for some nondecreasing concave utility function. We also provide such representations
for affine preference orders on the subset of those lotteries which fulfill some integrability
conditions. The subtleties of the weak topology are illustrated by some examples.
Im Zuge der Übernahme von 6 Linien der Havelbus Verkehrsgesellschaft mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der Entwicklung eines neuen Linien- und Taktplans für das Jahr 2010. Das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in einer projektbegleitenden Studie eingesetzt, um Alternativen bei verschiedenen Planungs- und Zielvorgaben auszuloten. In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen bestätigen, dass mit Hilfe von mathematischer Optimierung eine weitere Verkürzung der Reisezeit um 1%, eine als um 6% verkürzt empfundene Reisezeit, 10% weniger Fahrzeit im Fahrzeug und eine gleichzeitige Kostenreduktion um 5% möglich sind
Single-molecule force spectroscopy has proven to be a powerful tool for studying the kinetic be- havior of biomolecules. Through application of an external force, conformational states with small or transient populations can be stabilized, allowing them to be characterized and the statistics of in- dividual trajectories studied to provide insight into biomolecular folding and function. Because the observed quantity (force or extension) is not necessarily an ideal reaction coordinate, individual ob- servations cannot be uniquely associated with kinetically distinct conformations. While maximum- likelihood schemes such as hidden Markov models have solved this problem for other classes of single-molecule experiments by using temporal information to aid in the inference of a sequence of distinct conformational states, these methods do not give a clear picture of how precisely the model parameters are determined by the data due to instrument noise and finite-sample statistics, both sig- nificant problems in force spectroscopy. We solve this problem through a Bayesian extension that allows the experimental uncertainties to be directly quantified, and build in detailed balance to fur- ther reduce uncertainty through physical constraints. We illustrate the utility of this approach in characterizing the three-state kinetic behavior of an RNA hairpin in a stationary optical trap.
While seemingly straightforward in principle, the reliable estimation of rate constants is seldom easy in practice. Numerous issues, such as the complication of poor reaction coordinates, cause obvious approaches to yield unreliable estimates. When a reliable order parameter is available, the reactive flux theory of Chandler allows the rate constant to be extracted from the plateau region of an appropriate reactive flux correlation function. However, when applied to real data from single- molecule experiments or molecular dynamics simulations, the reactive flux correlation function requires the numerical differentiation of a noisy empirical correlation function, which can result in an unacceptably poor estimate of the rate and pathological dependence on the sampling interval. We present a modified version of this theory which does not require numerical derivatives, allowing rate constants to be robustly estimated from the time-correlation function directly. We illustrate the approach using single-molecule passive force spectroscopy measurements of an RNA hairpin.
Folding and conformational changes of macromolecules often require the generation of large amounts of simulation data that are difficult to ana- lyze. Markov state models (MSMs) address this challenge by providing a systematic way to decompose the state space of the molecular system into substates and to estimate a transition matrix containing the transi- tion probabilities between these substates. This transition matrix can be analyzed to reveal the metastable, i.e. long-living, states of the system, its slowest relaxation timescales and transition pathways and rates e.g. from unfolded to folded, or from dissociated to bound states. To reduce the technical burden of constructing such MSMs we provide the software framework EMMA (available at https://simtk.org/home/emma) to con- struct, validate and analyse such Markov State Models.
The slow processes of metastable stochastic dynamical systems are difficult to access by direct numerical simulation due the sampling problem. Here, we suggest an approach for modeling the slow parts of Markov processes by approximating the dominant eigenfunctions and eigenvalues of the propagator. To this end, a variational principle is derived that is based on the maximization of a Raleigh coefficient. It is shown that this Raleigh coefficient can be estimated from statistical observables that can be obtained from short distributed simulations starting from different parts of state space. The approach forms a basis for the development of adaptive and efficient computational algorithms for simulating and analyzing metastable Markov processes while avoiding the sampling problem. Since any stochastic process with finite memory can be transformed into a Markov process, the approach is applicable to a wide range of processes relevant for modeling complex real-world phenomena.
When simulating isolated resonators, the application of transparent boundary conditions causes the approximated spectrum to be polluted with spurious solutions. Distinguishing these artificial solutions from solutions with a physical meaning is often difficult and requires a priori knowledge of the spectrum or the expected field distribution of resonant states. We present an implementation of the pole condition that distinguishes between incoming and outgoing waves by the location of the poles of their Laplace transform as transparent boundary condition. This implementation depends on one tuning parameter. We will use the sensitivity of the computed solutions to perturbations of this parameter as a means to identify spurious solutions. To obtain global statements, we will combine this technique with a convergence monitor for the boundary condition.
We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem.
We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.
The mixed regularity of electronic wave functions in fractional order and weighted Sobolev spaces
(2012)
The paper continues the study of the regularity of electronic wave functions in Hilbert spaces of mixed derivatives. It is shown that the eigenfunctions of electronic Schr\"odinger operators and their
exponentially weighted counterparts possess, roughly speaking, square integrable mixed weak derivatives of fractional order $\vartheta$ for $\vartheta<3/4$. The bound $3/4$ is best possible and can neither be reached nor surpassed. Such results are important for the study
of sparse grid-like expansions of the wave functions and show that their asymptotic convergence rate measured in terms of the number of ansatz functions involved does not deteriorate with the number of electrons.
We study the expansion of the eigenfunctions of Schrödinger operators with smooth confinement potentials in Hermite functions; confinement potentials are potentials that become unbounded at infinity. The key result is that such eigenfunctions and all their derivatives decay more rapidly than any exponential function under some mild growth
conditions to the potential and its derivatives. Their expansion in Hermite functions converges therefore very fast, super-algebraically.