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)
Group-velocity matched cross-phase modulation between a fundamental soliton and a dispersive wave-packet has been previously suggested for optical switching applications similar to an optical transistor. Moreover, the nonlinear interaction in the resulting group-velocity horizon can be exploited for adiabatic compression of the soliton down into the few-cycle regime. Here we show that both mechanisms can be combined. In such a transient compressor, parameters of the dispersive wave may then serve to actively control the soliton compression and adjust the pulse duration in the presence of disturbances. While a certain amount of control is already enabled by the delay between soliton and dispersive wave, the means of controlling the compression process are substantially enhanced by additionally manipulating the chirp of the dispersive wave. Moreover, controlling the chirp of the dispersive wave also enables correction for limitations of the compression scheme due to a self-frequency shift of the soliton or for uncompensated dispersion in the scheme. This substantially widens the practicality of the compression scheme and other applications of the highly efficient nonlinear interaction at the group-velocity horizon.
Dissipative Hamiltonian (DH) systems are an important concept in energy based modeling of dynamical
systems. One of the major advantages of the DH formulation is that the system encodes system
properties in an algebraic way in the system. Making use of the structure,
it is easy to see that DH systems are stable. In this paper
the question is discussed when a linear constant coefficient DH system is on the boundary
of the region of asymptotic stability, i.e., when it has purely imaginary eigenvalues,
or how much it has to be perturbed to be on this boundary. For unstructured systems this distance to instability (stability radius) is well-understood. In this paper,
explicit formulas for this distance under structure preserving perturbations are determined.
It is also shown (via numerical examples) that under structured perturbations the asymptotical
stability of a DH system is much more robust than for unstructured perturbations, since the
distance can be much larger.
In this paper, we introduce and study analytically a vectorial Cahn-Hilliard reaction model coupled with rate-dependent damage processes. The recently proposed Cahn-Hilliard reaction model can e.g. be used to describe the behavior of electrodes of lithium-ion batteries as it includes both the intercalation reactions at the surfaces and the separation into different phases. The coupling with the damage process allows considering simultaneously the evolution of a damage field, a second important physical effect occurring during the charging or discharging of lithium-ion batteries.
Mathematically, this is realized by a Cahn-Larché system with a non-linear Newton boundary condition for the chemical potential and a doubly non-linear differential inclusion for the damage evolution. We show that this system possesses an underlying generalized gradient structure which incorporates the non-linear Newton boundary condition. Using this gradient structure and techniques from the field of convex analysis we are able to prove constructively the existence of weak solutions of the
coupled PDE system.
We discuss analytical and numerical methods for the optimization of optoelectronic devices by performing optimal control of the PDE governing the carrier transport with respect to the doping profile. First, we provide a cost functional that is a sum of a regularization and a contribution, which is motivated by the modal net gain that appears in optoelectronic models of bulk or quantum- well lasers. Then, we state a numerical discretization, for which we study optimized solutions for different regularizations and for vanishing weights.
We derive thermodynamically consistent models of reaction-diffusion equations
coupled to a heat equation. While the total energy is conserved, the total
entropy serves as a driving functional such that the full coupled system is a
gradient flow. The novelty of the approach is the Onsager structure, which is
the dual form of a gradient system, and the formulation in terms of the
densities and the internal energy. In these variables it is possible to assume
that the entropy density is strictly concave such that there is a unique
maximizer (thermodynamical equilibrium) given linear constraints on the total
energy and suitable density constraints.
We consider two particular systems of this type, namely, a
diffusion-reaction bipolar energy transport system, and a
drift-diffusion-reaction energy
transport system with confining potential. We prove corresponding
entropy-entropy production inequalities with explicitly calculable constants
and establish the convergence to thermodynamical equilibrium, at first in
entropy and further in $L^1$ using Cziszar-Kullback-Pinsker type inequalities.
We consider a non-isothermal multi-phase field model.
We subsequently discretize implicitly in time and with
linear finite elements. The arising algebraic problem is
formulated in two variables where one is the multi-phase
field, and the other contains the inverse temperature field.
We solve this saddle point problem numerically by a
non-smooth Schur-Newton approach using truncated
non-smooth Newton multigrid methods. An application in
grain growth as occurring in liquid phase crystallization
of silicon is considered.
In these notes we discuss two approaches to evolutionary Γ- convergence of gradient systems in Hilbert spaces. The formulation of the gradient system is based on two functionals, namely the energy functional and the dissipation potential, which allows us to employ Γ- convergence methods. In the first approach we consider families of uni- formly convex energy functionals such that the limit passage of the time-dependent problems can be based on the theory of evolutionary variational inequalities as developed by Daneri and Savar ́e 2010. The second approach uses the equivalent formulation of the gradient system via the energy-dissipation principle and follows the ideas of Sandier and Serfaty 2004.
We apply both approaches to rigorously derive homogenization limits for Cahn–Hilliard-type equations. Using the method of weak and strong two-scale convergence via periodic unfolding, we show that the energy and dissipation functionals Γ-converge. In conclusion, we will give specific examples for the applicability of each of the two approaches.
Structure-preserving generic low-rank perturbations are studied for classes of structured matrix pencils, including real symmetric, complex symmetric, and complex Hermitian pencils. For singular pencils it is analyzed which characteristic quantities stay invariant in the perturbed canonical form, and it is shown that the regular part of a structured matrix pencil is not affected by generic perturbations of rank one. When the rank one perturbations involve a scaling parameter, the behavior of the canonical forms in dependence of this parameter is analyzed as well.
We study a stationary thermistor model describing the electrothermal behavior of organic semiconductor devices featuring non-Ohmic current-voltage laws and self-heating effects. The coupled system consists of the current-flow equation for the electrostatic potential and the heat equation with Joule heating term as source. The self-heating in the device is modeled by an Arrhenius-like temperature dependency of the electrical conductivity. Moreover, the non-Ohmic electrical behavior is modeled by a power law such that the electrical conductivity depends nonlinearly on the electric field. Notably, we allow for functional substructures with different power laws, which gives rise to a $p(x)$-Laplace-type problem with piecewise constant exponent.
We prove the existence and boundedness of solutions in the two-dimensional case. The crucial point is to establish the higher integrability of the gradient of the electrostatic potential to tackle the Joule heating term. The proof of the improved regularity is based on Caccioppoli-type estimates, Poincar\'e inequalities, and a Gehring-type Lemma for the $p(x)$-Laplacian. Finally, Schauder's fixed-point theorem is used to show the existence of solutions.
We consider a coupled system of two elliptic PDEs, where the elliptic term in the first equation shares the properties of the $p(x)$-Laplacian with discontinuous exponent, while in the second equation we have to deal with an a~priori $L^1$ term on the right hand side. Such a system of equations is suitable for the description of various electrothermal effects, in particular those, where the non-Ohmic behavior can change dramatically with respect to the spatial variable. We prove the existence of a weak solution under very weak assumptions on the data and also under general structural assumptions on the constitutive equations of the model. The main difficulty consists in the fact that we have to overcome simultaneously two obstacles - the discontinuous variable exponent (which limits the use of standard methods) and the $L^1$ right hand side of the heat equation. Our existence proof based on Galerkin approximation is highly constructive and therefore seems to be suitable also for numerical purposes.
Trajectory- or mesh-based methods for analyzing the dynamical behavior of large
molecules tend to be impractical due to the curse of dimensionality - their computational cost increases
exponentially with the size of the molecule. We propose a method to break the curse by a
novel square root approximation of transition rates, Monte Carlo quadrature and a discretization
approach based on solving linear programs. With randomly sampled points on the molecular energy
landscape and randomly generated discretizations of the molecular conguration space as our initial
data, we construct a matrix describing the transition rates between adjacent discretization regions.
This transition rate matrix yields a Markov State Model of the molecular dynamics. We use Perron
cluster analysis and coarse-graining techniques in order to identify metastable sets in conguration
space and approximate the transition rates between the metastable sets. Application of our method
to a simple energy landscape on a two-dimensional conguration space provides proof of concept and
an example for which we compare the performance of dierent discretizations. We show that the
computational cost of our method grows only polynomially with the size of the molecule. However,
nding discretizations of higher-dimensional conguration spaces in which metastable sets can be
identied remains a challenge.
The chemical master equation is a fundamental equation in chemical kinetics. It underlies the classical reaction-rate equations and takes stochastic effects into account. In this paper we give a simple argument showing that the solutions of a large class of chemical master equations are bounded in weighted $\ell_1$-spaces and possess high-order moments. This class includes all equations in which no reactions between two or more already present molecules and further external reactants occur that add mass to the system. As an illustration for the implications of this kind of regularity, we analyze the effect of truncating the state space. This leads to an error analysis for the finite state projections of the chemical master equation, an approximation that forms the basis of many numerical methods.
The present work deals with the resolution of the Poisson equation in a bounded domain made of a thin and periodic layer of finite length placed into a homogeneous medium.
We provide and justify a high order asymptotic expansion which takes into account the boundary layer effect occurring in the vicinity of the periodic layer as well as the corner singularities appearing in the neighborhood of the extremities of the layer. Our approach combines mixes
the method of matched asymptotic expansions and the method of periodic surface homogenization.
We study non-isothermal nucleation and growth phase transformations, which are described by a generalized Avrami model for the phase transition coupled with an energy balance to account for recalescence
effects. The main novelty of our work is the identification of temperature dependent nucleation rates. We prove that such rates can be uniquely identified from measurements in a subdomain and apply an optimal control approach to develop a numerical strategy for its computation.
Let $\sigma_t(x)$ denote the implied volatility at maturity t for a strike $K = S_0 e^{x t}$, where $x \in R$ and $S_0$ is the current value of the underlying. We show that $\sigma_t(x)$ has a uniform (in $x$) limit as maturity t tends to infinity, given by the formula \sigma_{\infty}(x) = \sqrt2 (h^*(x)^{1/2} + (h^*(x) − x)^{1/2}, for $x$ in some compact neighbourhood of zero in the class of affine stochastic volatility models. The function $h^*$ is the convex dual of the limiting cumulant generating function $h$ of the scaled log-spot process. We express $h$ in terms of the functional characteristics of the underlying model. The proof of the limiting formula rests on the large deviation behaviour of the scaled log-spot process as time tends to infinity. We apply our results to obtain the limiting smile for several classes of stochastic volatility models with jumps used in applications (e.g. Heston with state-independent jumps, Bates with state-dependent jumps and Barndorff-Nielsen-Shephard model).
In this article we show, that the binding kinetics of a molecular system can be
identied by a projection of a continuous process onto a nite number of macro states. We thus
interpret binding kinetics as a projection. When projecting onto non-overlapping macro states the
Markovianity is spoiled. As a consequence, the description of e.g. a receptor-ligand system by a two
state kinetics is not accurate. By assigning a degree of membership to each state, we abandon the
non-overlapping approach. This overlap is crucial for a correct mapping of binding eects by Markov
State Models with regard to their long time behavior. It enables us to describe the highly discussed
rebinding eect, where the spatial arrangement of the system has the be included. By introducing
a \degree of fuzziness" we have an indicator for the strength of the rebinding eect, such that the
minimal rebinding eect can be derived from an optimization problem. The fuzziness also includes
some new paradigms for molecular kinetics. These new model paradigms show good agreement with
experimental data.
Markov State Models (MSMs) are widely used to represent molecular
conformational changes as jump-like transitions between subsets of the conformational
state space. However, the simulation of peptide folding in explicit water is
usually said to be unsuitable for the MSM framework. In this article, we summarize
the theoretical background of MSMs and indicate that explicit water simulations do
not contradict these principles. The algorithmic framework of a meshless conformational
space discretization is applied to an explicit water system and the sampling
results are compared to a long-term molecular dynamics trajectory. The meshless
discretization approach is based on spectral clustering of stochastic matrices (MSMs)
and allows for a parallelization of MD simulations. In our example of Trialanine we
were able to compute the same distribution of a long term simulation in less computing
time.
This paper is concerned with the distributed optimal control of a
time-discrete Cahn--Hilliard/Navier--Stokes system with variable
densities.
It focuses on the double-obstacle potential which yields an optimal
control problem for a family of coupled systems in each time instance of a
variational inequality of fourth order and the Navier--Stokes equation.
By proposing a suitable time-discretization, energy estimates are proved
and the existence of solutions to the primal system and of optimal
controls is established for the original problem as well as for a family
of regularized problems. The latter correspond to Moreau--Yosida type
approximations of the double-obstacle potential. The consistency of these
approximations is shown and first order optimality conditions for the
regularized problems are derived. Through a limit process, a stationarity
system for the original problem is established which is related to a
function space version of C-stationarity.
We propose a composite step method, designed for equality constrained optimization with partial differential equations. Focus is laid on the construction of a globalization scheme, which is based on cubic regularization of the objective and an affine covariant damped Newton method for feasibility. We show finite termination of the inner loop and fast local convergence of the algorithm. We discuss preconditioning strategies for the iterative solution of the arising linear systems with projected conjugate gradient. Numerical results are shown for optimal control problems subject to a nonlinear heat equation and subject to nonlinear elastic equations arising from an implant design problem in craniofacial surgery.
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.
We study a mechanical equilibrium problem for a material consisting of two components with different densities, which allows to change the outer shape by changing the interface between the subdomains. We formulate the shape design problem of compensating unwanted workpiece
changes by controlling the interface, employ regularity results for transmission problems for a rigorous derivation of optimality conditions based on the speed method, and conclude with some numerical results based on a spline approximation of the interface.
In this paper we propose a time discretization of a system of two parabolic equations describing diffusion-driven atom rearrangement in crystalline matter. The equations express the balances of microforces and microenergy; the two phase fields are the order parameter and the chemical potential. The initial and boundary-value problem for the evolutionary system is known to be well posed. Convergence of the discrete scheme to the solution of the continuous problem is proved by a careful development of uniform estimates, by weak compactness and a suitable treatment of
nonlinearities. Moreover, for the difference of discrete
and continuous solutions we prove an error estimate of
order one with respect to the time step.
This note is concerned with a nonlinear diffusion problem of phase-field type, consisting of a parabolic system of two partial differential equations, complemented by Neumann homogeneous boundary conditions and initial conditions. The system arises from a model of two-species phase segregation
on an atomic lattice [22]; it consists of the balance equations of microforces and microenergy; the two unknowns are the order parameter rho and the chemical potential mu. Some recent results obtained for this class of problems is reviewed and, in the case of a nonconstant and nonlinear atom mobility, uniqueness and continuous dependence on the initial data are shown with the help of a new line of
argumentation developed in [12].
We consider viscoelastic solids undergoing thermal expansion and exhibiting hysteresis effects due to plasticity or phase transformations. Within the framework of generalized standard solids, the problem is described in a 3D setting by the momentum equilibrium equation, the flow rule describing the dependence of the stress on the strain history, and the heat transfer equation. Under appropriate regularity assumptions on the data, a local existence result for this thermodynamically consistent system is established, by combining existence results for ordinary differential equations in Banach spaces with a fixed-point argument. Then global estimates are obtained by using both the classical energy estimate and more specific techniques for the heat equation introduced by Boccardo and Gallouet. Finally a global existence result is derived.
The Stefan problem is coupled with a spatially inhomogeneous and anisotropic Gibbs-Thomson condition at the phase boundary. We show the long-time existence of weak solutions for the non-degenerate Stefan problem with a
spatially inhomogeneous and anisotropic Gibbs-Thomson law and a conditional existence result for the corresponding degenerate Stefan problem. To this end, approximate solutions are constructed by means of variational problems
for energy functionals with spatially inhomogeneous and anisotropic interfacial energy. By passing to the limit, we establish solutions of the Stefan problem with a spatially inhomogeneous and anisotropic Gibbs--Thomson law in a weak generalized BV-formulation.
Uncertainty is inevitable when solving science and engineering application problems. In the face of
uncertainty, it is essential to determine robust and risk-averse solutions. In this work,
we consider a class of PDE-constrained optimization problems in which the PDE coefficients
and inputs may be uncertain. We introduce two approximations for minimizing the
conditional value-at-risk for such PDE-constrained optimization problems. These approximations are based
on the primal and dual formulations of the conditional value-at-risk. For the primal problem,
we introduce a smooth approximation of the conditional value-at-risk in order to utilize
derivative-based optimization algorithms and to take advantage of the convergence properties
of quadrature-based discretizations. For this smoothed conditional value-at-risk, we prove
differentiability as well as consistency of our approximation. For the dual problem, we
regularize the inner maximization problem, rigorously derive optimality conditions, and demonstrate
the consistency of our approximation. Furthermore, we propose a fixed-point iteration that takes
advantage of the structure of the regularized optimality conditions and provides a means of calculating
worst-case probability distributions based on the given probability level. We conclude with numerical
results.
This paper is concerned with the distributed optimal control of a
time-discrete Cahn--Hilliard/Navier--Stokes system with variable
densities.
It focuses on the double-obstacle potential which yields an optimal
control problem for a family of coupled systems in each time instance of a
variational inequality of fourth order and the Navier--Stokes equation.
By proposing a suitable time-discretization, energy estimates are proved
and the existence of solutions to the primal system and of optimal
controls is established for the original problem as well as for a family
of regularized problems. The latter correspond to Moreau--Yosida type
approximations of the double-obstacle potential. The consistency of these
approximations is shown and first order optimality conditions for the
regularized problems are derived. Through a limit process, a stationarity
system for the original problem is established which is related to a
function space version of C-stationarity.
With symmetric local absorbing boundary conditions for the Helmholtz equation scattering problems can be solved on a truncated domain, where the outgoing radiation condition is approximated by a Dirichlet-to-Neumann map with higher tangential derivatives on its outer boundary. Feng's conditions are symmetric local absorbing boundary conditions, which are based on an asymptotic expansion of the coefficients of the exact Dirichlet-to-Neumann map for large radia of the circular outer boundary. In this article we analyse the well-posedness of variational formulations with symmetric local absorbing boundary conditions in general and show how the modelling error introduced by Feng's conditions depends on the radius of the truncated domain.
Adaptive Numerical Solution of Eigenvalue Problems arising from Finite Element Models. AMLS vs. AFEM
(2015)
We discuss adaptive numerical methods for the solution of eigenvalue problems arising either
from the finite element discretization of a partial differential equation (PDE) or from discrete finite element modeling.
When a model is described by a partial differential equation, the adaptive finite element method
starts from a coarse finite element mesh which, based on a posteriori error estimators, is adaptively refined
to obtain eigenvalue/eigenfunction approximations of prescribed accuracy. This method is well established for classes of elliptic PDEs,
but is still in its infancy for more complicated PDE models.
For complex technical systems, the typical approach is to directly derive finite element models
that are discrete in space and are combined with macroscopic models to describe certain phenomena like damping or friction.
In this case one typically starts with a fine uniform mesh and computes eigenvalues and eigenfunctions using
projection methods from numerical linear algebra that are often combined with the algebraic multilevel
substructuring to achieve an adequate performance.
These methods work well in practice but their convergence and error analysis is rather difficult.
We analyze the relationship between these two extreme approaches. Both approaches have their pros and cons which are discussed in detail.
Our observations are demonstrated with several numerical examples.
This paper deals with the effect of generic but structured low rank perturbations on the Jordan structure and sign
characteristic of matrices that have structure in an indefinite inner product space.
The paper is a follow-up of earlier papers in which the effect of rank one perturbations
was considered. Several results that are in contrast to the case of unstructured low rank
perturbations of general matrices are presented here.
In large-area Organic Light-Emitting Diodes (OLEDs) spatially inhomogeneous luminance at high power due to inhomogeneous current flow and electrothermal feedback can be observed. To describe these self-heating effects in organic semiconductors we present a stationary thermistor model based on the heat equation for the temperature coupled to a p-Laplace-type equation for the electrostatic potential with mixed boundary conditions. The p-Laplacian describes the non-Ohmic electrical behavior of the organic material. Moreover, an Arrhenius-like temperature dependency of the electrical conductivity is considered.
We introduce a finite-volume scheme for the system and discuss its relation to recent network models for OLEDs. In two spatial dimensions we derive a priori estimates for the temperature and the electrostatic potential and prove the existence of a weak solution by Schauder's fixed point theorem.
The numerical simulation of the band structure of three-dimensional dispersive metallic photonic crystals with face-centered cubic lattices leads to large-scale nonlinear eigenvalue problems, which are very challenging due to a high dimensional subspace associated with the eigenvalue zero and the fact that the desired eigenvalues (with smallest real part) cluster near the zero eigenvalues. For
the solution of the eigenvalue problem, a Newton-type iterative method is proposed and the nullspace-free method is applied to exclude the zero eigenvalues from the associated generalized eigenvalue problem. To find the successive eigenvalue/eigenvector pairs, we propose a new non-equivalence deflation method to transform converged eigenvalues to infinity, while all other eigenvalues remain unchanged. The deflated problem is then solved by the same Newton-type method, which uses a hybrid method that combines the Jacobi-Davidson, the shift-invert residual Arnoldi and nonlinear Arnoldi methods to compute the clustered eigenvalues. Numerical results illustrate that the method is robust even for the case of computing many eigenvalues in very large problems.
Several classes of optimal control of electromagnetic fields are considered. Special emphasis is
laid on a non-standard $H$-based formulation of the equations of electromagnetism in multiply connected conductors. By this technique, the Maxwell equations can be solved with reduced computational complexity. While the magnetic field $H$ in the conductor is obtained from an elliptic equation
with the $\curl \sigma^{-1} \curl$ operator, an elliptic equation with the $\div \mu \nabla$ operator is set up for a potential $\psi$ in the isolator.
Both equations are coupled by appropriate interface conditions. In all problems, the
electrical current is controlled in the conducting domain. Several types of control functions are discussed. In particular, the problem of sparse optimal control is investigated in a package of electrical wires. For all problems, the associated sensitivity
analysis is performed.
A survey of methods from numerical linear algebra for linear constant coefficient differential-algebraic equations (DAEs) and descriptor control systems is presented. We discuss numerical methods to check the solvability properties of DAEs as well as index reduction and regularization techniques. For descriptor systems we discuss controllability and observability properties and how these can be checked numerically. These methods are based on staircase forms and derivative arrays, transformed with real orthogonal transformations that are discussed in detail. Then we use the reformulated problems in several control applications for differential-algebraic equations ranging from regular and singular linear-quadratic optimal and robust control to dissipativity checking. We discuss these applications and give a systematic overview over the theory and the numerical solution methods. In particular, we show that all these applications can be treated with a common approach that is based on the computation of eigenvalues and deflating subspaces of even matrix pencils. The unified approach allows to generalize and improve several techniques that are currently in use in systems and control.
The efficient and reliable computation of guided modes in photonic crystal wave-guides is of great importance for designing optical devices. Transparent boundary conditions based on Dirichlet-to-Neumann operators allow for an exact computation of well-confined modes and modes close to the band edge in the sense that no modelling error is introduced. The well-known super-cell method, on the other hand, introduces a modelling error which may become prohibitively large for guided modes that are not well-confined. The Dirichlet-to-Neumann transparent boundary conditions are, however, not applicable for all frequencies as they are not uniquely defined and their computation is unstable for a countable set of frequencies that correspond to so called Dirichlet eigenvalues. In this work we describe how to overcome this theoretical difficulty introducing Robin-to-Robin transparent boundary conditions whose construction do not exhibit those forbidden frequencies. They seem, hence, well suited for an exact and reliable computation of guided modes in photonic crystal wave-guides.
Regularization and Numerical Solution of the Inverse Scattering Problem using Shearlet Frames
(2014)
Regularization techniques for the numerical solution of nonlinear inverse scattering
problems in two space dimensions are discussed. Assuming that the boundary of a scatterer is its most prominent feature, we exploit as model the class of cartoon-like functions.
Since functions in this class are asymptotically optimally sparsely approximated by shearlet frames, we consider shearlets as a means for the regularization in a Tikhonov method.
We examine both directly the nonlinear problem and a linearized problem obtained by
the Born approximation technique. As problem classes we study the acoustic inverse
scattering problem and the electromagnetic inverse scattering problem. We show that
this approach introduces a sparse regularization for the nonlinear setting and we present
a result describing the behavior of the local regularity of a scatterer under linearization,
which shows that the linearization does not affect the sparsity of the problem. The analytical results are illustrated by numerical examples for the acoustic inverse scattering problem that highlight the effectiveness of this approach.
An eigenvalue perturbation theory under rank-one perturbations is developed for classes
of real matrices that are symmetric with respect to a non-degenerate bilinear form,
or Hamiltonian with respect to a non-degenerate skew-symmetric form.
In contrast to the case of complex matrices, the sign characteristic is a crucial feature
of matrices in these classes. The behavior of the sign characteristic under generic
rank-one perturbations is analyzed in each of these two classes of matrices.
Partial results are presented, but some questions remain open. Applications
include boundedness and robust boundedness for solutions of structured systems
of linear differential equations with respect to general perturbations as well
as with respect to structured rank perturbations of the coefficients.
Using a standard first-order optimality condition for nonsmooth optimization problems, a general framework for a descent method is developed. This setting is applied to a class of mathematical programs with equilibrium constraints in function space from which a new algorithm is derived. Global convergence of the algorithm is demonstrated in function space and the results are then illustrated by numerical experiments.
We derive formulae for the second-order subdifferential of polyhedral norms. These formulae are fully explicit in terms of initial data. In a first step we rely on the explicit formula for the coderivative of normal cone mapping to polyhedra. Though being explicit, this formula is quite involved and difficult to apply. Therefore, we derive simple formulae for the 1-norm and - making use of a recently obtained formula for the second-order subdifferential of the maximum function - for the maximum norm.
In this paper we present an efficient algorithm for the calculation of photonic crystal band structures and band structures of photonic crystal waveguides. Our method relies on the fact that the dispersion curves of the band structure are smooth functions of the quasi-momentum in the one-dimensional Brillouin zone. We show the derivation and computation of the group velocity, the group velocity dispersion, and any higher derivative of the dispersion curves. These derivatives are then employed in a Taylor expansion of the dispersion curves. We control the error of the Taylor expansion with the help of a residual estimate and introduce an adaptive scheme for the selection of nodes in the one-dimensional Brillouin zone at which we solve the underlying eigenvalue problem and compute the derivatives of the dispersion curves. The proposed algorithm is not only advantageous as it decreases the computational effort to compute the band structure but also because it allows
for the identification of crossings and anti-crossings of dispersion curves, respectively. This identification is not possible with the standard approach of solving the underlying eigenvalue problem at a discrete set of values of the quasi-momentum without taking the mode parity into account.
Structured eigenvalue backward errors of matrix pencils and polynomials with palindromic structures
(2014)
We derive formulas for the backward error of an approximate eigenvalue of a *-palindromic
matrix polynomial with respect to *-palindromic perturbations. Such formulas are also obtained
for complex T-palindromic pencils and quadratic
polynomials. When the T-palindromic polynomial is real, then we derive the backward error
of a real number considered as an approximate eigenvalue of the matrix polynomial with
respect to real T-palindromic perturbations.
In all cases the corresponding minimal structure preserving perturbations are obtained as well.
The results are illustrated by numerical experiments. These show that there is
significant difference between the backward errors with respect to structure
preserving and arbitrary perturbations in many cases.
A mechanical equilibrium problem for a material consisting of two components with dierent densities is considered. Due to the heterogeneous material densities, the
outer shape of the underlying workpiece can be changed by shifting the interface between
the subdomains. In this paper, the problem is modeled as a shape design problem for optimally compensating unwanted workpiece changes. The associated control variable is
the interface. Regularity results for transmission problems are employed for a rigorous
derivation of suitable first-order optimality conditions based on the speed method. The paper concludes with several numerical results based on a spline approximation of the
interface.
Multi-valued network models can be described by their topology and a set of parameters capturing the effects of the regulators for each component. Dynamics can then be derived and represented as state transition systems.
Different network models may lead to the same transition system, meaning dynamics analysis of a representative model covers a larger class of models. While rather clear in the Boolean case, the properties contributing to this effect become more involved for multi-valued models. We analyse these properties and present a mathematical description of the resulting model equivalence classes.
In this paper a new theorem is formulated
which allows a rigorous proof of the shape differentiability without the usage of the material derivative; the domain expression is automatically obtained and the boundary expression is easy to derive.
Furthermore, the theorem is applied to a cost function which depends on a quasi-linear transmission
problem. Using a Gagliardo penalization the existence of optimal shapes is established.
A coupling of discrete and continuous optimization to solve kinodynamic motion planning problems
(2014)
This paper studies the relationship between the material derivative method, the shape derivative method, the min-max formulation of Correa and Seeger, and the Lagrange method introduced by Cea. A theorem is formulated
which allows a rigorous proof of the shape differentiability without the usage of material derivative;
the domain expression is automatically obtained and the boundary expression is easy to derive.
Furthermore, the theorem is applied to a cost function which depends on a quasi-linear transmission
problem. Using a Gagliardo penalization the existence of optimal shapes is established.
An algorithm to detect collisions between robots moving along given trajectories is presented. The method is a combination of the adaptive
dynamic collision checking developed by Schwarzer et al. and Lin and Canny's algorithm, which computes efficiently the distance between two polyhedra. The resulting algorithm is part of a global model that computes the optimal task assignment, sequencing and kinodynamic
motion planning in a robotic work-cell.
Two optimal control problems for instationary magnetization
processes are considered in 3D spatial domains that
include electrically conducting and nonconducting regions. The magnetic
fields are generated by induction coils. In the first model, the induction coil
is considered as part of the conducting region and the electrical current is taken
as control. In the second, the coil is viewed as part of the nonconducting region and the
electrical voltage is the control. Here, an integro-differential equation accounts
for the magnetic induction law that couples the given
electrical voltage with the induced electrical current in the
induction coil.
We derive first-order necessary
optimality condition for the optimal controls of both problems. Based on them,
numerical methods of gradient type are applied. Moreover, we report on the application
of model reduction by POD that lead to tremendous savings. Numerical tests are
presented for academic 3D geometries but also for a real-world application.
We study the fundamental problem of scheduling bidirectional traffic across machines arranged on a path. The main feature of the problem is that jobs traveling in the same direction can be scheduled in quick succession on a machine, while jobs in the other direction have to wait for an additional transit time. We show that this tradeoff makes the problem significantly harder than the related flow shop problem, by showing that it is NP-hard even for jobs with identical processing and transit times. We give polynomial algorithms for a single machine and any constant number of machines. In contrast, we show the problem to be NP-hard on a single machine and with identical processing and transit times if some pairs of jobs in different directions are allowed to run on the machine concurrently. We generalize a PTAS of Afrati et al. [1999] for one direction and a single machine to the bidirectional case on any constant number of machines.
The analysis of adaptive finite element methods in practice immediately leads to eigenvalue clusters which requires the simultaneous marking in adaptive finite element methods. A first analysis for multiple eigenvalues of the recent work [Dai, He, Zhou, arXiv Preprint 1210.1846v2] introduces an adaptive method whose marking strategy is based on the element-wise sum of local error estimator contributions for multiple eigenvalues. This paper proves optimality of a practical adaptive algorithm for eigenvalue clusters for the eigenvalues of the Laplace operator in terms of nonlinear approximation classes. All estimates are explicit in the initial mesh-size, the eigenvalues and the cluster width to clarify the dependence of the involved constants.
For regular matrix pencils the distance in norm to the nearest singular pencil
under low rank perturbation is studied. Characterizations of this distance are derived via the Weyl function of the perturbation. Special attention is paid to the Hermitian pencil case.
Estimates for the distance of a given pencil to the set of singular pencils are obtained.
A Branch-Cut-And-Price Algorithm for a Combined Buy-at-Bulk Network Design Facility Location Problem
(2014)
In the combined buy-at-bulk network design facility location
problem we are given an undirected network with a set of potential facilities and a set of clients with demands. In addition, we are also provided a set of cable types with each cable type having a capacity and cost per unit length. The cost to capacity ratio decreases from large to small
cables following economies of scale. A network planner is expected to determine a set of facilities to open and install cables along the edges of the network in order to route the demands of the clients to some open facility. The capacities of the installed cable must be able to support the demands of the clients routed along that edge.The objective is to minimize the cost that is paid for opening facilities and installing cables. We model the problem as an integer program and propose a branch-cut-and-price algorithm for solving it. We study the effect of two family of valid inequalities that naturally emerge from the model. We present the results of our implementation that were tested on a set of large real world instances.
Asymptotic behavior is often of particular interest when analyzing asynchronous Boolean networks representing biological systems such as signal transduction or gene regulatory networks. Methods based on a generalization of the steady state notion, the so-called symbolic steady states, can be exploited to investigate attractor properties as well as for model reduction techniques conserving attractors. In this paper, we propose a novel optimization-based method for computing all maximal symbolic steady states and motivate their use. In particular, we add a new result yielding a lower bound for the number of cyclic attractors and illustrate the methods with a short study of a MAPK pathway model.
Constraint-based modeling of genome-scale metabolic network reconstructions has become a widely used approach in computational biology. Flux coupling analysis is a constraint-based method that analyses the impact of single reaction knockouts on other reactions in the network.We present an extension of flux coupling analysis for double and multiple gene or reaction knockouts, and develop corresponding algorithms for an in silico simulation. To evaluate our method, we perform a full single and double knockout analysis on a selection of genome-scale metabolic network reconstructions and compare the results.
Flux coupling analysis (FCA) has become a useful tool for aiding metabolic reconstructions and guiding genetic manipulations. Originally, it was introduced for constraint-based models of metabolic networks that are based on the steady-state assumption. Recently, we have shown that the steady-state assumption can be replaced by a much weaker lattice-theoretic property related to the supports of metabolic fluxes. In this paper, we further extend our approach and delevelop an efficient algorithm for general qualitative flux coupling analysis (QFCA). We illustrate our method by thermodynamic flux coupling analysis (tFCA), which allows studying steady-state metabolic models with loop-law thermodynamic constraints. These models do not satisfy the lattice-theoretic properties required in our previous work. For a selection of genome-scale metabolic network reconstructions, we discuss both theoretically and practically, how thermodynamic constraints strengthen the coupling results that can be obtained with classical FCA.
Transitive reductions and minimal equivalent subgraphs have proven to be a powerful concept to simplify networks and to measure their redundancy. Here we consider a generalization of the minimal equivalent subgraph problem where a set of arcs is already given. For two digraphs D = (V,A), D′ = (V,A′) with A′ ⊆ A, we ask for the minimal set of edges of D that have to be added to D′ such that the transitive closure of D equals the transitive closure of D′.
We present a method to compute such an extension and show that if D is transitively closed, this problem can be solved in polynomial time.
The long standing problem is discussed of how to deflate the part associated with the eigenvalue infinity in a structured matrix pencil using structure preserving unitary transformations. We derive such a deflation procedure and apply this new technique to symmetric, Hermitian or alternating pencils and in a modified form to (anti)-palindromic pencils. We present a detailed error and perturbation analysis of this and other deflation procedures and demonstrate the properties of the new algorithm with several numerical examples.
We discuss Möbius transformations for general matrix polynomials over arbitrary
elds, analyzing their in
uence on regularity, rank, determinant, constructs such as compound
matrices, and on structural features including sparsity and symmetry. Results on
the preservation of spectral information contained in elementary divisors, partial multiplicity
sequences, invariant pairs, and minimal indices are presented. The eect on canonical
forms such as Smith forms and local Smith forms, on relationships of strict equivalence
and spectral equivalence, and on the property of being a linearization or quadratication
are investigated. We show that many important transformations are special instances
of Möbius transformations, and analyze a Möbius connection between alternating and
palindromic matrix polynomials. Finally, the use of Möbius transformations in solving
polynomial inverse eigenproblems is illustrated.
This paper focuses on
rate-independent damage in elastic bodies. Since the driving energy is nonconvex,
solutions may have jumps as a function of time, and in this situation it is known that the classical concept
of energetic solutions for rate-independent systems
may fail to accurately describe the
behavior of the system at jumps.
Therefore, we resort to the (by now well-established) vanishing viscosity approach to rate-independent modeling
and approximate the model by its viscous regularization.
In fact, the analysis of the latter PDE system presents
remarkable difficulties, due to its highly nonlinear character.
We tackle it by combining a variational approach to a class of abstract doubly nonlinear evolution equations, with
careful regularity estimates tailored to this specific system relying on a q-Laplacian type gradient regularization of the damage variable.
Hence, for the viscous problem we conclude the existence of weak solutions satisfying a
suitable energy-dissipation inequality that is the starting point for the vanishing viscosity analysis.
The latter leads to the notion of (weak) parameterized
solution to our rate-independent system,
which encompasses the influence of viscosity in the description of the jump regime.
We study the approximation of Wasserstein gradient structures
by their finite-dimensional analog. We show that simple
finite-volume discretizations of the linear Fokker-Planck
equation exhibit the recently established entropic gradient-flow
structure for reversible Markov chains. Then we reprove the
convergence of the discrete scheme in the limit of vanishing
mesh size using only the involved gradient-flow structures.
In particular, we make no use of the linearity of the equations
nor of the fact that the Fokker-Planck equation is of second order.
Spectral deferred correction methods for solving stiff ODEs are known to
converge rapidly towards the collocation limit solution on equidistant grids,
but show a much less favourable contraction on non-equidistant grids such as
Radau-IIa points. We interprete SDC methods as fixed point iterations for the
collocation system and propose new DIRK-type sweeps for stiff problems based
on purely linear algebraic considerations. Good convergence is recovered also
on non-equidistant grids. The properties of different variants are explored on
a couple of numerical examples.
The well-known structure theorem of Hadamard-Zol\'esio states that the derivative of a shape functional is a distribution on the boundary of the domain depending only on the normal perturbations of a smooth enough boundary. However a volume representation (distributed shape derivative) is more general than the boundary form and allows to work with shapes having a lower regularity.
It is customary in the shape optimization literature to assume regularity of the domains and use the boundary expression of the shape derivative for numerical algorithm. In this paper we describe the numerous advantages of the distributed shape derivative in terms of generality, easiness of computation and numerical implementation. We give several examples of numerical applications such as the inverse conductivity problem and the level set method.
For the solution of optimal control problems governed by nonlinear parabolic PDEs, methods working on the reduced objective functional are often employed to avoid a full
spatio-temporal discretization of the problem. The evaluation of the reduced gradient requires one solve of the state equation forward in time, and one backward solve of
the adjoint equation. The state enters into the adjoint equation, requiring the storage of a full 4D data set. If Newton-CG methods are used, two additional trajectories
have to be stored. To get numerical results which are accurate enough, in many case very fine discretizations in time and space are necessary, which leads to a significant
amount of data to be stored and transmitted to mass storage. Lossy compression methods were developed to overcome the storage problem by reducing the accuracy of the stored
trajectories. The inexact data induces errors in the reduced gradient and reduced Hessian. In this paper, we analyze the influence of such a lossy trajectory compression
method on Newton-CG methods for optimal control of parabolic PDEs and design an adaptive strategy for choosing appropriate quantization tolerances.
Elementary flux mode (EM) analysis is an important tool in the constraint-based analysis of genome-scale metabolic networks. Due to the combinatorial complexity of these networks, as well as the advances in the level of detail to which they can be reconstructed, an exhaustive enumeration of all EMs is often not practical. Therefore, in recent years interest has shifted towards searching EMs with specific properties. We present a novel method that allows computing EMs containing a given set of target reactions. This generalizes previous algorithms where the set of target reactions consists of a single reaction. In the one-reaction case, our method compares favorably to the previous approaches. In addition, we present several applications of our algorithm for computing EMs containing two target reactions in genome-scale metabolic networks.
Resolving thin conducting sheets for shielding or even skin layers inside by the mesh of numerical methods like the finite element method (FEM) can be avoided by using impedance transmission conditions (ITCs). Those ITCs shall provide an accurate approximation for small sheet thicknesses $d$, where the accuracy is best possible independent of the conductivity or the frequency being small or large -- this we will call robustness. We investigate the accuracy and robustness of popular and recently developed ITCs, and propose robust ITCs which are accurate up to $O(d^2)$.
We consider multiscale Hamiltonian systems in which harmonic oscillators with several high frequencies are coupled to a slow system. It is shown that the oscillatory energy is nearly preserved over long times eps^{-N} for arbitrary N>1, where eps^{-1} is the size of the smallest high frequency. The result is uniform in the frequencies and does not require non-resonance conditions.
Sobolev stability of plane wave solutions to the cubic nonlinear Schrödinger equation on a torus
(2013)
It is shown that plane wave solutions to the cubic nonlinear Schrödinger equation on a torus behave orbitally stable under generic perturbations of the initial data that are small in a high-order Sobolev norm, over long times that extend to arbitrary negative powers of the smallness parameter. The perturbation stays small in the same Sobolev norm over such long times. The proof uses a Hamiltonian reduction and transformation and, alternatively, Birkhoff normal forms or modulated Fourier expansions in time.
Coarsening in solder alloys is a widely accepted indicator for
possible failure of joints in electronic devices.
Based on the well-established Cahn--Larch\'e model
with logarithmic chemical energy density (see, e.g., Dreyer and Mueller 2001),
we present a numerical environment for the efficient
and reliable simulation of coarsening in binary alloys.
Main features are adaptive mesh refinement based on hierarchical error estimates,
fast and reliable algebraic solution by multigrid and Schur--Newton multigrid methods,
and the quantification of the coarsening speed by the temporal growth of mean phase radii.
We provide a detailed description and a numerical assessment of the algorithm and its different components,
together with a practical application to a eutectic AgCu brazing alloy.
We investigate the convergence of an implicit Voronoi finite volume
method for reaction-diffusion problems including nonlinear diffusion
in two space dimensions. The model allows to handle heterogeneous
materials and uses the chemical potentials of the involved species as
primary variables. The numerical scheme uses boundary conforming Delaunay
meshes and preserves positivity and the dissipative property of the
continuous system. Starting from a result on the global stability of
the scheme (uniform, mesh-independent global upper and lower bounds),
we prove strong convergence of the chemical activities and their gradients
to a weak solution of the continuous problem. In order to illustrate the
preservation of qualitative properties by the numerical scheme, we present
a long-term simulation of the Michaelis-Menten-Henri system. Especially,
we investigate the decay properties of the relative free energy and the
evolution of the dissipation rate over several magnitudes of time, and
obtain experimental orders of convergence for these quantities.
In this work we present a complete algorithm for the exact computation of the guided mode band structure in photonic crystal (PhC) wave-guides. In contrast to the supercell method, the used approach does not introduce any modelling error and is hence independent of the confinement of the modes. The approach is based on Dirichlet-to-Neumann (DtN) transparent boundary conditions that yield a nonlinear eigenvalue problem. For the solution of this nonlinear eigenvalue problem we present a direct technique using Chebyshev interpolation that requires a band gap calculation of the PhC in advance. For this band gap calculation –- we introduce as a very efficient tool –- a Taylor expansion of the PhC band structure. We show that our algorithm –- like the supercell method –- converges exponentially, however, its computational costs –- in comparison to the supercell method –- only increase moderately since the size of the matrix to be inverted remains constant.
In high accuracy numerical simulations and optimal control of time-dependent processes, often both many time steps and fine spatial discretizations are needed. Adjoint gradient computation, or post-processing of simulation results, requires the storage of the solution trajectories over the whole time, if necessary together with the adaptively refined spatial grids. In this paper we discuss various techniques to reduce the memory requirements, focusing first on the storage of the solution data, which typically are double precision floating point values. We highlight advantages and disadvantages of the different approaches. Moreover, we present an algorithm for the efficient storage of adaptively refined, hierarchic grids, and the integration with the compressed storage of solution data.
A Fenchel dualization scheme for the one-step time-discretized contact problem of quasi-static
elasto-plasticity with kinematic or isotropic hardening is considered. The associated path is induced
by a combined Moreau-Yosida / Tichonov regularization of the dual problem.
The sequence of solutions to the regularized problems is shown to converge strongly to the optimal
displacement-stress-strain triple of the original elasto-plastic contact problem in the space-continuous setting.
This property relies on the density of the intersection of certain convex sets which is shown as well.
It is also argued that the mappings associated with the resulting problems are Newton- or slantly differentiable.
Consequently, each regularized subsystem can be solved mesh-independently at a local
superlinear rate of convergence. For efficiency purposes, an inexact path-following approach is proposed and
a numerical validation of the theoretical results is given.
The inverse eigenvalue problem for $T$-alternating matrix polynomials over arbitrary
algebraically closed fields of characteristic different from two is considered.
The main result shows that the necessary conditions obtained in \cite{MacMMM10} for a matrix
polynomial to be the Smith form of a $T$-alternating matrix polynomial are under mild
conditions also sufficient to be the Smith form of a $T$-alternating matrix polynomial with
invertible leading coefficient which is additionally in anti-triangular form.. In particular, this result
implies that any $T$-alternating matrix polynomial with invertible leading coefficient is
equivalent to a $T$-alternating matrix polynomial in anti-triangular form that has the
same finite and infinite elementary divisors as the original matrix polynomial.
Finally, the inverse eigenvalue problem for $T$-palindromic matrix polynomials is
considered excluding the case that both $+1$ and $-1$ are eigenvalues.
In this paper, we introduce a high order finite element (FEM) implementation using perfectly matched layer (PML) for the scattering by plasmonic structures inside layered media. The PML is proven to be very accurate and efficient by a comparative analysis with a commercial FEM software and the Multiple Multipole Program (MMP). A convergence analysis using hp-adaptive refinement inside the PML layer
shows that adaptive mesh refinement inside the PML layer is most efficient. Based on this convergence analysis an hp-strategy is proposed, which shows a remarkable error reduction for small additional computational costs.
Shielding sheets are commonly used in the protection of electronic devices. With their large aspect ratios they become a serious issue for the direct application of boundary element methods due to the occurring almost singular integrals. Impedance transmission conditions allow for boundary element formulations where only sheet mid-line has to be triangulated. We propose and analyse boundary element methods of second kind for impedance transmission conditions of two different types for the time-harmonic eddy current problem in two dimensions. In numerical experiments we study the effect on the magnetic shielding efficiency of the discretisation error due the boundary element discretisation and the modelling error due to the
impedance transmission condition.
We study the exact recovery of signals from quantized frame coefficients. Here, the basis of the quantization
is hard thresholding, and we present a simple algorithm for the recovery of reconstructable signals. The set of
non-reconstructable signals is shown to be star-shaped and symmetric with respect to the origin. Moreover, we
provide a criterion on the frame for the boundedness of this set. In this case, we also give a priori bounds.
According to the Helmholtz decomposition,
the irrotational parts of the momentum balance equations of
the incompressible Navier-Stokes equations are balanced by the
pressure gradient.
Unfortunately, nearly all mixed methods for incompressible flows
violate this fundamental property, resulting in the well-known
numerical instability of poor mass conservation.
The origin of this problem is the
lack of $L^2$-orthogonality between discretely divergence-free velocities
and irrotational vector fields.
In order to cure this,
a new variational crime using divergence-free
velocity reconstructions is proposed.
Applying lowest order Raviart-Thomas velocity reconstructions
to the nonconforming Crouzeix-Raviart element
allows to construct
a cheap flow discretization for general 2d and 3d
simplex meshes that possesses the same
advantageous robustness properties like divergence-free flow
solvers.
In the Stokes case,
optimal a-priori error estimates for the velocity gradients
and the pressure are derived. Moreover, the discrete velocity
is independent of the continuous pressure.
Several detailed linear and nonlinear
numerical examples illustrate the theoretical findings.
A basic task in signal analysis is to character-
ize data in a meaningful way for analysis and classification
purposes. Time-frequency transforms are powerful strategies
for signal decomposition, and important recent generalizations
have been achieved in the setting of frame theory. In parallel
recent developments, tools from algebraic topology, traditionally
developed in purely abstract settings, have provided new insights
in applications to data analysis. In this report, we investigate some
interactions of these tools, both theoretically and with numerical
experiments, in order to characterize signals and their frame
transforms. We explain basic concepts in persistent homology
as an important new subfield of computational topology, as well
as formulations of time-frequency analysis in frame theory. Our
objective is to use persistent homology for constructing topo-
logical signatures of signals in the context of frame theory. The
motivation is to design new classification and analysis methods by
combining the strength of frame theory as a fundamental signal
processing methodology, with persistent homology as a new tool
in data analysis.
Primal heuristics are an important component of state-of-the-art codes for mixed integer nonlinear programming (MINLP). In this article we give a compact overview of primal heuristics for MINLP that have been suggested in the literature of recent years. We sketch the fundamental concepts of different classes of heuristics and discuss specific implementations. A brief computational experiment shows that primal heuristics play a key role in achieving feasibility and finding good primal bounds within a global MINLP solver.
Enforcing solvability of a nonlinear matrix equation and estimation of multivariate ARMA time series
(2013)
The matrix equation $X+AX^{-1}A^T=B$, arising in parameter estimation of certain time series models,
is solvable only for certain values of the matrices $A,B$.
We present a numerical method to modify $A,B$ in order to make the matrix equation solvable.
Since solvability depends on the location of the eigenvalues of the palindromic matrix polynomial $\lambda^2 A+\lambda B+A^T$,
our method works by moving those eigenvalues to specified locations using first order spectral perturbation theory.
The method is heuristic but works in practice, as is supported by several compelling numerical examples.
These examples arise from parameter estimation of a common time series model, the multivariate ARMA(1,1).
We consider a general class of continuous asset price models where the drift and the volatility functions, as well as the driving Brownian motions, change at a random time. Under minimal assumptions on the random time and on the driving Brownian motions, we study the behavior of the model in all the filtrations which naturally arise in this setting, establishing martingale representation results and characterizing the validity of the NA1 and NFLVR no-arbitrage conditions.
We consider the design of a passive optical telecommunication access network, where clients have to be connected to an intermediate level of distribution points (DPs) and further on to some central offices (COs) in a tree-like fashion. Each client demands a given number of fiber connections to its CO. Passive optical splitters installed at the DPs allow k connections to share a single common fiber between the DP and the CO. We consider fixed charge costs for the use of an edge of the underlying street network, of a DP, and of a CO and variable costs for installing fibers along the street edges and for installing splitters at the DPs. We present two Lagrangian decomposition approaches that decompose the problem based on the network structure and on the cost structure, respectively. The subproblems are solved using MIP techniques. We report computational results for realistic instances and compare the efficiency of the Lagrangian approaches to the solutions of an integrated MIP model.
Motivation. Modelling, parameter identification, and simulation play an important role in systems biology. Usually, the goal is to determine parameter values that minimise the difference between experimental measurement values and model predictions in a least-squares sense. Large-scale biological networks, however, often suffer from missing data for parameter identification. Thus, the least-squares problems are rank-deficient and solutions are not unique. Many common optimisation methods ignore this detail because they do not take into account the structure of the underlying inverse problem. These algorithms simply return a “solution” without additional information on identifiability or uniqueness. This can yield misleading results, especially if parameters are co-regulated and data are noisy.
Results. The Gauss-Newton method presented in this paper monitors the numerical rank of the Jacobian and converges locally, for the class of adequate problems, to a solution that is unique within the subspace of identifiable parameters. This method has been implemented in BioPARKIN, a software package that combines state-of-the-art numerical algorithms with compliance to system biology standards, most importantly SBML, and an accessible interface.
Availability. The software package BioPARKIN is available for download at http://bioparkin.zib.de .
A basic task in signal analysis is to character-
ize data in a meaningful way for analysis and classification
purposes. Time-frequency transforms are powerful strategies
for signal decomposition, and important recent generalizations
have been achieved in the setting of frame theory. In parallel
recent developments, tools from algebraic topology, traditionally
developed in purely abstract settings, have provided new insights
in applications to data analysis. In this report, we investigate some
interactions of these tools, both theoretically and with numerical
experiments, in order to characterize signals and their frame
transforms. We explain basic concepts in persistent homology
as an important new subfield of computational topology, as well
as formulations of time-frequency analysis in frame theory. Our
objective is to use persistent homology for constructing topo-
logical signatures of signals in the context of frame theory. The
motivation is to design new classification and analysis methods by
combining the strength of frame theory as a fundamental signal
processing methodology, with persistent homology as a new tool
in data analysis.
We derive a formula for the backward error of a complex number $\lambda$ when considered as an approximate eigenvalue
of a Hermitian matrix pencil or polynomial with respect to Hermitian perturbations. The same are also obtained for approximate
eigenvalues of matrix pencils and polynomials with related structures like skew-Hermitian, $*$-even and $*$-odd.
Numerical experiments suggest that in many cases there is a significant difference between the backward
errors with respect to perturbations that preserve structure and those with respect to arbitrary perturbations.
An existence result is proved for a nonlinear diffusion problem of phase-field type, consisting of a parabolic system of two partial differential equations, complemented by Neumann homogeneous boundary conditions and initial
conditions. This system is meant to model two-species phase segregation on an atomic lattice under the presence of diffusion. A similar system has been recently
introduced and analyzed in [3]. Both systems conform to the general theory developed in [5]: two parabolic PDEs, interpreted as balances of microforces and microenergy,
are to be solved for the order parameter rho and the chemical potential mu. In the system studied in this note, a phase-field equation in rho fairly more general than in [3] is coupled with a highly nonlinear diffusion equation for mu, in which the conductivity coefficient is allowed to depend nonlinearly on both variables.
Global existence and uniqueness for a singular/degenerate Cahn-Hilliard system with viscosity
(2013)
Existence and uniqueness are investigated for a nonlinear diffusion problem of phase-field type, consisting of a parabolic system of two partial differential equations, complemented by Neumann homogeneous boundary conditions and initial conditions. This system aims to model two-species phase segregation on an atomic lattice [19]; in the balance equations of microforces and microenergy, the two
unknowns are the order parameter rho and the chemical potential mu. A simpler version of the same system has recently been discussed in [8]. In this paper, a fairly more general phase-field equation for rho is coupled with a genuinely nonlinear diffusion equation for mu. The existence of a global-in-time solution is proved with the help of suitable a priori estimates. In the case of constant atom mobility, a new and rather unusual uniqueness
proof is given, based on a suitable combination of variables.
We are concerned with a nonstandard phase field model of
Cahn-Hilliard type. The model, which was introduced by Podio-Guidugli (Ric. Mat. 2006), describes two-species phase segregation and consists of a system of two highly nonlinearly coupled PDEs. It has been recently investigated
by Colli, Gilardi, Podio-Guidugli, and Sprekels in a series of papers: see, in particular, SIAM J. Appl. Math. 2011,
and Boll. Unione Mat. Ital. 2012. In the latter contribution, the authors can treat the very general case in which the diffusivity coefficient of the parabolic PDE
is allowed to depend nonlinearly on both variables. In the same framework, this paper investigates the asymptotic limit of the solutions to the initial-boundary value problems as the diffusion coefficient sigma in the equation governing the evolution of the order parameter tends to zero. We prove that such a limit actually exists and solves the limit problem, which couples a nonlinear PDE of parabolic type with an ODE accounting for the phase dynamics. In the case of a constant diffusivity, we are able to show uniqueness and to improve the regularity of the solution.
The present note deals with a nonstandard systems of differential equations describing a two-species phase segregation. This system naturally arises in the asymptotic analysis carried out recently by the same authors,
as the diffusion coefficient in the equation governing
the evolution of the order parameter tends to zero. In particular, an existence result has been proved for the limit system in a very general framework. On the contrary, uniqueness was shown by assuming a constant mobility coefficient. Here, we generalize this result and prove
a continuous dependence property in the case that the mobility coefficient suitably depends on the chemical potential.
In this paper we propose a time discretization of a system of two parabolic equations describing diffusion-driven atom rearrangement in crystalline matter. The equations express the balances of microforces and microenergy; the two phase fields are the order parameter and the chemical potential. The initial and boundary-value problem for the evolutionary system is known to be well posed. Convergence of the discrete scheme to the solution of the continuous problem is proved by a careful development of uniform estimates, by weak compactness and a suitable treatment of
nonlinearities. Moreover, for the difference of discrete
and continuous solutions we prove an error estimate of
order one with respect to the time step.
We study the incremental facility location problem, wherein we are given an instance of the uncapacitated facility location problem. We seek an incremental sequence of opening facilities and an incremental sequence of serving customers along with their fixed assignments to facilities open in the partial sequence. Our aim is to have the solution obtained for serving the first l customers in the sequence be competitive with the optimal solution to serve any l customers. We provide an incremental framework that provides an overall competitive factor of 8 and a worst case instance that provides the lower bound of 3. The problem has applications in multi-stage network planning.
We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for nding its solution. Finally, we report computational results.
In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of innite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities suce to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.
We consider a generalization of the connected facility location problem where the clients must be connected to the open facilities via shared capacitated (tree) networks instead of independent shortest paths. This problem arises in the planning of ber optic telecommunication access networks, for example. Given a set of clients with positive demands, a set of potential facilities with opening costs, a set of capacitated access cable types, and a core cable type of innite capacity, one has to decide which facilities to open, how to interconnect them using a Steiner tree of innite capacity core cables, and which access cable types to install on which potential edges such that these edges form a forest and the installed capacities suce to simultaneously route the client demands to the open facilities via single paths. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for problem instances where the access cable types obey economies of scale. In the special case where only multiples of a single cable type can be installed on the access edges, a variant of our algorithm achieves a performance guarantee of 6.72.
This paper presents efficient computational techniques for solving an optimization problem in cardiac defibrillation governed by the monodomain equations. Time-dependent electrical currents injected at different spatial positions act as the control. Inexact Newton-CG methods are used, with reduced gradient computation by adjoint solves. In order to reduce the computational complexity, adaptive mesh refinement for state and adjoint equations is performed. To reduce the high storage and bandwidth demand imposed by adjoint gradient and Hessian-vector evaluations, a lossy compression technique for storing trajectory data is applied. An adaptive choice of quantization tolerance based on error estimates is developed in order to ensure convergence. The efficiency of the proposed approach is demonstrated on numerical examples.
In this paper a condition number for linear-quadratic two-stage stochastic optimization problems is introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probability distribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivative of this multifunction, the condition number can be estimated from above explicitly in terms of the problem data by applying appropriate calculus rules. Here, a chain rule for the extended partial second-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role. The obtained results are illustrated for the example of two-stage stochastic optimization problems with simple recourse.
The chemical master equation is a fundamental equation in chemical kinetics. It is an adequate substitute for the classical reaction-rate equations whenever stochastic effects become relevant. In the present paper we give a simple argument showing that the solutions of a large class of chemical master equations, including all those in which elementary reactions between two and more molecules do not generate a larger number of molecules than existed before,
are bounded in weighted $\ell_1$-spaces. As an illustration for the implications of this kind of regularity we analyze the effect of truncating the state space. This leads to an error analysis of the finite state projection of the chemical master equation, an approximation that underlies many numerical methods.
A mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraints
(2013)
We illustrate the solution of a mixed-integer stochastic nonlinear optimization problem in an application of power management. In this application, a coupled system consisting of a hydro power station and a wind farm is considered. The objective is to satisfy the local energy demand and sell any surplus energy on a spot market for a short time horizon. Generation of wind energy is assumed to be random, so that demand satisfaction is modeled by a joint probabilistic constraint taking into account the multivariate distribution. The turbine is forced to either operate between given positive limits or to be shut down. This introduces additional binary decisions. The numerical solution procedure is presented and results are illustrated.
We present new residual estimates based on Kato's square root theorem for spectral approximations of diagonalizable non-self-adjoint differential operators of convection-diffusion-reaction type. These estimates are incorporated as part of an hp-adaptive finite element algorithm for practical spectral computations, where it is shown that the
resulting a posteriori error estimates are reliable. Provided experiments demonstrate the efficiency and reliability of our approach.
The huge number of elementary flux modes (EFM) in genome-scale metabolic networks makes analysis based on elementary flux modes intrinsically difficult. However, it has been shown that the elementary flux modes with optimal yield often contain highly redundant information. The set of optimal-yield elementary flux modes can be compressed using modules. Up to now, this compression was only possible by first enumerating the whole set of all optimal-yield elementary flux modes.
We present a direct method for computing modules of the thermodynamically constrained optimal flux space of a metabolic network. This method can be used to decompose the set of optimal-yield elementary flux modes in a modular way and to speed up their computation. In addition, it provides a new form of coupling information that is not obtained by classical flux coupling analysis. We illustrate our approach on a set of model organisms.
Constraint-based analysis of metabolic networks has become a widely used approach in computational systems biology.
In the simplest form, a metabolic network is represented by a stoichiometric matrix and thermodynamic information on the irreversibility of certain reactions.
Then one studies the set of all steady-state flux vectors satisfying these stoichiometric and thermodynamic constraints.
We introduce a new lattice-theoretic framework for the computational analysis of metabolic networks, which focuses on the support of the flux vectors,
i.e., we consider only the qualitative information whether or not a certain reaction is active, but not its specific flux rate.
Our lattice-theoretic view includes classical metabolic pathway analysis as a special case, but turns out to be much more flexible and general,
with a wide range of possible applications.
We show how important concepts from metabolic pathway analysis, such as blocked reactions, flux coupling, or elementary modes, can be generalized to arbitrary lattice-based models. We develop corresponding general algorithms and present a number of computational results.