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)
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.
We solve Skorokhod's embedding problem for Brownian motion with linear drift $(W_t+ \kappa t)_{t\geq 0}$ by means of techniques of stochastic control theory. The search for a stopping time
$T$ such that the law of $W_T + \kappa T$ coincides with a prescribed law $\mu$ possessing the first
moment is based on solutions of backward stochastic differential equations of quadratic
type. This new approach generalizes an approach by Bass [Bas] of the classical version of
Skorokhod's embedding problem using martingale representation techniques.
We propose a hybrid approach for solving the resource-constrained project scheduling problem which is an extremely hard to solve combinatorial optimization problem of practical relevance. Jobs have to be scheduled on (renewable) resources subject to precedence constraints such that the resource capacities are never exceeded and the latest completion time of all jobs is minimized. The problem has challenged researchers from different communities, such as integer programming (IP), constraint programming (CP), and satisfiability testing (SAT). Still, there are instances with 60 jobs which have not been solved for many years. The currently best known approach, lazyFD, is a hybrid between CP and SAT techniques. In this paper we propose an even stronger hybridization by integrating all the three areas, IP, CP, and SAT, into a single branch-and-bound scheme. We show that lower bounds from the linear relaxation of the IP formulation and conflict analysis are key ingredients for pruning the search tree. First computational experiments show very promising results. For five instances of the well-known PSPLIB we report an improvement of lower bounds. Our implementation is generic, thus it can be potentially applied to similar problems as well.
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.
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.
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.
A theorem on error estimates for smooth nonlinear programming
problems in Banach spaces is proved that can be used to derive
optimal error estimates for optimal control problems. This theorem is applied
to a class of optimal control problems for quasilinear elliptic equations.
The state equation is approximated by a finite element scheme, while different
discretization methods are used for the control functions. The distance of
locally optimal controls to their discrete approximations is estimated.
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.
This study presents a differential equation model for the feedback mechanisms between
Gonadotropin-releasing Hormone (GnRH), Follicle-Stimulating Hormone (FSH), Luteinizing
Hormone (LH), development of follicles and corpus luteum, and the production of estradiol
(E2), progesterone (P4), inhibin A (IhA), and inhibin B (IhB) during the female menstrual
cycle. In contrast to other models, this model does not involve delay differential equations
and is based on deterministic modelling of the GnRH pulse pattern, which allows for faster
simulation times and efficient parameter identification. These steps were essential to tackle
the task of developing a mathematical model for the administration of GnRH analogues. The
focus of this paper is on model development for GnRH receptor binding and the integration of
a pharmacokinetic/pharmacodynamic model for the GnRH agonist Nafarelin and the GnRH
antagonist Cetrorelix into the menstrual cycle model. The final mathematical model describes
the hormone profiles (LH, FSH, P4, E2) throughout the menstrual cycle in 12 healthy women.
Moreover, it correctly predicts the changes in the cycle following single and multiple dose
administration of Nafarelin or Cetrorelix at different stages in the cycle.
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.
We propose a new approach to competitive analysis by introducing the novel concept of online approximation schemes. Such scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal competitive ratio to a question that a computer can answer. We believe that our method can also be applied to many other problems and yields a completely new and interesting view on online algorithms.
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 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.
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.
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.
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.
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.
Supercomputers can simulate complex molecular systems. However, there is a very large gap between the fastest oscillations of covalent bonds of a molecule and the time-scale of the dominant processes. In order to extract the dominant time-scales and to identify the dominant processes, a clustering of information is needed. This thesis shows that only the subspace-based Robust Perron Cluster Analysis (PCCA+) can solve this problem correctly by the construction of a Markov State Model. PCCA+ allows for time-extrapolation in molecular kinetics. This thesis shows the difference between molecular dynamics and molecular kinetics. Only in the molecular kinetics framework a definition of transition rates is possible. In this context, the existence of an infinitesimal generator of the dynamical processes is discussed. If the existence is assumed, the Theorem of Gauß can be applied in order to compute transition rates efficiently. Molecular dynamics, however, is not able to provide a suitable statistical basis for the determination of the transition pattern.
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.
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.
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.
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.
Markov state models have become very popular for the description of conformation dynamics of molecules over
long timescales. The construction of such models requires a partitioning of the configuration space such that the discretization
can serve as an approximation of metastable conformations. Since the computational complexity for the construction of a
Markov state model increases quadratically with the number of sets, it is desirable to obtain as few sets as necessary. In this
paper we propose an algorithm for the adaptive refinement of an initial coarse partitioning. A spectral clustering method is
applied to the final partitioning to detect the metastable conformations. We apply this method to the conformation analysis of
a model tri-peptide molecule, where metastable beta- and gamma-turn conformations can be identified.
Our model of the bovine estrous cycle is a set of ordinary differential equations which generates hormone profiles of successive estrous cycles with several follicular waves per cycle. It describes the growth and decay of the follicles and the corpus luteum, as well as the change of the key substances over time. In this work we describe recent improvements of this model, including the introduction of new components, and elimination of time delays. We validate our model by showing that the simulations agree with observations from synchronization studies and with measured progesterone data after a single dose administration of synthetic prostaglandin F2alpha.
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.
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.
Energetic reasoning is one of the most powerful propagation algorithms in cumulative scheduling. In practice, however, it is not commonly used because it has a high running time and its success highly depends on the tightness of the variable bounds. In order to speed up energetic reasoning, we provide an easy-to-check necessary condition for energetic reasoning to detect infeasibilities. We present an implementation of energetic reasoning that employs this condition and that can be parametrically adjusted to handle the trade-off between solving time and propagation overhead. Computational results on instances from the PSPLIB are provided. These results show that using this condition decreases the running time by more than a half, although more search nodes need to be explored.
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.
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.
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 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.
Analysis of the second phase of the GMRES convergence for a convection-diffusion model problem
(2012)
It is well konwn that GMRES applied to linear algebraic systems arising from a convection-diffusion model problem that has been discretized by the streamline upwind Petrov-Galerkin (SUPG) method, typically displays two distinct phases of convergence: a slow initial phase followed by a convergence acceleration in the second phase. This paper complements the known results on the length of the initial phase by analyzing how the acceleration in the second phase of convergence is related to the mesh Peclet number and the choice of the stabilization parameter in the SUPG discretization. The analysis is based on some new expressions and bounds for the GMRES residuals, which can be of general interest.
In this paper we revisit models for the description of the evolution of crystalline films with anisotropic surface energies.
We prove equivalences of symmetry properties of anisotropic surface energy models commonly used in the literature.
Then we systematically develop a framework for the derivation of surface diffusion models for the self-assembly of quantum dots during Stranski-Krastanov
growth that include surface energies also with large anisotropy as well as the effect of wetting energy,
elastic energy and a randomly perturbed atomic deposition flux.
A linear stability analysis for the resulting sixth-order semilinear evolution equation for the thin film surface shows that that the new model allows
for large anisotropy and gives rise to the formation of anisotropic quantum dots. The nonlinear three-dimensional evolution is investigated via numerical solutions.
These suggest that increasing anisotropy stabilizes the faceted surfaces and may lead to a dramatic slow-down of the coarsening of the dots.
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.
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.
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.
Modelling, parameter identification, and simulation play an important rôle in Systems Biology. In recent years, various software packages have been established for scientific use in both licencing types, open source as well as commercial. Many of these codes are based on inefficient and mathematically outdated algorithms. By introducing the package BioPARKIN recently developed at ZIB, we want to improve this situation significantly. The development of the software BioPARKIN involves long standing mathematical ideas that, however, have not yet entered the field of Systems Biology, as well as new ideas and tools that are particularly important for the analysis of the dynamics of biological networks. BioPARKIN originates from the package PARKIN, written by P.Deuflhard and U.Nowak, that has been applied successfully for parameter identification in physical chemistry for many years.
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.
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.
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 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 consider a class of generalized capital asset pricing models in continuous time with a finite number of agents and tradable securities. The securities may not be sufficient to span all sources of uncertainty. If the agents have exponential utility functions and the individual endowments are spanned by the securities, an equilibrium exists and the agents’ optimal trading strategies are constant. Affine processes, and the theory of information-based asset pricing are used to model the endogenous asset price dynamics and the terminal payoff. The derived semi-explicit pricing formulae are applied to numerically analyze the impact of the agents’ risk aversion on the implied volatility of simultaneously-traded European-style options.
Convergence Analysis of Smoothing Methods for Optimal Control of Stationary Variational Inequalities
(2012)
In the article an optimal control problem subject to a stationary variational inequality is investigated. The optimal control problem is complemented with pointwise
control constraints. The convergence of a smoothing scheme is analyzed. There, the variational inequality is replaced by a semilinear elliptic equation. It is shown that solutions of the regularized optimal control problem converge to solutions of the original one. Passing to
the limit in the optimality system of the regularized problem allows to prove C-stationarity of local solutions of the original problem. Moreover, convergence rates with respect to the regularization parameter for the error in the control are obtained. These rates coincide with
rates obtained by numerical experiments, which are included in the paper.
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.
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.
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.
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.
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.
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.
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.
We formulate the static mechanical coupling of a geometrically exact Cosserat rod to an elastic continuum. The coupling conditions accommodate for the difference in dimension between the two models. Also, the Cosserat rod model incorporates director variables, which are not present in the elastic continuum model. 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. We also derive the corresponding conditions for the dual variables and interpret them in mechanical terms.
We provide results on the existence and uniqueness of equilibrium in dynamically incomplete financial markets in discrete time. Our framework allows for heterogeneous agents, unspanned random endowments and convex trading constraints. In the special case where all agents have preferences of the same type and all random endowments are replicable by trading in the financial market we show that a one-fund theorem holds and give an explicit expression for the equilibrium pricing kernel. If the underlying noise is generated by finitely many Bernoulli random walks, the equilibrium dynamics can be described by a system of coupled backward stochastic difference equations, which in the continuous-time limit becomes a multi-dimensional backward stochastic differential equation. If the market is complete in equilibrium, the system of equations decouples, but if not, one needs to keep track of the prices and continuation values of all agents to solve it. As an example we simulate option prices in the presence of stochastic volatility, demand pressure and short-selling constraints.
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.
We analyze a remarkable class of centrally symmetric polytopes, the Hansen
polytopes of split graphs. We confirm Kalai's 3^d-conjecture for such polytopes
(they all have at least 3^d nonempty faces) and show that the Hanner polytopes
among them (which have exactly 3^d nonempty faces) correspond to threshold
graphs. Our study produces a new family of Hansen polytopes that have only
3^d+16 nonempty faces.
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.
We consider a dynamical system described by the differential equation $\dot{Y}_t = -U^'(Y_t)$
with a unique stable point at the origin. We perturb the system by L\'evy noise of
intensity $\varepsilon$, to obtain the stochastic differential equation $dX^\varepsilon_t = -U^'(X^\varepsilon_{t-})dt + \varepsilon dL_t}.
The process $L$ is a symmetric L\'evy process whose jump measure $\nu$ has exponentially
light tails, $\nu([u, \infty))\sim exp(-u^\alpha), \alpha > 0, u \to\infty$. We study the first exit problem for
the trajectories of the solutions of the stochastic differential equation from the interval
$[-1, 1]$. In the small noise limit $\varepsilon\to 0$ we determine the law and the mean value of the
first exit time, to discover an intriguing phase transition at the critical index $\alpha = 1$.
Flows over time and generalized flows are two advanced network flow models of utmost importance, as they incorporate two crucial features occurring in numerous real-life networks. Flows over time feature time as a problem dimension and allow to realistically model the fact that commodities (goods, information, etc.) are routed through a network over time. Generalized flows allow for gain/loss factors on the arcs that model physical transformations of a commodity due to leakage, evaporation, breeding, theft, or interest rates. Although the latter effects are usually time-bound, generalized flow models featuring a temporal dimension have never been studied in the literature.
In this paper we introduce the problem of computing a generalized maximum flow over time in networks with both gain factors and transit times on the arcs. While generalized maximum flows and maximum flows over time can be computed efficiently, our combined problem turns out to be NP-hard and even completely non-approximable. A natural special case is given by lossy networks where the loss rate per time unit is identical on all arcs. For this case we present a (practically efficient) FPTAS that also reveals a surprising connection to so-called earliest arrival flows.
Global higher integrability of minimizers of variational problems with mixed boundary conditions
(2012)
We consider integral functionals with densities of p-growth, with respect to gradients, on a Lipschitz domain with mixed boundary conditions. The aim of this paper is to prove that, under uniform estimates within certain classes of p-growth and coercivity assumptions on the density, the minimizers are of higher integrability order, meaning that they belong to the space of first order Sobolev functions with an integrability of order $p+\epsilon$ for a uniform $\epsilon >0$. The results are applied to a model describing damage evolution in a nonlinear elastic body and to a model for shape memory alloys.
Global spatial regularity for elasticity models with cracks, contact and other nonsmooth constraints
(2012)
A global higher differentiability result in Besov
spaces is proved for the displacement fields of linear elastic models
with self contact.
Domains with cracks are studied, where nonpenetration
conditions/Signorini conditions are imposed on the crack faces.
It is shown that
in a neighborhood of crack tips (in 2D) or
crack fronts (3D) the displacement fields are
$B^{3/2}_{2,\infty}$ regular.
The proof relies on a difference
quotient argument for the directions tangential to the crack. In order
to obtain the regularity estimates also in the normal direction, an
argument due to
Ebmeyer/Frehse/Kassmann is modified.
The methods are then applied to further examples like
contact problems with nonsmooth rigid foundations, to a model with
Tresca friction and
to minimization problems with
nonsmooth energies and constraints as they occur for instance in the modeling of
shape memory alloys.
Based on Falk's approximation Theorem for variational
inequalities, convergence rates for FE-discretizations of contact
problems are derived relying on the proven regularity properties.
Several numerical examples illustrate the theoretical results.
We provide lower estimates for the norm of gradients of Gaussian
distribution functions and apply the results obtained to a special class of
probabilistically constrained optimization problems. In particular, it is shown
how the precision of computing gradients in such problems can be controlled
by the precision of function values for Gaussian distribution functions. Moreover,
a sensitivity result for optimal values with respect to perturbations of the
underlying random vector is derived. It is shown that the so-called maximal
increasing slope of the optimal value with respect to the Kolmogorov distance
between original and perturbed distribution can be estimated explicitly from
the input data of the problem.
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.
Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.
We consider a basic subproblem which arises in line planning,
and is of particular importance in the context of a high system
load or robustness: How much can be routed maximally along all possible
lines? The essence of this problem is the Path Constrained Network
Flow (PCN) problem. We explore the complexity of this problem and
its dual. In particular we show for the primal that it is as hard to
approximate as MAX CLIQUE and for the dual that it is as hard to
approximate as SET COVER. We also prove that the PCN problem is
hard for special graph classes, interesting both from a complexity and
from a practical perspective. Finally, we present a special graph class
for which there is a polynomial-time algorithm.
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).
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.
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.
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, 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.
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).
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.
We study minimal supersolutions of backward stochastic differential equations. We show the existence and uniqueness of the minimal supersolution, if the generator is jointly lower semicontinuous, bounded from below by an affine function of the control variable, and satisfies a specific normalization property. Semimartingale convergence is used to establish the main result.
We study a nonlinear operator defined via minimal supersolutions of backward stochastic differential equations with generators that are monotone in y, convex in z, jointly lower semicontinuous, and bounded below by an affine function of the control variable. We show existence, uniqueness, monotone convergence, Fatou’s Lemma and lower semicontinuity of this functional. We provide a comparison principle for the underlying minimal supersolutions of BSDEs, which we illustrate by maximizing expected exponential utility.
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.
MIPLIB 2010
(2012)
This paper reports on the fifth version of the Mixed Integer Programming Library. The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.
In recent years, substantial progress in shape analysis has been achieved through methods that use the spectra and eigenfunctions of discrete Laplace operators. In this work, we study spectra and eigenfunctions of discrete differential operators that can serve as an alternative to discrete Laplacians for applications in shape analysis. We construct such operators as the Hessians of surface energies or deformation energies. In particular, we design a quadratic energy such that, on the one hand, its Hessian equals the Laplace operator if the surface is a part of the Euclidean plane, and, on the other hand, the Hessian eigenfunctions are sensitive to the extrinsic curvature (e.g. sharp bends) on curved
surfaces. Furthermore, we consider eigenvibrations induced by deformation energies, and we derive a closed form representation for the Hessian (at the rest state of the energy) for a general class of deformation energies. Based on these spectra and eigenmodes, we derive two shape signatures. One that measures the similarity of points on a surface, and another that can be used to identify features of surfaces.
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.
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.
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.
We introduce nonsmooth Schur-Newton methods for the solution of the nonlinear discrete saddle-point problems arising from discretized vector-valued Cahn-Hilliard equations with logarithmic and obstacle potentials. The discrete problems are obtained by semi-implicit discretization in time and a first order finite element discretization in space. We incorporate the linear constraints that enforce solutions to stay on the Gibbs simplex using Lagrangian multipliers and prove existence of these multipliers under the assumption of a non-trivial initial condition for the order parameters.
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.
We present a unified computational framework for matching 3d geometric objects (points, lines, surfaces, volumes) of highly varying shape. Our approach is based on the Large Deformation Diffeomorphic Metric Mapping (LDDMM) method acting on $m$-currents. After stating an optimization algorithm in the function space of admissible morph generating velocity fields, two innovative aspects in this framework are presented: First, we spatially discretize the velocity field with conforming adaptive finite elements and discuss advantages of this new approach. Secondly, we directly compute the temporal evolution of discrete $m$-current attributes. Several numerical experiments demonstrate the effectiveness of this approach.
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.
Genome-scale metabolic networks are useful tools for achieving a system-level understanding of metabolism. However, due to their large size, analysis of such networks may be difficult and algorithms can be very slow. Therefore, some authors have suggested to analyze subsystems instead of the original genome-scale models.
Flux coupling analysis (FCA) is a well-known method for detecting functionally related reactions in metabolic networks.
In this paper, we study how flux coupling relations may change if we analyze a subsystem instead of the original network. We show mathematically that a pair of fully, partially or directionally coupled reactions may be detected as uncoupled in certain subsystems. Interestingly, this behavior is the opposite of the flux coupling changes that may occur due to missing reactions, or equivalently, deletion of reactions.
Computational experiments suggest that the analysis of plastid (but not mitochondrial) subsystems may significantly influence the results of FCA. Therefore, the results of FCA for subsystems, especially plastid subsystems, should be interpreted with care.
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.
This paper deals with the computation of regular coderivatives of
solution maps associated with a frequently arising class of generalized equations.
The constraint sets are given by (not necessarily convex) inequalities,
and we do not assume linear independence of gradients to active constraints.
The achieved results enable us to state several versions of sharp necessary optimality
conditions in optimization problems with equilibria governed by such
generalized equations. The advantages are illustrated by means of examples.
Some optimal control problems for linear and nonlinear ordinary differential equations related to the optimal switching between
different magnetic fields are considered. The main aim is to move an electrical initial current by a controllable
voltage in shortest time to a desired terminal current and to hold it afterwards. Necessary optimality conditions are derived by
Pontryagin's principle and a Lagrange technique. In the case of a linear system, the principal structure of time-optimal controls is
discussed. The associated optimality systems are solved by a one-shot strategy
using a multigrid software package. Various numerical examples are discussed.
We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.
We derive a-priori estimates on the length of the primal-dual path that results from a Moreau-Yosida approximation of the feasible set for state constrained optimal control problems. These bounds depend on the regularity of the state and the dimension of the problem. Comparison with numerical results indicates that these bounds are sharp and are attained for the case of a single active point.
In a strong constant electric field, a dielectric particle immersed in a weakly conducting fluid exhibits spontaneous rotations. This phenomenon is known under the name of the Quincke effect. In the original setup the particle was suspended on a silk thread and performed torsional oscillations of remarkably high amplitude. We derive the governing equations for this experiment, and ascertain
that onset of oscillations from the quiescent state corresponds to the supercritical Hopf bifurcation.
For the case of a soft thread, we characterize the regime of large-scale torsional relaxation oscillations:
explicit estimates are derived for their period and amplitude, effects of bifurcation delay are described. In a stronger electric field, these relaxation oscillations yield to small-scale erratic rotations of the pendulum.
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 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.
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