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)
Mixed-integer two-stage stochastic programs with fixed recourse matrix, random recourse costs, technology matrix, and right-hand sides are considered. Quantitative continuity properties of its optimal value and solution set are derived when the underlying probability distribution is perturbed with respect to an appropriate probability metric.
We show how time-dependent optimal control for partial differential equations can be realized in a modern high-level modeling and simulation package. We summarize the general formulation for distributed and boundary control for initial-boundary value problems for parabolic PDEs and derive the optimality system including the adjoint equation. The main difficulty therein is that the latter has to be integrated backwards in time. This implies that complicated implementation effort is necessary to couple state and adjoint equations to compute an optimal solution. Furthermore a large amount of computational effort or storage is required to provide the needed information (i.e the trajectories) of the state and adjoint variables. We show how this can be realized in the modeling and simulation package COMSOL MULTIPHYSICS, taking advantage of built-in discretization, solver and post-processing technologies and thus minimizing the implementation effort. We present two strategies: The treatment of the coupled optimality system in the space-time cylinder, and the iterative approach by sequentially solving state and adjoint system and updating the controls. Numerical examples show the elegance of the implementation and the efficiency of the two strategies.
Let $\lambda$ be a nonderogatory eigenvalue of $A \in \C^{n \times
n}$. The sensitivity of $\lambda$ with respect to matrix
perturbations
$A \leadsto A+\Delta,\Delta \in \DD$, is measured by the structured
condition number $\kappa_\DD(A,\lambda)$. Here $\DD$ denotes the set
of admissible perturbations. However, if $\DD$ is not a vector space
over $\C$ then $\kappa_\DD(A,\lambda)$ provides only incomplete
information about the mobility of $\lambda$ under small
perturbations from $\DD$. The full
information is then given by a certain set $K_\DD(x,y)\subset \C$
which depends on $\DD$ and
a pair of normalized right and left eigenvectors $x,y$. In this paper
we study the sets $K_\DD(x,y)$ and obtain methods for computing
them.
In particular we show that $K_\DD(x,y)$ is an ellipse in some
important cases.
$\mu$-values and spectral value sets for linear perturbation classes defined by a scalar product
(2007)
We study the variation of the spectrum of matrices
under perturbations which are self- or skew-adjoint
with respect to a scalar product.
Computable formulae are given for the associated
$\mu$-values. The results can be used to calculate spectral value
sets for the perturbation classes under consideration.
We discuss the special case of
complex Hamiltonian perturbations of a Hamiltonian matrix in detail.
Stochastic optimization techniques are highly relevant for applications in electricity production and trading since, in particular after the deregulations of many electricity markets, there is a high number of uncertainty factors (e.g., demand, spot prices) to be considered that can be described reasonably by statistical models. Here, we want to highlight two aspects of this approach: scenario tree approximation and risk aversion. The former is a procedure to replace a general statistical model (probability distribution), which makes the optimization problem intractable, suitably by a finite discrete distribution (scenarios). This is typically an indispensable first step towards a solution of a stochastic optimization model. On the other hand, this is a highly sensitive concern, in particular if dynamic decision structures are involved (multistage stochastic programming). Then, the approximate distribution must exhibit tree structure. Moreover, it is of interest to get by with a moderate number of scenarios to have the resulting problem tractable. In any case, it has to be relied on suitably stability results to ensure that the obtained results are indeed related to the original (infinite dimensional) problem. These stability results involve probability distances and, for the multistage case, a filtration distance that evaluates the information increase over time. We present respective approximation schemes relying on Monte Carlo sampling and scenario reduction and combining techniques. The second topic of this talk is risk aversion. Namely, we present the approach of polyhedral risk measures which are given as (the optimal values of) certain simple stochastic programs. Well-known risk measures such as CVaR and expected polyhedral utility belong to this class and, moreover, multiperiod risk measures for multistage stochastic programs are suggested. For stochastic programs incorporating polyhedral risk measures it has been shown that numerical tractability as well as stability results known for classical (non-risk-averse) stochastic programs remain valid. In particular, the same scenario approximation methods can be used. Finally, we present illustrative numerical results from an electricity portfolio optimization model for a municipal power utility.
In a companion paper [Matheon-Preprint 403] we introduced an abstract definition of a parallel and adaptive hierarchical grid for scientific computing. Based on this
definition we derive an efficient interface specification as a set of C++ classes.
This interface separates the applications from the grid data structures.
Thus, user implementations become independent of the underlying grid
implementation. Modern C++ template techniques are used to provide an
interface implementation without big performance losses.
The implementation is realized as part of the
software environment DUNE.
Numerical tests demonstrate the flexibility and the efficiency of our approach.
A Generic Grid Interface for Parallel and Adaptive Scientific Computing. Part I: Abstract Framework
(2007)
We give a mathematically rigorous definition of a grid for algorithms solving
partial differential equations. Unlike previous approaches, our grids have a
hierarchical structure. This makes them suitable for geometric multigrid
algorithms and hierarchical local grid refinement. The description is also
general enough to include geometrically nonconforming grids. The definitions
in this article serve as the basis for an implementation of an abstract grid
interface as C++ classes in the DUNE.
A class of optimal control problems for a semilinear parabolic partial differential equation
with control and mixed control-state constraints is considered.
For this problem, a projection formula is derived
that is equivalent to the necessary optimality
conditions. As main result, the superlinear convergence of a semi-smooth Newton method is shown.
Moreover we show the numerical treatment and several numerical experiments.
In this paper we present the new numerical algorithm GEOMS for the numerical integration of the most general form of the equations of motion of multibody systems, including nonholonomic constraints and possible redundancies in the constraints, as they may appear in industrial applications. Besides the numerical integration it offers some additional features like stabilization of the model equations, use of different decomposition strategies, or checking and correction of the initial values with respect to their consistency. Furthermore, GEOMS preserves hidden constraints and (possibly) existing solution invariants if they are provided as equations.
We will also demonstrate the performance and the applicability of GEOMS for two mechanical examples of different degrees of complexity.
We consider the magnetization dynamics in the presence of a spin torque as induced by a polarized current. The dynamic response is of significant importance in magnetic multilayers and spintronic applications. Based on the Landau-Lifshitz-Gilbert equation
we investigate the possibility of Hopf bifurcations at isolated stationary
points that give rise to periodic solutions, so-called precessional states.
We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost
installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context,
helping to increase the dual bound and to reduce the optimality gaps.
We consider the problem of automatically extracting simplified models out of complex high-dimensional and time-dependent data. The simplified model is given by a linear Langevin equation with time-varying coefficients. The reduced model may still be high-dimensional, but it is physically intuitive and much easier to interpret than the original data. In particular we can distinguish whether certain dynamical effects are influenced by friction, noise, or systematic drift.
The parameters for the reduced model are obtained by a robust and efficient numerical predictor-corrector scheme which relies on analytical solutions to a maximum-likelihood problem provided the time steps between successive observations are not too large. Our approach emphasizes the specific hypoelliptic structure of the Langevin equation given high-dimensional observation data, and therefore can be considered as complemetary to the procedure recently proposed in \emph{Horenko et al. (submitted SIAM MMS, 2007)} by one of the authors, or to the problem of incomplete (one-dimensional) observations \emph{Pokern et al. (submitted to JRSSB, 2007)}. If the data set is very heterogeneous the time series is better described not by a single model, but by a collection of reduced models. This scenario is accounted for by embedding the parameter estimation procedure into the framework of hidden Markov models which it is particularly suited to treat high-dimensional data. That is, we decompose the data into several subsets, each of which gives rise to an appropriate linear Langevin model, where the switching between the local model is done by a Markov jump process. The optimal decomposition into submodels can then be regarded as one global Langevin model with piecewise constant coefficients. We illustrate the performance of the algorithm by means of several examples. Especially we focus on the numerical error as a function of the time step of the observation sequence.
We present a formal procedure for structure-preserving model reduction of linear second-order control problems. Second-order equations appear in a variety of physical contexts, e.g., vibromechanical systems or electrical circuit design to mention just a few. However typical balanced truncation methods that project onto the subspace of the largest Hankel singular values fail to preserve the problem's physical structure and may suffer from lack of stability. In this paper we adopt the framework of port-Hamiltonian systems that covers the class of relevant problems and that allows for a generalization of balanced truncation to second-order problems. We explore two possible routes to truncation of a balanced port-Hamiltonian system: one is by imposing holonomic constraints, the other one proceeds by a singular perturbation argument using an explicit scaling of the small Hankel singular values. In both cases the reduced system turns out to be port-Hamiltonian. Moreover the procedure preserves stability and passivity. For the singularly perturbed system we prove convergence of the corresponding transfer functions.
We address the problem of computing canonical ensembles of Hamiltonian systems that are subject to holonomic constraints. For this purpose we introduce a hybrid Monte-Carlo scheme that allows for sampling configurational expectation values in the canonical ensemble without bias, proving ergodicity for the proposed scheme. In doing so, we extend recent ideas of Canc\`es \emph{et al.} (\emph{M2AN, Vol. 41, No. 2, pp. 351-389, 2007}) who could prove a law of large numbers for unconstrained molecular systems with a separable Hamiltonian employing a least-action principle. The sampling scheme is illustrated by means of calculating the free energy profile of a small peptide.
Lyapunov and exponential dichotomy spectral theory is extended
from ordinary differential equations (ODEs) to nonautonomous
differential-algebraic equations (DAEs). By using orthogonal
changes of variables, the original DAE system is transformed into
appropriate condensed forms, for which concepts such as Lyapunov
exponents, Bohl exponents, exponential dichotomy and spectral
intervals of various kinds can be analyzed via the resulting
underlying ODE. Some essential differences between the spectral
theory for ODEs and that for DAEs are pointed out. Numerical
methods for computing the spectral intervals associated with
Lyapunov and Sacker-Sell (exponential dichotomy) spectra are
derived by modifying and extending those methods proposed for ODEs. Perturbation theory and error analysis are discussed, as
well. Finally, some numerical examples are presented to illustrate
the theoretical results and the properties of the numerical
methods.
A state-constrained optimal control problem with nonlocal radiation interface conditions arising from the modeling of crystal growth processes is considered. The problem is approximated by a Moreau-Yosida type regularization. Optimality conditions for the regularized problem are derived and the convergence of the regularized problems is shown. In the last part of the paper, some numerical results are presented.
We consider a control- and state-constrained optimal control problem
governed by a semilinear
elliptic equation with nonlocal interface conditions.
These conditions occur during the
modeling of diffuse-gray conductive-radiative heat transfer.
The nonlocal radiation interface condition and the pointwise state-constraints
represent the particular features of this problem. To deal with the
state-constraints, continuity of the state is shown which allows to
derive first-order necessary conditions. Afterwards, we establish second-order
sufficient conditions that account for strongly active sets and
ensure local optimality in an $L^2$-neighborhood.
Polyhedral discrepancies are relevant for the quantitative stability
of mixed-integer two-stage and chance constrained stochastic programs. We
study the problem of optimal scenario reduction for a discrete probability
distribution with respect to certain polyhedral discrepancies and develop
algorithms for determining the optimally reduced distribution approximately.
Encouraging numerical experience for optimal scenario reduction is provided.
As an alternative to Newton's method an approach based on singularity
theory can be exploited for computing a simple eigenvalue and corresponding
eigenvectors of a nonnormal matrix $A$ in a stable way, see
[Schwetlick/L\"osche, 2000].
In the paper it is shown by constructing a counterexample with an singular
singularity system, that a straightforward extension of this technique
to the computation of invariant subspaces of dimension $p>1$
will not work, in general. The finding of this counterexample required a
detailed study of the linear block singularity operator.
We investigate the convexity of chance constraints with independent random variables. It will be shown, how concavity properties of the mapping related to the decision vector have to be combined with a suitable property of decrease for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels. It turns out that the required decrease can be verified for most prominent density functions. The results are applied then, to derive convexity of linear chance constraints with normally distributed stochastic coefficients when assuming independence of the rows of the coefficient matrix.
The perturbation and ADAE index of a degenerated hyperbolic system modelling a heat exchanger
(2007)
The heat exchanger in a heat pump can be modelled by the zero Mach-number limit of the Euler equations of compressible fluid flow. This system turns out to be a coupled hyperbolic/parabolic equation with coupled, time-dependent boundary conditions. Using the theory of abstract differential-algebraic equations it is shown that the frozen coefficient system has ADAE index 1. Moreover, the much stronger result is proven that the system has time-perturbation index one and space-perturbation index two even in the case of time-dependent boundary conditions. The results are stated in terms of the original physical variables. The estimates agree well with numerical experiments.
The asymptotic convergence behavior of cyclic versions of the nonsymmetric Jacobi algorithm for the
computation of the Schur form of a general complex matrix is investigated.
Similar to the symmetric case, the nonsymmetric Jacobi algorithm proceeds by applying a
sequence of rotations that annihilate a pivot element in the strict lower triangular
part of the matrix until convergence to the Schur form of the matrix is
achieved.
In this paper, it is shown that the cyclic nonsymmetric Jacobi method converges
locally and asymptotically quadratically under mild hypotheses if special ordering
schemes are chosen, namely ordering schemes that lead to so-called northeast directed sweeps.
The theory is illustrated by the help of numerical experiments. In particular, it is shown that
there are ordering schemes that lead to asymptotic quadratic convergence for the cyclic symmetric
Jacobi method, but only to asymptotic linear convergence for the cyclic nonsymmetric
Jacobi method. Finally, a generalization of the nonsymmetric Jacobi method
to the computation of the Hamiltonian Schur form for Hamiltonian matrices is introduced
and investigated.
We propose a model reduction method for positive systems that ensures the positivity of the reduced model. For both, continuous-time and discrete-time systems, our approach is based on constructing diagonal solutions of Lyapunov inequalities. These are linear matrix inequalities (LMIs), which are shown to be feasible. Stability is preserved and an error bound in the $\mathcal{H}_\infty$-norm is provided.
For modeling and analyzing regulatory networks based on qualitative information and possibly additional temporal constraints, approaches using hybrid automata can be very helpful. The formalism focussed on in this paper starts from the logical description developed by R. Thomas to capture network structure and qualitative behavior of a system. Using the framework of timed automata, the analysis of the dynamics can be refined by adding a continuous time evolution. This allows for the incorporation of data on time delays associated with specific processes. In general, structural aspects such as character and strength of interactions as well as time delays are context sensitive in the sense that they depend on the current state of the system. We propose an enhancement of the approach described above, integrating both structural and temporal context sensitivity.
We discuss the eigenvalue problem for
general and structured matrix polynomials which may
be singular and may have eigenvalues at infinity.
We derive staircase
condensed forms that allow deflation of the infinite eigenvalue and
singular structure of the matrix polynomial.
The remaining reduced order staircase form leads to
new types of linearizations which determine the finite eigenvalues and
and corresponding eigenvectors. The new linearizations
also simplify the construction of structure preserving linearizations.
A Lavrentiev type regularization technique for
solving elliptic boundary control problems with pointwise state
constraints is considered. The main concept behind this
regularization is to look for controls in the range of the adjoint
control-to-state mapping. After investigating the analysis of the
method, a semismooth Newton method based on the optimality
conditions is presented. The theoretical results are confirmed by
numerical tests. Moreover, they are validated by comparing the
regularization technique with standard numerical codes based on the
discretize-then-optimize concept.
A state-constrained optimal boundary control problem governed by a linear elliptic equation is considered. In order to obtain the optimality conditions for the solutions to the model problem, a Slater assumption has to be made that restricts the theory to the two-dimensional case. This difficulty is overcome by a source representation of the control and combined with a Lavrentiev type regularization. Optimality conditions for the regularized problem are derived, where the corresponding Lagrange multipliers have $L^2$-regularity. By the spectral theorem for compact and normal operators, the convergence result is shown. Moreover, the convergence for vanishing regularization parameter of the adjoint state associated with the regularized problem is shown. Finally, the uniform boundedness of the regularized Lagrange multipliers in $L^1(\O)$ is verified by a maximum principle argument.
In this paper we develop a QR-like algorithm for the palindromic eigenvalue problem $Ax=\lambda A^\adj x$.
We will discuss the two cases that $A^\adj$ denotes the transpose or the conjugate transpose of $A\in\C^{n,n}$.
It is shown that this so-called palindromic QR iteration is equivalent to applying the standard QR algorithm to $A^{-\adj}A$.
Also the concepts of deflation, shifting, and exploiting the invariance of a Hessenberg-type form are adapted.
Moreover, we analyze the problem of reducing a general square matrix to the mentioned Hessenberg-type form
and establish analogies to the Hamiltonian eigenvalue problem.
Finally, we present concrete Hessenberg-type reduction algorithms for special cases.
We investigate a thermomechanical model of phase transitions in steel. The strain is assumed to be additively decomposed into an
elastic and a thermal part as well as a contribution from transformation induced plasticity. The resulting model can be viewed
as an extension of quasistatic linear thermoelasticity. We prove existence of a unique solution and conclude with some numerical simulations.
Numerical methods for palindromic eigenvalue problems: Computing the anti-triangular Schur form
(2007)
We present structure-preserving numerical methods
for complex palindromic polynomial eigenvalue problems
via corresponding palindromic linearizations.
A key ingredient is the development of an appropriate condensed form ---
the anti-triangular Schur form.
Ill-conditioned problems which have eigenvalues near the unit circle,
in particular near +/-1, are discussed.
We show how a combination of unstructured methods
followed by a structured refinement can be used
to solve such problems very accurately.
Let H_d(n, p) signify a random d-uniform hypergraph with n vertices in which each of the possible edges is present with probability p = p(n) independently, and let H_d(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of H_d(n, p) and H_d(n,m). As an application, we obtain an asymptotic formula for the probability that H_d(n, p) is connected, and a corresponding formula for H_d(n,m). In addition, we infer a local limit theorem for the conditional distribution of the number of edges in H_d(n, p) given that H_d(n, p) is connected. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.
The purpose of this paper is the analysis of dynamic iteration methods for
the numerical integration of coupled systems of ODEs and DAEs.
We will investigate convergence of these methods and put special emphasis
on the {\sc Jacobi}- and {\sc Gauss-Seidel} methods. Furthermore, the
fundamental difference in the convergence behaviour of coupled ODEs and DAEs
is pointed out. This difference is used to explain why certain relaxation methods
for coupled DAEs may fail. Finally, a remedy to this undesirable
effect is proposed that makes use of a so-called {\em preconditioned dynamic
iteration} strategy. This regularization also allows significant reduction of
dynamic iteration steps.
Structured eigenvalue conditioning and backward error of a class of polynomial eigenvalue problems
(2007)
Characterisations of simple eigenvalues of complex matrix polynomials with *-even/odd and *-palindromic/antipalindromic structures that have the same normwise condition number with respect to structure preserving and arbitrary perturbations are obtained. Here * denotes either the transpose T or the conjugate tranpose *. In the process we obtain formulae for the normwise structured condition number of simple eigenvalues of T-palindromic/antipalindromic and *-even/odd polynomials. Moreover, conditions under which the normwise structured backward error of approximate eigenvalues of such polynomials is equal to the unstructured error are also derived. These lead to complete characterisations of approximate eigenvalues that have the same structured and unstructured backward errors for the *-even/odd and T-even/odd polynomials.
Stability and Sensitivity of Optimization Problems with First Order Stochastic Dominance Constraints
(2007)
We analyze the stability and sensitivity of stochastic optimization problems with stochastic dominance constraints of first order. We consider general perturbations of the underlying probability measures in the space of regular measures equipped with a suitable discrepancy distance. We show that the graph of the feasible set mapping is closed under rather general assumptions. We obtain conditions for the continuity of the optimal value and upper-semicontinuity of the optimal solutions, as well as quantitative stability estimates of Lipschitz type.
Furthermore, we analyze the sensitivity of the optimal value and obtain upper and lower bounds for the directional
derivatives of the optimal value. The estimates are formulated in terms of the dual utility functions associated with the
dominance constraints.
In this paper, we empirically investigate the NP-hard problem of finding sparsest solutions to linear equation systems, i.e., solutions with as few nonzeros as possible. This problem has received considerable interest in the sparse approximation and signal processing literature, recently. We use a branch-and-cut approach via the maximum feasible subsystem problem to compute optimal solutions for small instances and investigate the uniqueness of the optimal solutions. We furthermore discuss five (modifications of) heuristics for this problem that appear in different parts of the literature. For small instances, the exact optimal solutions allow us to evaluate the quality of the heuristics, while for larger instances we compare their relative performance. One outcome is that the so-called basis pursuit heuristic performs worse, compared to the other methods. Among the best heuristics are a method due to Mangasarian and a bilinear approach.
Orbitopal Fixing
(2007)
The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the order of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree.
We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving such symmetric integer programming models. We devise a linear time algorithm that,
applied at each node of the branch-and-cut tree, removes redundant parts
of the tree produced by the above mentioned symmetry. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch 2007). It does, however, not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks.
The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a network such that a giv en demand can be satisfied. There are two objectives. passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commo dity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path rou tings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam.
The fare planning problem for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a discrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands.
In this paper we consider structure-preserving model reduction of
second-order systems using a~ba\-lan\-ced truncation approach.
Several sets of singular values are introduced for such systems,
which lead to different concepts of balancing and different
second-order balanced truncation methods. We compare the
properties of these methods on numerical examples.
In this work numerical methods for the solution of two classes of structured generalized eigenvalue problems, $Ax=\lambda Bx$, are developed. Those classes are the palindromic ($B=A^T$) and the even ($A=A^T$, $B=-B^T$) eigenvalue problems.
The spectrum of these problems is not arbitrary, rather do eigenvalues occur in pairs.
We will construct methods for palindromic and even eigenvalue problems that are of cubic complexity and that are guaranteed to produce eigenvalues that are paired to working precision.
At the heart of both methods is a new URV-type matrix decomposition, that simultaneously transforms three matrices to skew triangular form, i.e., to a form that is triangular with respect to the Northeast-Southwest diagonal.
The algorithm to compute this URV decomposition uses several other methods to reduce a single square matrix to skew triangular form: the skew QR factorization and the skew QRQ$^T$ decomposition. Moreover, a method to compute the singular value decomposition of a complex, skew symmetric matrix is presented and used.
In this paper, we discuss stability properties of positive descriptor systems in the continuous-time as well as in the discrete-time case. We present different characterisations of positivity and establish generalised stability criteria for the case of positive descriptor systems. We show that if the spectral projector onto the right finite deflating subspace of the matrix pair $(E,A)$ is non-negative, then all stability criteria for standard positive systems take a comparably simple form in the positive descriptor case. Furthermore, we provide sufficient conditions that guarantee entry-wise non-negativity along with positive semi-definiteness of solutions of generalised projected Lyapunov equations. As an application of the framework established throughout this paper, we exemplarily generalise two criteria for the stability of two switched standard positive systems under arbitrary switching to the descriptor case.
Modeling several competitive leaders and followers acting in an electricity market
leads to coupled systems of mathematical programs with equilibrium constraints,
called equilibrium problems with equilibrium constraints (EPECs). We consider
a simplified model for competition in electricity markets under uncertainty of demand
in an electricity network
as a (stochastic) multi-leader-follower game. First order necessary conditions are
developed for the corresponding stochastic EPEC based on a result of Outrata.
For applying the general result an explicit representation of the co-derivative of
the normal cone mapping to a polyhedron is derived. Later the
co-derivative formula is used for verifying constraint qualifications and for identifying
$M$-stationary solutions of the stochastic EPEC if the demand is represented by a
finite number of scenarios.
Starting from the logical description of gene regulatory networks developed by R.~Thomas, we introduce an enhanced modelling approach
based on timed automata. We obtain a refined qualitative description of the dynamical behaviour by exploiting not only information on ratios of kinetic parameters related to synthesis and decay, but also constraints on the time delays associated with the operations of the system. We develop a formal framework for handling such temporal constraints using timed automata, discuss the relationship with the original Thomas formalism, and demonstrate the potential of our approach by analysing an illustrative gene regulatory network of bacteriophage~$\lambda$.
In this paper we consider the rational interpolation problem consisting in finding a rational matrix-valued function that
interpolates a given set of parameters. We briefly describe two different numerical methods for solving this problem. These are
the vector fitting and the frequency domain subspace identification method. Several numerical examples are given that compare
the properties of these methods. Furthermore, we discuss the computation of a (minimal) state space realization of a rational
function. Model order reduction methods such as modal approximation and balanced truncation are also presented. These
methods can be used to compute a reduced-order approximation of the realized dynamical system.
Lagrangian invariant subspaces for symplectic matrices play an important role in the numerical solution of discrete time, robust and optimal control problems. The sensitivity (perturbation) analysis of these subspaces, however, is a difficult problem, in particular, when the eigenvalues are on or close to some critical regions in the complex plane, such as the unit circle.
We present a detailed perturbation analysis for several different cases of real and complex symplectic matrices. We analyze stability and conditional stability
as well as the index of stability for these subspaces.
Being one of the key tools in conformation dynamics, the identification of
meta-stable states of Markov chains has been subject to extensive research in
recent years, especially when the Markov chains represent energy states of biomolecules. Some previous work on this topic involved the computation
of the eigenvalue cluster close to one, as well as the corresponding
eigenvectors and the stationary probability distribution of the associated stochastic
matrix. Later, since the eigenvalue cluster algorithm turned out to be non-robust, an optimisation approach was developed. As a possible less costly alternative, we present an SVD approach to identifying
meta-stable states of a stochastic matrix, where we only need
the second largest singular vector. We outline some theoretical background
and discuss the advantages of this strategy. Some simulated and real
numerical examples illustrate the effectiveness of the proposed algorithm.
We present a new extension of the well-known
Perron-Frobenius theorem to regular matrix pairs $(E,A)$.
The new extension is based on projector chains and is motivated from
the solution of positive differential-algebraic systems or descriptor
systems. We present several examples where the new condition holds, whereas conditions
in previous literature are not satisfied.
Passivation of LTI systems
(2007)
In this paper we consider a passivation procedure for linear time-invariant systems.
This procedure is based on the spectral properties of related Hamiltonian matrices.
We also present a structure-preserving algorithm for computing the imaginary
eigenvalues and the corresponding eigenvectors of Hamiltonian matrices.
Numerical examples are given.
Perturbation of Purely Imaginary Eigenvalues of Hamiltonian Matrices under Structured Perturbations
(2007)
We discuss the perturbation theory for purely imaginary eigenvalues of Hamiltonian matrices under Hamiltonian and non-Hamiltonian perturbations. We
show that there is a substantial difference in the behavior under these perturbations. We also discuss the perturbation of real eigenvalues of real
skew-Hamiltonian matrices under structured perturbations and use these results to analyze the properties of the URV method of computing the
eigenvalues of Hamiltonian matrices.
We review some known results for POD model reduction applied to ODEs. Then, these
results are generalized to several types of DAEs. We provide algorithms for the
model reduction and error bounds for the reduced order models. Some limits of
the approach are pointed out and alternative methods for reduced order subspace approximation
are presented. The POD approach is tested and evaluated for a medium sized DAE example
from multibody dynamics.
We propose a model for non-isothermal phase
transitions with non-conserved order parameter driven by
a spatially nonlocal free energy with respect to both the
temperature and the order parameter. The resulting system of equations
is shown to be thermodynamically consistent and to admit a strong
solution.
We prove the existence, uniqueness, thermodynamic consistency,
global boundedness from both above and below, and continuous data
dependence for a strong solution to an
integrodifferential model for nonisothermal phase transitions
under nonhomogeneous mixed boundary conditions.
The specific heat is allowed to depend on the order parameter,
and the convex component of the free energy may or may not
be singular.
In this paper, we study an optimal control problem for a singular system of partial differential equations that models a nonisothermal phase transition with a nonconserved order parameter. The control acts through a third boundary condition for the absolute temperature and plays the role of the outside temperature. It is shown that the corresponding control-to-state mapping is well defined, and the existence of an optimal control and the first-order optimality conditions for a quadratic cost functional of Bolza type are established.
Classical stability properties of solutions
that are well-known for ordinary differential
equations (ODEs) are generalized to differential-algebraic equations (DAEs).
A new test equation is derived for the analysis of numerical methods applied
to DAEs with respect to the stability of the numerical approximations.
Morevover, a stabilization technique is developed to improve the stability of classical DAE integration methods. The stability regions for these stabilized discretization methods are determined and it is shown that they much better reproduce the stability properties known for the ODE case
than in the unstabilized form.
Movies that depict the stability regions for several methods are included for interactive use.
This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.
A multistage stochastic programming approach to airline network revenue management is presented. The objective is to determine seat protection levels for all itineraries, fare classes, point of sales of the airline network and all data collection points of the booking horizon such that the expected revenue is maximized. While the passenger demand and cancelation rate processes are the stochastic inputs of the model, the stochastic protection level process represents its output and allows to control the booking process. The stochastic passenger demand and cancelation rate processes are approximated by a nite number of tree structured scenarios. The scenario tree is generated from historical data using a stability-based recursive scenario reduction scheme. Numerical results for a small hub-and-spoke network are reported.
Discrete approximations to chance constrained and mixed-integer two-stage stochastic programs require moderately sized scenario
sets. The relevant distances of (multivariate) probability
distributions for deriving quantitative stability results for such stochastic programs are $\mathcal{B}$-discrepancies, where the class $\mathcal{B}$ of Borel sets depends on their structural properties.
Hence, the optimal scenario reduction problem for such models is stated with respect to $\mathcal{B}$-discrepancies. In this paper,
upper and lower bounds, and some explicit solutions for optimal scenario reduction problems are derived. In addition, we develop
heuristic algorithms for determining nearly optimally reduced probability measures, discuss the case of the cell discrepancy (or
Kolmogorov metric) in some detail and provide some numerical experience.
We analyse stability aspects of linear multistage stochastic programs with polyhedral risk measures in the objective. In particular, we consider sensitivity of the optimal value with respect perturbations of the underlying stochastic input process. An existing stability result for multistage stochastic programs with expectation objective is carried forward to the case of polyhedral risk-averse objectives. Beside Lr-distances these results also involve filtration distances of the perturbations of the stochastic process. We discuss additional requirements for the
polyhedral risk measures such that the problem dependent filtration distances can be bounded by problem independent ones. Stability and such bounds are the basis for scenario tree approximation techniques used in practical problem solving.
We present globally convergent multigrid methods for the nonsymmetric
obstacle problems as arising from the discretization of Black–Scholes models of
American options with local volatilities and discrete data. No tuning or regularization
parameters occur. Our approach relies on symmetrization by transformation
and data recovery by superconvergence.
The paper provides a structural analysis of the feasible set defined by linear probabilistic constraints. Emphasis is laid on single (individual) probabilistic constraints. A classical convexity result by Van de Panne/Popp and Kataoka is extended to a broader class of distributions and to more general functions of the decision vector. The range of probability levels for which convexity can be expected is exactly identified. Apart from convexity, also nontriviality and compactness of the
feasible set are precisely characterized at the same time. The relation between feasible sets with negative and with nonnegative right-hand side is revealed. Finally, an existence result is formulated for the more difficult case of joint probabilistic constraints.
In this paper we lay the foundation for a numerical algorithm to
simulate high-dimensional coupled FBSDEs under weak coupling or
monotonicity conditions. In particular we prove convergence of a
time discretization and a Markovian iteration. The iteration
differs from standard Picard iterations for FBSDEs in that the
dimension of the underlying Markovian process does not increase
with the number of iterations. This feature seems to be
indispensable for an efficient iterative scheme from a numerical
point of view. We finally suggest a fully explicit numerical
algorithm and present some numerical examples with up to
10-dimensional state space.
We show that pricing a big class of relevant options by hedging
and no-arbitrage can be extended beyond semimartingale models. To
this end we construct a subclass of self-financing portfolios that
contains hedges for these options, but does not contain arbitrage
opportunities, even if the stock price process is a
non-semimartingale of some special type.
Moreover, we show that the option prices depend
essentially only on a path property of the stock price process,
viz. on the quadratic variation. As a consequence, we can
incorporate many stylized facts to a pricing model without
changing the option prices.
We study optimal control problems for general unstructured nonlinear differential-algebraic equations of arbitrary index.
In particular, we derive necessary conditions in the case of linear-quadratic control problems and extend them to the general nonlinear case.
We also present a Pontryagin maximum principle for general unstructured nonlinear DAEs in the case of restricted controls.
Moreover, we discuss the numerical solution of the resulting two-point boundary value problems and present a numerical example.
In this paper we introduce a new method for the computation of KKT matrices that arise from solving constrained, nonlinear optimization problems. This method requires updating of null-space factorizations after a low rank modification. The update procedure has the advantage that it is significantly cheaper than a re-factorization of the system at each new iterate. This paper focuses on the cheap update of a rectangular LU decomposition after a rank-1 modification.
Two different procedures for updating the LU factorization are presented in detail and compared regarding their costs of computation and their stability. Moreover we will introduce an extension of these algorithms which further improves the computation time. This turns out to be an excellent alternative to algorithms based on orthogonal transformations.
This paper concerns hyperbolic systems of two linear first-order PDEs in one space dimension with periodicity conditions in time and reflection boundary conditions in space.
The coefficients of the PDEs are supposed to be time independent, but allowed to be discontinuous with respect to the space variable. We construct two scales of Banach spaces (for the solutions and for the right hand sides of the equations, respectively) such that the problem can be modeled by means of Fredholm operators of index zero between corresponding spaces of the two scales.
The main tools of the proofs are separation of variables, integral representation of the solutions of the corresponding boundary value problems of the ODE systems and an abstract criterion for Fredholmness which seems to be new.
A primal-dual interior point method for state-constrained parabolic optimal control problems is considered. By a Lavrentiev type regularization, the state constraints are transformed to mixed control-state constraints which, after a simple transformation, can be handled as control constraints. Existence and convergence of the central path are shown. Moreover, the convergence of a short step interior point algorithm is proven in a function space setting. The theoretical properties of the algorithm are confirmed by numerical examples.
In this paper, the one-dimensional equation for the transversal vibrations of an elastoplastic beam is derived from a general
three-dimensional system. The plastic behavior is modeled using the classical
three-dimensional von Mises plasticity model. It turns out that this single-yield model leads after a dimensional reduction to a multi-yield one-dimensional hysteresis model,
given by a hysteresis operator of Prandtl-Ishlinskii type whose density
function can be determined explicitly. This result indicates that the use
of Prandtl-Ishlinskii hysteresis operators in the modeling of elastoplasticity
is not just a questionable phenomenological approach, but in fact quite natural. In addition to the derivation of the model, it is shown that the resulting partial differential equation with hysteresis can be transformed into an equivalent system for which the existence and uniqueness
of a strong solution is proved. The proof employs techniques from the mathematical theory of hysteresis operators.
Flux coupling analysis is a method to identify blocked and coupled reactions
in a metabolic network at steady state. We present a new approach to
flux coupling analysis, which uses a minimum set of generators of the steady state
flux cone. Our method does not require to reconfigure the network by splitting
reversible reactions into forward and backward reactions.
By distinguishing different types of reactions (irreversible, pseudo-irreversible,
fully reversible), we show that reaction coupling relationships can only hold
between certain reaction types. Based on this mathematical analysis, we propose
a new algorithm for flux coupling analysis.
The Bottleneck Shortest Path Problem is a basic problem
in network optimization. The goal is to determine the limiting capacity of any path between two specified vertices of the network. This is
equivalent to determining the unsplittable maximum flow between the
two vertices. In this note we analyze the complexity of the problem, its
relation to the Shortest Path Problem, and the impact of the underlying
machine/computation model.
A class of optimal control problem for a semilinear elliptic partial differential equation
with control constraints is considered. It is well known that
sufficient second-order conditions ensure the stability of optimal solutions, the convergence of
numerical methods. Otherwise, such conditions are very difficult to verify (analytically or numerically).
We will propose a new approach: Starting with a numerical solution for a fixed mesh we will
show the existence of a local minimizer of the continuous problem. Moreover, we will prove that
this minimizer satisfies the sufficient second-order conditions.
We present a new solver for large-scale two-body contact problems in nonlinear elasticity. It is based on an SQP-trust-region approach.
This guarantees global convergence to a first-order critical point of
the energy functional. The linearized contact conditions are
discretized using mortar elements. A
special basis transformation known from linear contact problems
allows to use a monotone multigrid solver for the inner quadratic programs.
They can thus be solved with multigrid complexity. Our algorithm
does not contain any regularization or penalization parameters,
and can be used for all hyperelastic material models.
The purpose of the paper is to apply monotone multigrid methods
to static and dynamic biomechanical contact problems.
In space, a finite element method involving a mortar
discretization of the contact conditions is used.
In time, a new contact--stabilized Newmark scheme is presented.
Numerical experiments for a two body Hertzian contact problem
and a biomechanical knee problem are reported.
We study a two-species interacting particle model on a subset of $\Z$
with open boundaries. The two species are injected with time
dependent rate on the left, resp.~right boundary.
Particles of different species annihilate when
they try to occupy the same site. This model has been proposed as a
simple model for the dynamics of an ``order book'' on a stock
market. We consider the hydrodynamic scaling limit for the empirical
process and prove a large deviation principle that implies
convergence to the solution of a non-linear parabolic equation.
The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an epsilon-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies.
For the solution of nonlinear equation systems
quasi-Newton methods based on low-rank updates are of particular interest. We analyze a class
of TR1 update formulas to approximate the system Jacobian. The local q-superlinear convergence for nonlinear problems is proved for a particular subclass of updates. Moreover, we give an estimate of the r-order of convergence. Numerical results comparing the TR1 method to Newton's and other quasi-Newton methods atr presented.
In this paper we discuss the numerical
solution of projected generalized Lyapunov
equations using the matrix sign function
method. Such equations arise in stability
analysis and control problems for
descriptor systems including model reduction
based on balanced truncation. It is known
that the matrix sign function method applied
to a matrix pencil $\lambda E-A$ converges
if and only if $\lambda E-A$ is of index at
most two. The convergence is quadratic if
$E$ is nonsingular, and it is linear,
otherwise. We will propose a modification
of the matrix sign function method that
converges quadratically for pencils of
arbitrary index. Numerical examples will be
presented to demonstrate the properties of
the modified method.
Quasi-Newton methods based on least change secant updating
formulas that solve linear equations $Ax=b$ in $n=\dim(x)=\dim(b)$ steps
can be expected to solve corresponding smooth nonlinear
systems $n$-step quadratically, i.e. with an $r$-order
of $\rho = 2^{1/n} = 1 + 1/n +O(1/n^2)$. The best rate one can
possibly expect on general problems is given by the positive root
$\rho_n$ of $\rho^n(\rho -1)=1$, for which
$\rho_n-1 = \ln(n)/n + O(1/n^2)$. To show that this upper bound is
actually achieved one usually has to impose a priori some kind of
linear independence condition on the sequence of steps taken by the
quasi-Newton iteration in question. Without any such assumptions we
establish in this paper the convergence order $\rho_n$ for the
two-sided rank one formula proposed by Schlenkrich et al in \cite{SGW06}.
It requires the evaluation of adjoint vectors, is invariant with respect
to linear transformations on the variable domain and combines the
properties of bounded deterioration and heredity.
An important problem of the analysis of fMRI experiments is to achieve some noise reduction of the data without blurring the shape of the activation areas. As a novel solution to this problem, the Propagation-Separation approach (PS), a structure adaptive smoothing method, has been proposed recently. PS adapts to different shapes of activation areas by generating a spatial structure corresponding to similarities and differences between time series in adjacent locations. In this paper we demonstrate how this method results in more accurate localization of brain activity. First, it is shown in numerical simulations that PS is superior over Gaussian smoothing with respect to the accurate description of the shape of activation clusters and and results in less false detections. Second, in a study of 37 presurgical planning cases we found that PS and Gaussian smoothing often yield different results, and we present examples showing aspects of the superiority of PS as applied to presurgical planning.
This paper is concerned with transparent boundary
conditions (TBCs) for the time-dependent Schrödinger equation
on a circular domain.
Discrete TBCs are introduced in the
numerical simulations of problems on unbounded domains in order to reduce
the computational domain to a finite region in order to make this problem feasible for numerical simulations.
The main focus of this article is on the
appropriate discretization of such
TBCs for the two-dimensional Schrödinger equation
in conjunction with a conservative Crank-Nicolson-type finite difference discretization.
The presented discrete TBCs yield an unconditionally stable
numerical scheme and are completely reflection-free at the boundary.
Furthermore we prove concisely the stability of the recurrence formulas used to
obtain the convolution coefficients of the new discrete TBC
for a spatially dependent potential.
In this paper we give an overview of model
order reduction techniques for coupled
systems. We consider linear time-invariant
control systems that are coupled through
input-output relations and discuss model
reduction of such systems using moment
matching and balanced truncation.
Structure-preserving approaches to model
order reduction of coupled systems are also
presented. Numerical examples are given.
Consistent Initialization and Perturbation Analysis for Abstract Differential-Algebraic Equations
(2006)
In this paper we consider linear and time-invariant
differential-algebraic equations (DAEs) $E\dot{x}(t)=Ax(t)+f(t)$,
$x(0)=x_0$, where $x(\cdot)$ and $f(\cdot)$ are functions with
values in separable Hilbert spaces $X$ and $Z$. $E:X\To Z$ is
assumed to be a bounded operator, whereas $A$ is closed and defined
on some dense subspace $D(A)$ which is in general a proper subset of
$X$. Based on a decoupling of the algebraic and the differential
part, the set of initial values being consistent with the given
inhomogeneity will be parameterized. As a consequence of these results, we
will derive estimates for the trajectory $x(\cdot)$ in dependence of the initial
state $x_0$ and the inhomogeneity $f(\cdot)$. In the theory of
differential-algebraic equations, this is commonly known as
perturbation analysis.
Roughgarden and Sundararajan recently introduced an alternative measure
of efficiency for cost sharing mechanisms.
We study cost sharing methods for combinatorial optimization problems
using this novel efficiency measure, with a particular focus on
scheduling problems. While we prove a lower bound of $\Omega(\log n)$ for a very general class of problems, we give a best possible cost sharing method for minimum makespan scheduling. Finally, we show that no budget balanced cost sharing methods for completion or flow time objectives exist.
Short term climate events such as the sea surface temperature anomaly known as El Nino are financial risk sources leading to incomplete markets. To make such risk tradable, we use a market model in which a climate index provides an extra investment opinion. Given one possible market price of risk each agent can maximize the exponential utility from three sources of income: capital market, additional security, and individual risk exposure. Under an equilibrium condition the market price of risk is uniquely determined by a backward stochastic differential equation. We translate these stochastic equations into semi-linear partial differential equations for the simulation of which numerical schemes are available. We choose two simple models for sea surface temperature, and with ENSO risk exposed fisher and farmer and a nonh-exposed bank three toy agents. By simulating their optimal investment into the climat index we obtain first insight into the dynamics of the market.
Expected suprema of a function f observed along the paths of a nice Markov process define an excessive function, and in
fact a potential if f vanishes at the boundary. Conversely, we show under mild regularity conditions that any
potential admits a representation in terms of expected suprema. Moreover, we identify the maximal and the minimal
representing function in terms of probabilistic potential theory. Our results are motivated by the work of El Karoui and
Meziou on the max-plus decomposition of supermartingales, and they provide a singular analogue to
the non-linear Riesz representation in El Karoui and Föllmer.
The possibility of controlling risk in stochastic power optimization by incorporating special risk functionals, so-called polyhedral risk measures, into the objective is demonstrated. We present an exemplary optimization model for mean-risk optimization of an electricity portfolios of a price-taking retailer. Stochasticity enters the model via uncertain electricity demand, heat demand, spot prices, and future prices. The objective is to maximize the expected overall revenue and, simultaneously, to minimize risk in terms of multiperiod risk measures, i.e., risk measures that take into account intermediate cash values in order to avoid liquidity problems at any time. We compare the effect of different multiperiod polyhedral risk measures that had been suggested in our earlier work.
An analysis of convex stochastic programs is provided if the underlying probability distribution is subjected to (small) perturbations. It is shown, in particular, that epsilon-approximate solution sets of convex stochastic programs behave Lipschitz continuous with respect to certain distances of probability distributions that are generated by the relevant integrands. It is shown that these results apply to linear two-stage stochastic programs with random recourse. Consequences are discussed on associating Fortet-Mourier metrics to two-stage models and on the asymptotic behavior of empirical estimates of such models, respectively.
By extending the stability analysis of [17] for multistage stochastic programs we show that their solution sets behave stable with respect to the sum of an Lr-distance and a filtration distance. Based on such stability results we suggest a scenario tree generation method for the (multivariate) stochastic input process. It starts with a fan of individual scenarios and consists of a recursive deletion and branching procedure which is controlled by bounding the approximation error. Some numerical experience for generating scenario trees in electricity portfolio management is reported.
This work deals with the efficient numerical solution of
the two-dimensional one-way Helmholtz equation
posed on an unbounded domain.
In this case one has to introduce
artificial boundary conditions to confine the computational domain.
Here we construct with the Z-transformation
so-called discrete transparent
boundary conditions
for higher-order parabolic equations schemes.
These methods are Pade ``Parabolic'' approximations of
the one-way Helmholtz equation
and frequently used in integrated optics and (underwater) acoustics.
We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the
columns. Special cases are packing and partitioning orbitopes, which
arise from restrictions to matrices with at most or exactly one 1-entry
in each row, respectively. The goal of investigating these polytopes is to
gain insight into ways of breaking certain symmetries in integer programs
by adding constraints, e.g., for a well-known formulation of the graph
coloring problem.
We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns
is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining
inequalities. For the cyclic group case, the descriptions turn out to be
totally unimodular, while for the symmetric group case both the description and the proof are more involved. Nevertheless, the associated
separation problem can be solved in linear time also in this case.
We consider real or complex palindromic pencils, i.e., pencils of the form $A-\lambda A^\star$,
where $A^{\star}$ denotes either the transpose $A^T$ or the conjugate transpose $A^*$.
Structured canonical forms for these pencils are derived that reveal complete spectral information.
Moreover, this canonical form is used to provide necessary and sufficient conditions for the existence of palindromic factorizations $B=A^{-\star}A$ of a given square matrix $B$.
In particular, we answer the questions when symplectic matrices allow palindromic factorization and when a matrix having a palindromic factorization is similar to a symplectic one.
We define a discrete Laplace-Beltrami operator for simplicial surfaces. It depends only on the intrinsic geometry of the surface and its edge weights are positive. Our Laplace operator is similar to the one defined by Pinkall and Polthier (the so called “cotan formula”) except that it is based on the intrinsic Delaunay triangulation of the simplicial surface. This leads to new definitions of discrete harmonic and holomorphic functions, discrete mean curvature, and discrete minimal surfaces.
We prove an existence and uniqueness theorem for weighted Delaunay triangulations (with non-intersecting site-circles) with prescribed combinatorial type and circle intersection angles. Such weighted Delaunay triangulations can also be interpreted as hyperbolic polyhedra with vertices beyond the infinite boundary. The proof is based on a variational principle. This extends similar work by Rivin on Delaunay triangulations and ideal polyhedra to weighted Delaunay triangulations and hyperideal polyhedra.
We introduce a novel method for the construction of discrete conformal mappings from surface meshes of arbitrary topology to the plane. Our approach is based on circle patterns, i.e., arrangements of circles—one for each face—with prescribed intersection angles. Given these angles the circle radii follow as the unique minimizer of a convex energy. The method supports very flexible boundary conditions ranging from free boundaries to control of the boundary shape via prescribed curvatures. Closed meshes of genus zero can be parameterized over the sphere. To parameterize higher genus meshes we introduce cone singularities at designated vertices. The parameter domain is then a piecewise Euclidean surface. Cone singularities can also help to reduce the often very large area distortion of global conformal maps to moderate levels. Our method involves two optimization problems: a quadratic program and the unconstrained minimization of the circle pattern energy. The latter is a convex function of logarithmic radius variables with simple explicit expressions for gradient and Hessian. We demonstrate the versatility and performance of our algorithm with a variety of examples.
We study various properties of a dynamic convex risk measure for bounded random variables which describe the discounted terminal values of financial positions. In particular we characterize time-consistency by a joint supermartingale property of the risk measure and its penalty function. Moreover we discuss the limit behavior of the risk measure in terms of asymptotic safety and of asymptotic precision, a property which may be viewed as a non-linear analogue of martingale convergence. These results are illustrated by the entropic dynamic risk measure.
We present a domain decomposition approach for the computation of the
electromagnetic field within periodic structures. We use a
Schwarz method with transparent boundary conditions at the interfaces of
the domains. Transparent boundary conditions are approximated by the
perfectly matched layer method (PML). To cope with Wood anomalies
appearing in periodic structures an adaptive strategy to determine
optimal PML parameters is developed. \\ We focus on the application to
typical EUV lithography line masks. Light propagation within the
multi-layer stack of the EUV mask is treated analytically. This results
in a drastic reduction of the computational costs and allows for the
simulation of next generation lithography masks
on a standard personal computer.
In this work we derive an exact discrete artificial boundary condition
for the Crank-Nicolson scheme for solving the Black-Scholes
equation for the valuation of American options.
To ensure stability and to avoid any numerical reflections
we derive the artificial boundary
condition on a purely discrete level.
Since the exact discrete artificial boundary condition
includes a convolution with respect to time
with a weakly decaying kernel, its numerical evaluation
becomes very costly for large-time simulations.
As a remedy we construct approximate artificial boundary conditions
with a kernel having the form of a
finite sum-of-exponentials, which can be evaluated in a very
efficient recursion. We prove a simple stability criteria
for the approximated artificial boundary conditions.
Finally we illustrate the
efficiency of the proposed method on several examples
and compare it to previously obtained discretized artificial boundary conditions.