Refine
Year of publication
Language
- English (1103)
- German (10)
- Multiple languages (1)
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)
Zonotopes With Large 2D Cuts
(2009)
We study the class of linear differential-algebraic m-input m-output systems
which have a transfer function with proper inverse.
A sufficient condition for the transfer function to have proper inverse
it that the system has 'strict and non-positive relative degree'.
We present two main results:
First, a so called 'zero dynamics form' is derived: this form is - within the class of system equivalence - a simple "almost normal" form of the DAE; it is a counterpart to the well-known Byrnes-Isidori form for
ODE systems with strictly proper transfer function.
The 'zero dynamics form' is exploited to characterize structural properties such as
asymptotically stable zero dynamics,
minimum phase, and high-gain stabilizability.
The zero dynamics are characterized by (A,E,B)-invariant subspaces.
Secondly, it is shown that the 'funnel controller' (that is a static nonlinear output error feedback) achieves, for all DAE systems with asymptotically stable zero dynamics and transfer function with proper inverse, tracking of a reference signal by the output signal within a pre-specified funnel. This funnel determines the transient behaviour.
The timetable is the essence of the service offered by any provider
of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the
timetable has a major impact on both operating costs and on passenger
comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two
strategies with respect to vehicle operation costs. It turns out that
for short time horizons, periodic timetabling can be suboptimal; for
sufficiently long time horizons, however, periodic timetabling can
always be done in an optimal way'.
We study a diffusion model of phase field type, consisting of
a system of two partial differential equations encoding the balances
of microforces and microenergy; the two unknowns are the order parameter
and the chemical potential. By a careful development of uniform estimates and
the deduction of certain useful boundedness properties, we
prove existence and uniqueness of a global-in-time
smooth solution to the associated initial/boundary-value problem;
moreover, we give a description of the relative $\omega$-limit set.
We prove the existence, uniqueness, regularity and smooth dependence
of the weak solution on the initial data for a certain class of semilinear first order
dissipative hyperbolic systems with spacially discontinuous coefficients. Such
kind of hyperbolic problems have succesfully been used to describe the dynamics
of distributed feedback multisection semiconductor lasers in recent years. We
show that in a suitable function space of continuous functions the weak solutions
generate a smooth semiflow.
Den kürzesten Weg in einem Graphen zu finden ist ein klassisches Problem der Graphentheorie. Über einen Vortrag zu diesem Thema beim Tag der Mathematik 2007 von R. Borndörfer kam ich in Kontakt mit dem Konrad-Zuse-Zentrum (ZIB), das sich u.a. mit Wegeoptimierung beschäftigt. Ein Forschungsschwerpunkt dort ist im Rahmen eines Projekts zur Chipverifikation das Zählen von Lösungen, das, wie wir sehen werden, eng mit dem Zählen von Wegen zusammenhängt.
Anhand von zwei Fragen aus der Graphentheorie soll diese Facharbeit unterschiedliche Lösungsmethoden untersuchen. Wie bestimmt man den kürzesten Weg zwischen zwei Knoten in einem Graphen und wie findet man alle möglichen Wege?
Nach einer Einführung in die Graphentheorie und einer Konkretisierung der Probleme wird zunächst für beide eine Lösung mit auf Graphen basierenden Algorithmen vorgestellt. Während der Algorithmus von Dijkstra sehr bekannt ist, habe ich für das Zählen von Wegen einen eigenen Algorithmus auf der Basis der Tiefensuche entwickelt.
Im zweiten Teil der Arbeit wird das Konzept der ganzzahligen Programmierung vorgestellt und die Lösungsmöglichkeiten für Wegeprobleme, die sich darüber ergeben.
In den letzten Jahren ist die Bedeutung computerunterstützter Darstellungen von Mathematik
im Lern- als auch im Forschungsbereich stark gestiegen. Obwohl bereits massive Anstrengungen
unternommen werden, die Mathematikausbildung im Ingenieursbereich durch Neue
Medien zu unterstützen und auszubauen[Mum], gibt es dennoch nur eine geringe Zahl von
Projekten, die auf die Studenten der Mathematik und Physik abzielen. Ferner beschränkten
sich viele Projekte nur auf die Verwaltung von Dokumenten, die den Lernenden — obgleich
teilweise aufgelockert durch eingestreute aktive Inhalte—zu einem passiven Konsumenten des
Lerninhaltes machen und die darum selten geeignet sind, die eigentständige, selbstgesteuerte
Auseinandersetzung mit der Materie zu fördern.
Wir präsentieren in diesem Artikel das Konzept des „Virtuellen Labors“, welches die Metapher
eines Laborpraktikums innerhalb eines Computernetzwerkes nachbildet und damit das zweite
Standbein der universitären Ausbildung in die Neuen Medien abbildet. Das Labor „Cinderella“
[KRG04] zur Untersuchung euklidischer und nicht-euklidischer Geometrie mag hier als ein
Beispiel dienen.
Wir werden im ersten Teil ein didaktisches Anforderungsprofil an derartige Labore definieren,
dann in einem zweiten Teil die sich daraus untersuchenden Konsequenzen für die Software-
Architektur darstellen und im dritten Teil ein am DFG-ForschungzentrumMATHEON der Berliner
Universitäten entwickeltes Labor für Elemente der statistischen Mechanik präsentieren.
This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers.
The classical approach to investigating polynomial eigenvalue problems is linearization, where the
polynomial is converted into a larger matrix pencil with the same eigenvalues. For any polynomial there are infinitely
many linearizations with widely varying properties, but in practice the companion forms are typically used. However,
these companion forms are not always entirely satisfactory, and linearizations with special properties may sometimes
be required.
In this paper we develop a systematic approach to generating large classes of linearizations for matrix polynomials.
Given a polynomial P, we show how to simply construct two vector spaces of pencils that generalize the companion
forms of P, and prove that almost all of these pencils are linearizations for P. Eigenvectors of these pencils are
shown to be closely related to those of P. A distinguished subspace is then isolated, and the special properties of
these pencils are investigated. These spaces of pencils provide a convenient arena in which to look for structured
linearizations of structured polynomials, as well as to try to optimize the conditioning of linearizations, issues to be
addressed in further work.
The adaptive weights smoothing (AWS) procedure was introduced in
Polzehl and Spokoiny (2000) in the context of image denoising. The
procedure has some remarkable properties like preservation of edges and
contrast, and (in some sense) optimal reduction of noise. The procedure
is fully adaptive and dimension free. Simulations with artificial images
show that AWS is superior to classical smoothing techniques especially
when the underlying image function is discontinuous and can be well
approximated by a piecewise constant function. However, the latter as-
sumption can be rather restrictive for a number of potential applications.
Here the AWS method is generalized to the case of an arbitrary local lin-
ear parametric structure. We also establish some important results about
properties of the AWS procedure including the so called "propagation
condition" and spatial adaptivity. The performance of the procedure is
illustrated by examples for local polynomial regression in univariate and
bivariate situations.
We formulate the static mechanical coupling of a geometrically exact Cosserat rod
to a nonlinearly elastic continuum. In this setting, appropriate coupling conditions have
to connect a one-dimensional model with director variables to a three-dimensional
model without directors.
Two alternative coupling conditions are proposed,
which correspond to two different configuration trace spaces.
For both we show existence of solutions of the coupled problems, using the direct
method of the calculus of variations. From the first-order optimality conditions
we also derive the corresponding conditions for the dual variables. These are
then interpreted in mechanical terms.
We consider the problem of utility maximization for small traders on incomplete
financial markets. As opposed to most of the papers dealing with this
subject, the investors’ trading strategies we allow underly constraints described
by closed, but not necessarily convex, sets. The final wealths obtained by trading
under these constraints are identified as stochastic processes which usually are
supermartingales, and even martingales for particular strategies. These strategies
are seen to be optimal, and the corresponding value functions determined
simply by the initial values of the supermartingales. We separately treat the
cases of exponential, power and logarithmic utility.
Under market frictions like illiquidity or transaction costs, contingent claims
can incorporate some inevitable intrinsic risk that cannot be completely hedged
away but remains with the holder. In general, they cannot be synthesized by
dynamical trading in liquid assets and hence not be priced by no-arbitrage arguments alone. Still, an agent can determine a valuation with respect to her
preferences towards risk. The utility indifference value for a variation in the
quantity of illiquid assets held by the agent is defined as the compensating variation
of wealth, under which her maximal expected utility remains unchanged.
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.
We consider discretizations for reaction-diffusion systems with nonlinear
diffusion in two space dimensions. The applied model allows to handle heterogeneous
materials and uses the chemical potentials of the involved species as primary variables.
We propose an implicit Voronoi finite volume discretization on regular Delaunay
meshes that allows to prove uniform, mesh-independent global upper and lower L1
bounds for the chemical potentials. These bounds provide the main step for a convergence
analysis for the full discretized nonlinear evolution problem. The fundamental
ideas are energy estimates, a discrete Moser iteration and the use of discrete
Gagliardo-Nirenberg inequalities. For the proof of the Gagliardo-Nirenberg inequalities
we exploit that the discrete Voronoi finite volume gradient norm in 2d coincides
with the gradient norm of continuous piecewise linear finite elements.
We study discrete curvatures computed from nets of curvature lines on a given smooth surface and prove their uniform convergence to smooth principal curvatures. We provide explicit error bounds, with constants depending only on properties of the smooth limit surface and the shape regularity of the discrete net.
We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem.
We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.
We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib.
We shortly review the uncoupling-coupling method, a Markov chain
Monte Carlo based approach to compute statistical properties of systems like
medium-sized biomolecules. This technique has recently been proposed for the efficient computation of biomolecular conformations. One crucial step of UC is the
decomposition of reversible nearly uncoupled Markov chains into rapidly mixing
subchains. We show how the underlying scheme of uncoupling-coupling can also be
applied to stochastic differential equations where it can be translated into a domain
decomposition technique for partial differential equations.
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.
For a system of globally pulse-coupled phase-oscillators,
we derive conditions for stability of the completely synchronous
state and all possible two-cluster states and explain
how the different states are naturally connected via
bifurcations. The coupling is modeled using the phaseresponse-
curve (PRC), which measures the sensitivity of
each oscillator’s phase to perturbations. For large systems
with a PRC, which turns to zero at the spiking threshold,
we are able to find the parameter regions where multiple
stable two-cluster states coexist and illustrate this by an
example. In addition, we explain how a locally unstable
one-cluster state may form an attractor together will its
homoclinic connections. This leads to the phenomenon
of intermittent, asymptotic synchronization with abating
beats away from the perfect synchrony.
We prove that the Random-Edge simplex algorithm requires an
expected number of at most 13n/pd pivot steps on any simple d-polytope with
n vertices. This is the first nontrivial upper bound for general polytopes. We
also describe a refined analysis that potentially yields much better bounds for
specific classes of polytopes. As one application, we show that for combinatorial
d-cubes, the trivial upper bound of 2d on the performance of Random-Edge
can asymptotically be improved by any desired polynomial factor in d.
We present a new inexact nonsmooth Newton method for the solution
of convex minimization problems with piecewise smooth, pointwise
nonlinearities. The algorithm consists of a nonlinear smoothing
step on the fine level and a linear coarse correction.
Suitable postprocessing guarantees global convergence
even in the case of a single multigrid step for each linear subproblem.
Numerical examples show that the overall efficiency
is comparable to multigrid for similar linear problems.
We present a generic non-nested Monte Carlo procedure for computing true upper bounds for Bermudan products, given an approximation of the Snell envelope. The pleonastic ``true'' stresses that, by construction, the estimator is biased above the Snell envelope. The key idea is a regression estimator for the Doob martingale part of the approximative Snell envelope, which preserves the martingale property. The so constructed martingale may be employed for computing dual upper bounds without nested simulation. In general, this martingale can also be used as a control variate for simulation of conditional expectations. In this context, we develop a variance reduced version of the nested primal-dual estimator (Anderson & Broadie (2004)) and nested consumption based (Belomestny & Milstein (2006)) methods . Numerical experiments indicate the efficiency of the non-nested Monte Carlo algorithm and the variance reduced nested one.
We use the traveling wave model for simulating and analyzing
nonlinear dynamics of complex semiconductor ring laser devices.
This modeling allows to consider temporal-spatial distributions
of the coun\-ter-pro\-pa\-ga\-ting slowly varying optical fields
and the carriers, what can be important when studying
non-homogeneous ring cavities, propagation of short pulses or fast switching.
By performing numerical integration of the model
equations we observe several dynamic regimes as well as transitions
between them. The computation of ring cavity modes explains some
peculiarities of these regimes.
A new approach to derive transparent boundary conditions (TBCs) for wave, Schrödinger, heat and drift-diffusion equations is presented. It relies on the pole condition and distinguishes between physical reasonable and unreasonable solutions by the location of the singularities of the spatial Laplace transform of the exterior solution. To obtain a numerical algorithm, a Möbius transform is applied to map the Laplace transform onto the unit disc. In the transformed coordinate the solution is expanded into a power series. Finally, equations for the coefficients of the power series are derived. These are coupled to the equation in the interior, and yield transparent boundary conditions.
Numerical results are presented in the last section, showing that the error introduced by the new approximate TBCs decays exponentially in the number of coefficients.
The pole condition approach for deriving transparent boundary conditions is extended to the time-dependent, two-dimensional case. Non-physical modes of the solution are identified by the position of poles of the solution's spatial Laplace transform in the complex plane. By requiring the Laplace transform to be analytic on some
problem dependent complex half-plane, these modes can be
suppressed. The resulting algorithm computes a finite number of coefficients of a series expansion of the Laplace transform, thereby providing an approximation to the exact boundary condition. The resulting error decays super-algebraically with the number of coefficients, so relatively few additional degrees of freedom are
sufficient to reduce the error to the level of the discretization error in the interior of the computational domain. The approach shows good results for the Schroedinger and the drift-diffusion equation
but, in contrast to the one-dimensional case, exhibits instabilities for the wave and Klein-Gordon equation. Numerical examples are shown that demonstrate the good performance in the former and the instabilities in the latter case.
In this article, we use numerical simulation to investigate transient temperature
phenomena during sublimation growth of SiC single crytals via physical
vapor transport (also called the modified Lely method). We consider the evolution
of temperatures at the SiC source and at the SiC seed crystal, which
are highly relevant to the quality of the grown crystals, but inaccessible to
direct measurements. The simulations are based on a transient mathematical
model for the heat transport, including heat conduction, radiation, and radio
frequency (RF) induction heating. Varying the position of the induction coil
as well as the heating power, it is shown that the measurable temperature difference
between the bottom and the top of the growth apparatus can usually
not be used as a simple indicator for the respective temperature difference
between SiC source and seed. Moreover, it is shown that there can be a time
lack of 1.5 hours between the heating of the temperature measuring points
and the heating of the interior of the SiC source.
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.
Building on a transformation formula that we previously found in connection with Landau-Lifshitz-Gilbert equations, we present a strategy for utilizing compensated compactness methods in the context of Ginzburg-Landau approximation for harmonic maps and related problems in magnetism and superconductivity. Its applicability is illustrated by a number of new examples.
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 present a time-dependent finite element model of the human knee joint of full 3D geometric complexity together with advanced numerical algorithms needed for its simulation. The model comprises bones, cartilage and the major ligaments, while patella and menisci are still missing. Bones are modeled by linear elastic materials, cartilage by linear viscoelastic materials, and ligaments by one-dimensional nonlinear Cosserat rods. In order to capture the dynamical contact problems correctly, we solve the full PDEs of elasticity with strict contact inequalities. The spatio--temporal discretization follows a time layers approach (first time, then space discretization). For the time discretization of the elastic and viscoelastic parts we use a new contact-stabilized Newmark method, while for the Cosserat rods we choose an energy--momentum method. For the space discretization, we use linear finite elements for the elastic and viscoelastic parts and novel geodesic finite elements for the Cosserat rods. The coupled system is solved by a Dirichlet--Neumann method. The large algebraic systems of the bone--cartilage contact problems are solved efficiently by the truncated non-smooth Newton multigrid method.
Several qualitative properties of equilibria in electrical circuits are analyzed in this paper. Specifically, non-singularity, hyperbolicity, and asymptotic stability are addressed in terms of the circuit topology, which is captured through the use of Modified Nodal Analysis (MNA) models. The differential-algebraic or semistate nature of these models drives the analysis of the spectrum to a matrix pencil setting, and puts the results beyond the ones already known for state-space models, unfeasible in many actual problems. The topological conditions arising in this qualitative study are proved independent of those supporting the index, and therefore they apply to both index-1 and index-2 configurations. The analysis combines results coming from graph theory, matrix analysis, matrix pencil theory, and Lyapunov theory for DAEs. The study is restricted to problems with independent sources; qualitative properties of circuits including controlled sources are the focus of future research.
Time-lag in Derivative Convergence Time-lag in Derivative Convergence for Fixed Point Iterations
(2004)
In an earlier study it was proven and experimentally confirmed on a 2D Euler code
that fixed point iterations can be differentiated to yield first and second order derivatives of
implicit functions that are defined by state equations. It was also asserted that the resulting
approximations for reduced gradients and Hessians converge with the same R-factor as the
underlying fixed point iteration.
A closer look reveals now that nevertheless these derivative values lag behind the functions
values in that the ratios of the corresponding errors grow proportional to the iteration counter
or its square towards infinity. This rather subtle effect is caused mathematically by the
occurrence of nontrivial Jordan blocks associated with degenerate eigenvalues. We elaborate
the theory and report its confirmation through numerical experiments.
We consider anisotropic Allen--Cahn equations with interfacial energy
induced by an anisotropic surface energy density $\gamma$.
Assuming that $\gamma$
is positive, positively homogeneous of degree one,
strictly convex in tangential directions to the unit sphere,
and sufficiently smooth, we show stability of
various time discretizations. In particular,
we consider a fully implicit and a linearized time discretization
of the interfacial energy combined with implicit
and semi-implicit time discretizations
of the double-well potential. In the semi-implicit variant,
concave terms are taken explicitly.
The arising discrete spatial problems are solved by
globally convergent truncated nonsmooth Newton multigrid methods.
Numerical experiments show the accuracy of the different
discretizations.
We also illustrate that pinch-off under anisotropic
mean curvature flow is no longer frame invariant,
but depends on the orientation of the initial configuration.
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 many couplings between parabolic systems for processes in solids can be formulated as a gradient system with respect to the total free energy or the total entropy. This includes Allen-Cahn, Cahn-Hilliard, and reaction-diffusion systems and the heat equation. For this, we write the coupled system as an Onsager system $(X,\Phi,K)$ defining the evolution $\dot{U} = -K(U)D\Phi(U)$. Here $\Phi$ is the driving functional, while the Onsager operator $K(U)$ is symmetric and positive semidefinite. If the inverse $G = K^{-1}$ exists, the triple $(X,\Phi,G)$ defines a gradient system. Onsager systems are well suited to model bulk-interface interactions by using the dual dissipation potential $\Psi^*(U,\Xi) = 1/2 <\Xi,K(U)\Xi>$. Then, the two functionals $\Phi$ and $\Psi^*$ can be written as a sum of a volume integral and a surface integral, respectively. The latter may contain interactions of the driving forces in the interface as well as the traces of the driving forces from the bulk. Thus, capture and escape mechanisms like thermionic emission appear naturally in Onsager systems, namely simply through integration by parts.
This paper deals with a three-dimensional mixture model describing materials undergoing phase transition with thermal expansion. The problem is formulated within the framework of generalized standard solids by the coupling of the momentum equilibrium equation and the flow rule with the heat transfer equation. A global solution for this thermodynamically consistent problem is obtained by using a fixed-point argument combined with global energy estimates.
We show the existence of solutions to a system of elliptic PDEs, that was recently introduced to describe the electrothermal behavior of organic semiconductor devices. Here, two difficulties appear: (i) the elliptic term in the current-flow equation is of $p(x)$-Laplacian-type with discontinuous exponent $p$, which limits the use of standard methods, and (ii) in the heat equation, we have to deal with an a priori $L^1$ term on the right hand side describing the Joule heating in the device. We prove the existence of a weak solution under very weak assumptions on the data. Our existence proof is based on Schauder’s fixed point theorem and the concept of entropy solutions for the heat equation. Here, the crucial point is the continuous dependence of the entropy solutions on the data of the problem.
We show the existence of solutions to a system of elliptic PDEs, that was recently introduced to describe the electrothermal behavior of organic semiconductor devices. Here, two diffculties appear: (i) the elliptic term in the current-flow equation is of p(x)-Laplacian type with discontinuous exponent p, which limits the use of standard methods, and (ii) in the heat equation, we have to deal with an a priori L1 term on the right hand side describing the Joule heating in the device. We prove the existence of a weak solution under very weak assumptions on the data. Our existence proof is based on Schauder’s fixed point theorem and the concept of entropy solutions for the heat equation. Here, the crucial point is the continuous dependence of the entropy solutions on the data of the problem.
This paper analyzes a model for phase
transformation in shape-memory alloys
induced by temperature changes and by
mechanical loading. We assume that the temperature is prescribed and
formulate the problem within the framework
of the energetic theory of
rate-independent processes. Existence and uniqueness results are proved.
Tree spanner problems have important applications in network design, e.g. in the telecommunications industry. Mathematically, there have been considered quite a number of maxstretch tree spanner problems and of average stretch tree spanner problems. We propose a unified notation for 20 tree spanner problems, which we investigate for graphs with general positive weights, with metric weights, and with unit weights. This covers several prominent problems of combinatorial optimization. Having this notation at hand, we can clearly identify which problems coincide. In the case of unweighted graphs, the formally 20 problems collapse to only five different problems. Moreover, our systematic notation for tree spanner problems enables us to identify a tree spanner problem whose complexity status has not been solved so far. We are able to provide an NP-hardness proof. Furthermore, due to our new notation of tree spanner problems, we are able to detect that an inapproximability result that is due to Galbiati (2001, 2003) in fact applies to the classical max-stretch tree spanner problem. We conclude that the inapproximability factor for this problem thus is 2-ε, instead of only (1+sqrt(5))/2 ~ 1.618 according to Peleg and Reshef (1999).
The weak Stratonovich integral with respect to fractional Brownian motion with Hurst parameter 1/6
(2010)
Let $B$ be a fractional Brownian motion with Hurst parameter
$H=1/6$. It is known that the symmetric Stratonovich-style Riemann sums
for $\int g(B(s))\,dB(s)$ do not, in general, converge in probability.
We show, however, that they do converge in law in the Skorohod space of
c\`adl\`ag functions. Moreover, we show that the resulting stochastic
integral satisfies a change of variable formula with a correction term
that is an ordinary It\^o integral with respect to a Brownian motion
that is independent of $B$.
The Steiner connectivity problem is a generalization of
the Steiner tree problem. It consists in finding a minimum cost set of
simple paths to connect a subset of nodes in an undirected graph.
We show that important polyhedral and algorithmic results on the
Steiner tree problem carry over to the Steiner connectivity problem,
namely, the Steiner cut and the Steiner partition inequalities, as
well as the associated polynomial time separation algorithms, can be
generalized. Similar to the Steiner tree case, a certain directed
formulation, which is stronger than the natural undirected one,
plays a central role.
We show that the spectrum of linear delay differential equations with
large delay splits into two different parts. One part, called the
strong spectrum, converges to isolated points when the delay parameter
tends to infinity. The other part, called the pseudocontinuous spectrum,
accumulates near criticality and converges after rescaling to a set
of spectral curves, called the asymptotic continuous spectrum. We
show that the spectral curves and strong spectral points provide a
complete description of the spectrum for sufficiently large delay
and can be comparatively easily calculated by approximating expressions.
We characterise the asymptotic smile and term structure of implied volatility in the Heston model at small maturities and all strikes. Using saddlepoint methods we derive a small-maturity expansion formula for call option prices, which we then transform into a closed-form expansion (including the leading-order and correction terms) for implied volatility. This refined expansion reveals the relationship between the small-expiry smile and all Heston parameters (including the pair in the volatility drift coefficient), sharpening the leading-order result of~\cite{FJ09I} which found the relationship between the zero-expiry smile and the diffusion coefficients. We solve for in/out-of-the-money and at-the-money cases; in the latter case our proof involves subleading-order saddlepoint approximation along a suitable path of integration.
We investigate the worst-case behavior of the simplex algorithm on linear programs
with 3 variables, that is, on 3-dimensional simple polytopes. Among the
pivot rules that we consider, the “random edge” rule yields the best asymptotic
behavior as well as the most complicated analysis. All other rules turn out to be
much easier to study, but also produce worse results: Most of them show essentially
worst-possible behavior; this includes both Kalai’s “random-facet” rule, which is
known to be subexponential without dimension restriction, as well as Zadeh’s deterministic
history-dependent rule, for which no non-polynomial instances in general
dimensions have been found so far.
The background for the general mathematical link between utility and information
theory investigated in this paper is a simple financial market model with two kinds of small
traders: less informed traders and insiders whose extra information is represented by an
enlargement of the other agents' filtration. The expected logarithmic utility increment,
i.e. the difference of the insider's and the less informed trader's expected logarithmic
utility is described in terms of the information drift, i.e. the drift one has to eliminate
in order to perceive the price dynamics as a martingale from the insider's perspective.
On the one hand, we describe the information drift in a very general setting by natural
quantities expressing the probabilistic better informed view of the world. This on the
other hand allows us to identify the additional utility by entropy related quantities known
from information theory. In particular in a complete market in which the insider has some
fixed additional information during the entire trading interval, its utility increment can
be represented by the Shannon information of his extra knowledge. For general markets,
and in some particular examples, we provide estimates of maximal utility by information
inequalities.
The Real Multiple Dual
(2009)
In this paper we present a dual representation for the multiple stopping
problem, hence multiple exercise options. As such it is a natural generalization of the
method in Rogers (2002) and Haugh and Kogan (2004) for the standard stopping
problem for American options. We consider this representation as the real dual as it is
solely expressed in terms of an infimum over martingales rather than an infimum over
martingales and stopping times as in Meinshausen and Hambly (2004). For the multiple
dual representation we present three Monte Carlo simulation algorithms which require
only one degree of nesting.
The PSurface Library
(2010)
We describe psurface, a C++ library that allows to store and access piecewise linear mappings between simplicial surfaces in $\R^2$ and $\R^3$. These mappings are stored in a graph data structure and can be constructed explicitly, by projection, or by surface simplification. Piecewise linear maps can be used, e.g., to construct boundary
approximations for finite element grids, and grid intersections for domain decomposition methods. In computer graphics the mappings allow to build level-of-detail representations as well as texture- and bump maps. We document the data structures and algorithms used and show how \psurface is used in the numerical analysis framework Dune
and the visualization software Amira.
Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\% on average for concrete example networks are achievable.
When simulating isolated resonators, the application of transparent boundary conditions causes the approximated spectrum to be polluted with spurious solutions. Distinguishing these artificial solutions from solutions with a physical meaning is often difficult and requires a priori knowledge of the spectrum or the expected field distribution of resonant states. We present an implementation of the pole condition that distinguishes between incoming and outgoing waves by the location of the poles of their Laplace transform as transparent boundary condition. This implementation depends on one tuning parameter. We will use the sensitivity of the computed solutions to perturbations of this parameter as a means to identify spurious solutions. To obtain global statements, we will combine this technique with a convergence monitor for the boundary condition.
The 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 periodic QR algorithm is a strongly backward stable method for computing the
eigenvalues of products of matrices, or equivalently for computing the eigenvalues of
block cyclic matrices. The main purpose of this paper is to show that this algorithm
is numerically equivalent to the standard QR algorithm. It will be demonstrated
how this connection may be used to develop a better understanding of the periodic
QR algorithm.
We propose a class of Markovian agent based models for the time evolution of a share price in an interactive market. The models rely on a microscopic description of a market of buyers and sellers who change their opinion about the stock value in a stochastic way. The actual price is determined in realistic way by matching (clearing) offers until no further transactions can be performed. Some analytic results for a non-interacting model are presented. We also propose basic interaction mechanisms and show in simulations that these already reproduce certain particular features of prices in real stock markets.
Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable
first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later.
We introduce the novel concept of an Online Target Date Assignment Problem (OnlineTDAP) as a general framework for online problems with this nature. Requests for the OnlineTDAP become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.g., an appointment with a customer for a
washing machine repair). The cost at a target date is given by the downstream cost, the optimal cost of processing all requests
at that date w.r.t. some fixed downstream offline optimization problem (e.g., the cost of an optimal dispatch for service
technicians). We provide general competitive algorithms for the OnlineTDAP independently of the particular downstream problem,
when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the particular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.
We consider simple models of financial markets with less and better
informed investors described by a smaller and a larger filtration on a
general stochastic basis that describes the market dynamics, including
continuous and jump components. We study the relation between different forms of non existance of arbitrage and the characteristics of the stochastic basis under the different filtrations. This is achieved through the analysis of the properties of the numéraire portfolio. Furthermore, we focus on the problem of calculating the additional logarithmic utility of the better informed investor in terms of the Shannon antropy of is additional information. The information drift, i.e. the drift to eliminate in order to preserved the martingale property in the larger filtration terms out to be the crucial quantity needed to tackle these problems. We show that the expected
ed logarithmic utility increment due to better information equals its Shannon
entropy also in case of a pure jump basis with jumps that are quadratically
hedgeable, and so extend a similar result known for bases consisting of
continuous semimartingales. An example illustrates that the equality may
not persist if both continuous and jump components are present in the
underlying.
In the planning process of railway companies, we propose to integrate important
decisions of network planning, line planning, and vehicle scheduling into the task of periodic
timetabling. From such an integration, we expect to achieve an additional potential for
optimization.
Models for periodic timetabling are commonly based on the Periodic Event Scheduling
Problem (PESP). We show that, for our purpose of this integration, the PESP has to be extended
by only two features, namely a linear objective function and a symmetry requirement.
These extensions of the PESP do not really impose new types of constraints, because practitioners
have already required them even when only planning timetables autonomously without
interaction with other planning steps.
The mixed regularity of electronic wave functions in fractional order and weighted Sobolev spaces
(2012)
The paper continues the study of the regularity of electronic wave functions in Hilbert spaces of mixed derivatives. It is shown that the eigenfunctions of electronic Schr\"odinger operators and their
exponentially weighted counterparts possess, roughly speaking, square integrable mixed weak derivatives of fractional order $\vartheta$ for $\vartheta<3/4$. The bound $3/4$ is best possible and can neither be reached nor surpassed. Such results are important for the study
of sparse grid-like expansions of the wave functions and show that their asymptotic convergence rate measured in terms of the number of ansatz functions involved does not deteriorate with the number of electrons.
The minimization of an L^{\infty}-functional subject to an elliptic PDE and state constraints
(2008)
We study the optimal control of a maximum-norm objective functional subjected to an elliptic-type PDE and pointwise state constraints. The problem is transformed into a problem where the non-differentiable L^{\infty}-norm in the functional will be replaced by a scalar variable and additional state constraints. This problem is solved by barrier methods. We will show the existence and convergence of the central path for a class of barrier functions. Numerical experiments complete the presentation.
Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We
identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems
by a factor of two on average.
The well-known Kalman-Yakubovich-Popov Lemma establishes an equivalence between dissipativity and the solvability of a linear matrix inequality. In this paper we strengthen this result by showing the equivalence of dissipativity to the solvability of a so-called Lur'e equation, which mainly is a linear matrix inequality with a rank minimizing condition. Finally, we apply the result to standard systems to obtain the well-known result about the solvability of the algebraic Riccati equation.
This paper introduces the line connectivity
problem, a generalization of the Steiner tree problem and a
special case of the line planning problem. We study its complexity and
give an IP formulation in terms of an exponential number of
constraints associated with "line cut constraints". These inequalities
can be separated in polynomial time. We also generalize the Steiner
partition inequalities.
We derive a full asymptotic expansion for call option prices and a third order approximation for implied volatility in the large-time, large log-moneyness regime for a general exponential Levy model, by extending the saddlepoint argument used in Forde,Jacquier & Mijatovic for the Heston model. As for the Heston model, there are two special log-moneyness values where the call option asymptotics are qualitatively different, and we use an Edgeworth expansion to deal with these cases. We also characterise the behaviour of the implied volatility skew at large-maturities; in particular we show that the derivative of the dimensionless implied variance with respect to log-moneyness exists and is less than or equal to 4 in the large-maturity limit, which is consistent with the bound on the right and left-side derivative given in Rogers&Tehranchi.
We investigate properties of a certain countably infinite graph called the
infinite locally random graph, written R_N. The graph R_N arises in the study
of models for massive, self-organizing networks like the web-graph. We
characterize the isomorphism type of R_N as the limit of a random process, and
via a domination elimination ordering. We prove that R_N satisfies vertex
deletion properties generalizing inexhaustibility. As is the case for the
infinite random graph R, R_N has a universal automorphism group and
endomorphism monoid. Unlike R, R_N isometrically embeds all finite graphs.
The hypergraph assignment problem (HAP) is the generalization of assignments
from directed graphs to directed hypergraphs. It serves, in particular,
as a universal tool to model several train composition rules in vehicle rotation
planning for long distance passenger railways. We prove that even for problems
with a small hyperarc size and hypergraphs with a special partitioned structure
the HAP is NP-hard and APX-hard. Further, we present an extended integer
linear programming formulation which implies, e. g., all clique inequalities.
In this paper we consider the first exit problem of an overdamped
Lévy driven particle in a confining potential. We survey results
obtained in recent years from our work on the Kramers' times for
dynamical systems of this type with Lévy perturbations containing
heavy, and exponentially light jumps, and compare them to the well
known case of dynamical systems with Gaussian perturbations. It
turns out that exits induced by Lévy processes with jumps are
always essentially faster than Gaussian exits.
The goal of this paper is to show how the heat treatment of steel can be modelled in terms of a mathematical optimal
control problem. The approach is applied to laser surface hardening and the cooling of a steel slab including
mechanical effects. Finally, it is shown how the results can be utilized in industrial practice by a coupling with
machine-based control.
We present an extension module for the Dune system. This module, called dune-subgrid, allows to mark elements of another Dune hierarchical grid. The set of marked elements can then be accessed as a Dune grid in its own right. dune-subgrid is free software and is available for download. We describe the functionality and use of dune-subgrid, comment on its implementation, and give two example applications.
First, we show how dune-subgrid can be used for micro-FE simulations of trabecular bone. Then we present an algorithm that allows to use exact residuals for the adaptive solution of the spatial problems of time-discretized evolution equations.
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.
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.
A relational structure is a core, if all its endomorphisms are embeddings. This notion is important for the classification for the computational complexity of constraint satisfaction problems. It is a fundamental fact that every finite structure S has a core, i.e., S has an endomorphism e such that the structure induced by e(S) is a core; moreover, the core is unique up to isomorphism.
We prove that this result remains valid for countably categorical structures, and prove that every countably categorical structure has a core, which is unique up to isomorphism, and which is again countably categorical. We thus reduced the classification for the complexity of constraint satisfaction problems with countably categorical templates to the classifiaction for constraint satisfaction problems where the templates are countably categorical cores. We also show that a core of a countably categorical structure Gamma is model complete, and therefore universal-existential axiomatizable. If Gamma contains all primitive positive definable relations, then the core of Gamma admits quantifier elimination. We discuss consequences for constraint satisfaction with countably categorical templates.
The paper addresses primal interior point method for state constrained PDE optimal
control problems. By a Lavrentiev regularization, the state constraint is transformed to a mixed
control-state constraint with bounded Lagrange multiplier. Existence and convergence of the central
path are established, and linear convergence of a short-step pathfollowing method is shown. The
behaviour of the regularizations are demonstrated by numerical examples.
In this paper, mean curvature type equations with general potentials and contact angle boundary conditions are considered. We extend the ideas of Ural'tseva, formulating sharper hypotheses for the existence of a classical solution.
Corner stone for these results is a method to estimate quantities on the boundary of the free surface. We moreover provide alternative proofs for the higher-order estimates, and for the existence result.
Single-hop WDM networks with a central Passive Star Coupler (PSC), as well as single-hop networks with
a central Arrayed-Waveguide Grating (AWG) and a single transceiver at each node, have been extensively
studied as solutions for the quickly increasing amounts of unicast and multicast traffic in the metropolitan
area. The main bottlenecks of these networks are the lack of spatial wavelength reuse in the studied PSC
based networks and the single transceiver in the studied AWG based metro WDM networks. In this paper
we develop and evaluate the FT EE ???? FREE AWG network, which is based on a central AWG and has arrays
of fixed-tuned transmitters and receivers at each node. Transceiver arrays are a mature technology, making
the proposed network practical. In addition, the transmitter arrays allow for high speed signaling over the
AWG while the receiver arrays relieve the receiver bottleneck arising from multicasting in conjunction with
spatial wavelength reuse on the AWG. Our results from probabilistic analysis and simulation indicate that
the FTEE ???? FREE AWG network gives particularly good throughput-delay performance for a mix of unicast
and multicast traffic.
Single–hop WDM networks with a central Passive
Star Coupler (PSC), as well as single–hop networks with a central
Arrayed–Waveguide Grating (AWG) and a single transceiver at
each node, have been extensively studied as solutions for the
quickly increasing amounts of unicast and multicast traffic in
the metropolitan area. The main bottlenecks of these networks
are the lack of spatial wavelength reuse in the studied PSC based
networks and the single transceiver in the studied AWG based
metro WDM networks. In this paper we develop and evaluate
the FT? ? FR? AWG network, which is based on a central
AWG and has arrays of fixed–tuned transmitters and receivers
at each node. Transceiver arrays are a mature technology, making
the proposed network practical. In addition, the transmitter
arrays allow for high speed signaling over the AWG while
the receiver arrays relieve the receiver bottleneck arising from
multicasting in conjunction with spatial wavelength reuse on the
AWG. Our results from probabilistic analysis and simulation
indicate that the FT? ? FR? AWG network gives particularly
good throughput–delay performance for multicast traffic with
small multicast group sizes or localized destination nodes, as
well as for a mix of unicast and multicast traffic.
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$.
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.
Periodic timetabling for railway networks is usually modeled by the Periodic Event Scheduling
Problem (PESP). This model permits to express many requirements that practitioners impose
on periodic railway timetables. We discuss a requirement practitioners are asking for, but which,
so far, has not been the topic of mathematical studies: the concept of symmetry.
Several motivations why symmetric timetables might seem promising will be given. However,
we provide examples showing that symmetry leads to suboptimality.
To integrate symmetry into the graph model of the PESP, there are many obstacles to overcome.
Nevertheless, adding symmetry requirements to mixed-integer programming formulations
explicitly, enables MIP solvers such as CPLEX
to terminate earlier with good solutions.
We consider the design of a logical network topology, together with node hardware, link capacities, and a survivable routing of demands. In addition to all single node failures, the routing must also survive multiple logical link failures caused by single failures in the underlying physical network. Furthermore, the number of logical links supported by a physical link is bounded. We propose an integer linear programming model for this design problem, together with a branch-and-cut based solution approach combined with column generation. The model and algorithm are tested on three real-world test instances, and preliminary results are given.
Supporting Global Numerical Optimization of Rational Functions by Generic Symbolic Convexity Tests
(2010)
Convexity is an important property in nonlinear optimization since it allows to apply efficient local methods for finding global solutions. We propose to apply symbolic methods to prove or disprove convexity of rational functions over a polyhedral domain. Our algorithms reduce convexity questions to real quantifier elimination problems. Our methods are implemented and publicly available in the open source computer algebra system REDUCE. Our long term goal is to integrate REDUCE as a ``workhorse'' for symbolic computations into a numerical solver.
A thorough convergence analysis of the Control Reduced Interior Point
Method in function space is performed. This recently proposed method is a
primal interior point pathfollowing scheme with the special feature, that the
control variable is eliminated from the optimality system. Apart from global
linear convergence we show, that this method converges locally almost quadratically,
if the optimal solution satisfies a certain non-degeneracy condition. In
numerical experiments we observe, that a prototype implementation of our
method behaves as predicted by our theoretical results.
An optimal control problem for a 2-d elliptic equation is investigated with pointwise control constraints.
This paper is concerned with discretization of the control by piecewise constant functions. The state and
the adjoint state are discretized by linear finite elements. Approximations of the optimal solution of the continuous
optimal control problem will be constructed by a projection of the discrete adjoint state. It is proved that these
approximations have convergence order h2.
Second-order sufficient optimality conditions are established for the optimal control
of semilinear elliptic and parabolic equations with pointwise constraints on the control and the state. In
contrast to former publications on this subject, the cone of critical directions is the smallest possible in the
sense that the second-order sufficient conditions are the closest to the associated necessary ones. The theory
is developed for elliptic distributed controls in domains up to dimension three. Moreover, problems of elliptic
boundary control and parabolic distributed control are discussed in spatial domains of dimension two and one,
respectively.
In this paper we study the shape and growth of structured pseudospectra
for small matrix perturbations of the form $A \leadsto
A_\Delta=A+B\Delta C$, $\Delta \in \DD$, $\|\Delta\|\leq \delta$.
It is shown that the properly scaled pseudospectra components converge
to non-trivial limit sets as $\delta$ tends to 0.
We discuss the relationship of these limit sets with $\mu$-values and
structured eigenvalue condition numbers for multiple eigenvalues.
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.
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.
This paper investigates the effect of structure-preserving perturbations on the eigenvalues
of linearly and nonlinearly structured eigenvalue problems. Particular attention is paid to
structures that form Jordan algebras, Lie algebras, and automorphism groups of a scalar product.
Bounds and computable expressions for structured eigenvalue condition numbers are derived for
these classes of matrices, which include complex symmetric, pseudo symmetric, persymmetric, skewsymmetric,
Hamiltonian, symplectic, and orthogonal matrices. In particular we show that under mild
assumptions on the scalar product, the structured and unstructured eigenvalue condition numbers
are equal for structures in Jordan algebras. For Lie algebras, the effect on the condition number of
incorporating structure varies greatly with the structure. We identify Lie algebras for which structure
does not affect the eigenvalue condition number.
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.
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.