Refine
Year of publication
Language
- English (1103) (remove)
Keywords
- optimal control (27)
- stability (14)
- integer programming (11)
- Stochastic programming (9)
- finite elements (9)
- mixed integer programming (9)
- Hamiltonian matrix (8)
- finite element method (8)
- model reduction (8)
- state constraints (8)
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.
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.
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.
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).
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.
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 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.
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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.