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)
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.
In this review article we discuss different techniques to solve numerically the
time-dependent Schrödinger equation on unbounded domains.
We present in detail the most recent approaches and describe briefly alternative ideas pointing out the relations between these works.
We conclude with several numerical examples from
different application areas to compare the presented techniques. We mainly focus on the one-dimensional problem but also touch upon the situation in two space dimensions and the cubic nonlinear case.
Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment
structure.
We investigate the detection of symmetries appearing in this approach.
We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear
time if the assignment structure is known.
We consider hybrid systems of differential-algebraic equations and present
a general framework for general nonlinear over- and underdetermined hybrid
systems that allows the
analysis of existence and uniqueness and the application of index reduction
methods for hybrid differential-algebraic systems.
A particular difficulty in the numerical simulation of hybrid systems is
(numerical) chattering, i.e., fast oscillations between modes of operations.
A regularization technique using sliding modes allows to regularize the
system behavior in the case of chattering.
Further, we show how chattering behavior during the numerical solution can
be prevented using sliding mode simulation. The advantage of the sliding mode
simulation is illustrated by numerical examples.
In this article, we analyse three related preconditioned steepest descent algorithms, which are partially popular in Hartree-Fock and Kohn-Sham theory as well as invariant subspace computations, from the viewpoint of minimization of the corresponding functionals, constrained by orthogonality conditions. We exploit the geometry of the of the admissible manifold, i.e. the invariance with respect to unitary transformations, to reformulate the problem on the Grassmann manifold as the admissible set. We then prove asymptotical linear convergence of the algorithms under the condition that the Hessian of the corresponding Lagrangian is elliptic on the tangent space of the Grassmann manifold at the minimizer.
Canonical forms for matrix triples $(A,G,\hat G)$, where
$A$ is arbitrary rectangular and $G$, $\hat G$ are either real symmetric
or skew symmetric, or complex Hermitian or skew Hermitian, are derived.
These forms generalize classical product Schur forms as well as
singular value decompositions.
An new proof for the complex case is given, where there is no need to
distinguish whether $G$ and $\hat G$ are Hermitian or skew Hermitian.
This proof is independent from the results in Bolschakov/Reichstein 1995, where
a similar canonical form has been obtained for the complex case,
and it allows generalization to the real case. Here,
the three cases, i.e., that
$G$ and $\hat G$ are both symmetric, both skew symmetric or one each,
are treated separately.
About 15 years ago, Goemans and Williamson formally introduced the primal-dual framework for approximation algorithms and applied it to a class of network design optimization problems. Since then literally hundreds of results appeared that extended, modified and applied the technique to a wide range of optimization problems.
In this paper we define a class of cost-sharing games arising from Goemans and Williamson's original network design problems. We then show how to derive a group-strategyproof (i.e., collusion resistant) mechanism for such a game, using an existing primal-dual algorithm for the underlying optimization problem as a black box. The budget-balance factor of this mechanism is proportional to the performance ratio of the primal-dual algorithm if the optimization problem satisfies an additional technical condition.
Most existing collusion-resistant cost-sharing mechanisms are obtained through skillful adaptation of existing primal-dual algorithms for the associated optimization problems. This paper shows that, at least for a large class of games arising from network design problems, no such adaptation is necessary.
The nonlinear Schrödinger equation based on the Taylor approximation of the material dispersion can become invalid for ultrashort and few-cycle optical pulses. Instead, we use a rational fit to the dispersion function such that the resonances are naturally accounted for. This approach allows us to derive a simple non-envelope model for short pulses propagating in one spatial dimension. This model is further investigated numerically and analytically.
We discuss first order optimality conditions for state constrained
optimal control problems. Our concern is the treatment of problems,
where the solution of the state equation is not known to be continuous,
as in the case of boundary control in three space dimensions or optimal
control with parabolic partial differential equations. We show existence of
measure valued Lagrangian multipliers, which have just enough additional
regularity to be applicable to all possibly discontinuous solutions of the
state equation.
An extended mathematical framework for barrier methods for state constrained optimal control compared to [Schiela, ZIB-Report 07-07] is considered. This allows to apply the results derived there to more general classes of optimal control problems, in particular to boundary control and finite dimensional control.
We study barrier methods for state constrained optimal control problems
with PDEs. In the focus of our analysis is the path of minimizers of the
barrier subproblems with the aim to provide a solid theoretical basis for function
space oriented path-following algorithms. We establish results on existence,
continuity, and convergence of this path. Moreover, we consider the structure of
barrier subdifferentials, which play the role of dual variables.
In a rather general setting of multivariate stochastic volatility market models we derive global iterative probabilistic schemes for computing the free boundary and its Greeks for a generic class of American derivative models using front-fixing methods. Establishment of convergence is closely linked to a proof of global regularity of the free boundary surface.
The paper focuses on multi-period aspects of risk functionals. It discusses properties,
provides dual representations and offers methods for constructing multiperiod
risk functionals. On the way, existence results and representations for conditional
risk mappings are derived. In particular, conditional, multi-period, and
nested versions of the average value-at-risk are given. Finally, the importance of
polyhedral multi-period risk functionals for their employment in practical dynamic
decision making and risk management is discussed.
Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination.
In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm.
Dynamic risk management in electricity portfolio optimization via polyhedral risk functionals
(2008)
We propose a methodology for combining risk management with optimal planning of power production and trading based on probabilistic knowledge about future uncertainties such as demands and spot prices. Typically, such a joint optimization of risk and (expected) revenue yields additional overall efficiency. Our approach is based on stochastic optimization (stochastic programming) with a risk functional as objective. The latter maps an uncertain cash flow to a real number. In particular, we employ so-called polyhedral risk functionals which, though being non-linear mappings, preserve linearity structures of optimization problems. Therefore, these are favorable to the numerical tractability of the optimization problems. The class of polyhedral risk functionals contains well-known risk functionals such as Average-Value-at-Risk and expected polyhedral utility. Moreover, it is also capable to model different dynamic risk mitigation strategies.
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.
In this review, we intend to clarify the underlying ideas and the relations
between various multigrid methods ranging from subset decomposition,
to projected subspace decomposition and truncated multigrid.
In addition, we present a novel globally convergent inexact active set method
which is closely related to truncated multigrid. The numerical properties
of algorithms are carefully assessed by means of a degenerate problem and
a problem with a complicated coincidence set.
The goal of this paper is a mathematical investigation of dilatometer experiments. These are used to detect the kinetics
of solid-solid phase transitions in steel upon cooling from the high temperature phase. Usually, the data are only used for measuring
the start and end temperature of the phase transition. In the case of several coexisting product phases, expensive microscopic
investigations have to be performed to obtain the resulting fractions of the different phases. In contrast, it is shown in this paper that in the case of at most two product phases the complete phase transition kinetics including the final phase fractions are uniquely determined by the dilatometer data. Numerical results confirm the theoretical result.
We consider an adaptive finite element method (AFEM) for obstacle problems associated with linear second order elliptic boundary value problems and prove a reduction in the energy norm of the discretization error which leads to $R$-linear convergence. This result is shown to hold up to a consistery error due to the extension of the discrete multipliers (point functionals) to $H^{-1}$ and a possible mismatch between the continuous and discrete coincidence and noncoincidence sets. The AFEM is based on a residual-type error estimator consisting of element and edge residuals. The a posteriori error analysis reveals that the significant difference to the unconstrained case lies in the fact that these residuals only have to be taken into account within the discrete noncoincidence set. The proof of the error reduction property uses the reliability and the discrete local efficiency of the estimator as well as a perturbed Galerkin orthogonality. Numerical results are given illustrating the performance of the AFEM.
This paper discusses the convergence of kinetic variational inequalities to rate-independent quasi-static variational inequalities. Mathematical formulations as well as existence and uniqueness results for kinetic and rate-independent quasi-static problems are provided. Sharp a priori estimates for the kinetic problem are derived that imply that the kinetic solutions converge to the rate-independent ones, when the size of initial perturbations and the rate of application of the forces tends to 0. An application to three-dimensional elastic-plastic systems with hardening is given.
This paper deals with a three-dimensional model for thermal stress-induced transformations in shape-memory materials. Microstructure, like twined martensites, is described mesoscopically by a vector of internal variables containing the volume fractions of each phase. We assume that the temperature variations are prescribed. The problem is formulated mathematically within the energetic framework of rate-independent processes. An existence result is proved and temporal regularity is obtained in case of uniform convexity. We study also space-time discretizations and establish convergence of these approximations.
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.
Mehta, Roughgarden, and Sundararajan recently introduced a new class of cost sharing mechanisms called acyclic mechanisms. These mechanisms achieve a slightly weaker notion of truthfulness than the well-known Moulin mechanisms, but provide additional freedom to improve budget balance and social cost approximation guarantees. In this paper, we investigate the potential of acyclic mechanisms for combinatorial optimization problems. In particular, we study a subclass of acyclic mechanisms which we term singleton acyclic mechanisms. We show that every rho-approximate algorithm that is partially increasing can be turned into a singleton acyclic mechanism that is weakly group-strategyproof and rho-budget balanced. Based on this result, we develop singleton acyclic mechanisms for parallel machine scheduling problems with completion time objectives, which perform extremely well both with respect to budget balance and social cost.
In ferromagnetic materials, the gyrotropic nature of Landau-Lifshitz-Gilbert dynamics and anisotropic effects from stray-field interaction lead in certain regimes effectively to a wave-type dynamic equation. In the case of soft thin films and small Gilbert damping, we investigate the motion of Néel walls and prove the existence of traveling wave solutions under a small constant forcing.
A new concept is introduced for the adaptive finite element discretization of partial differential equations that have a sparsely
representable solution. Motivated by recent work on compressed sensing, a recursive mesh refinement procedure is presented that uses linear programming to find a good approximation to the sparse solution on a given refinement level. Then only those parts of the mesh are refined that belong to nonzero expansion coefficients. Error estimates for this procedure are refined and the behavior of the procedure is demonstrated via some simple elliptic model problems.
We study a so-called static approach for the problem of routing vehicles conflict-free through a given street network. In fact, we assume that routes are computed without taking time-dependences into account
and collisions are avoided via a particular reservation procedure. In this context, the task is to cope with two arising problems: the appearance of congestion and detours on the one hand and the risk of deadlocks on the other.
We provide a two-stage routing approach for that problem. In the first phase we focus on balancing the load on the edges of the
given graph that models the underlying street network. Therefore, we consider the Online Load Balancing Problem with Bounded Stretch
Factor and give an optimal algorithm with respect to a specific performance ratio, the stretch factor restricted competitive ratio. Furthermore, in a second phase, we investigate the detection and avoidance of deadlock situations.
For the evaluation of the entire algorithm we consider the routing of Automated Guided Vehicles (AGVs) at HHLA Container Terminal
Altenwerder (CTA).
The numerical solution of the Dirichlet boundary optimal control problem of the Navier-Stokes equations in presence of
pointwise state constraints is investigated. Two different regularization techniques are considered. First, a Moreau-Yosida
regularization of the problem is studied. Optimality conditions are derived and the convergence of the regularized solutions
towards the original one is proved. A source representation of the control combined with a Lavrentiev type regularization
strategy is also presented. The analysis concerning optimality conditions and convergence of the regularized solutions is
carried out. In the last part of the paper numerical experiments are presented. For the numerical solution of each
regularized problem a semi-smooth Newton method is applied.
We propose and analyse an interior point path-following method in function space
for state constrained optimal control. Our emphasis is on proving convergence in
function space and on constructing a practical path-following algorithm. In particular, the introduction of a pointwise damping step leads to a very efficient method, as verified by numerical experiments.
A continuity result for Nemyckii Operators and some applications in PDE constrained optimal control
(2008)
This work explores two applications of a classical result on the continuity of Nemyckii operators to optimal control with PDEs. First, we present an alternative approach to the analysis of Newton's method for function space problems involving semi-smooth Nemyckii operators. A concise proof for superlinear convergence is presented, and sharpened bounds on the rate of convergence are derived. Second, we derive second order sufficient conditions for problems, where the underlying PDE has poor regularity properties. We point out that the analytical structure in both topics is essentially the same.
The discontinuous Galerkin (dG) method provides a hierarchy of time discretization schemes for evolutionary problems. A dG time discretization has been proposed for a variational inequality in the context of rate-independent inelastic material behaviour in [Alberty, Carstensen: Discontinuous {G}alerkin Time Discretization in Elastoplasticity: Motivation, Numerical Algorithms and Applications, Comp. Meth. Appl. Mech. Engrg. \textbf{191} (2002)] with the help of duality in convex analysis to justify certain jump terms. Convincing numerical experiments have already been displayed in the literature.\This paper establishes a mathematical a~priori error analysis for the dG($1$) scheme with discontinuous piecewise linear polynomials in the temporal and first-order finite elements for the spacial discretization. One novel key idea in the a~priori convergence analysis is an optimal trace estimate under convex constraints. The numerical investigation of the empirical convergence rate in a benchmark concludes the paper.
The LSW model with encounters has been suggested by Lifshitz and
Slyozov as a regularization of their classical mean-field model for
domain coarsening to obtain universal self-similar long-time
behavior. We rigorously establish that an exponentially decaying
self-similar solution to this model exist, and show that this
solutions is isolated in a certain function space. Our proof relies
on setting up a suitable fixed-point problem in an appropriate
function space and careful asymptotic estimates of the solution to a
corresponding homogeneous problem.
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.
A mathematical model for the case hardening of steel is presented. Carbon is dissolved in the surface layer of a low-carbon steel part at a temperature sufficient to
render the steel austenitic, followed by quenching to form
a martensitic microstructure. The model consists of a nonlinear evolution equation for the temperature, coupled
with a nonlinear evolution equation for the carbon concentration, both coupled with two ordinary differential equations to describe the evolution of phase fractions.
We investigate questions of existence and uniqueness of a solution and finally present some numerical simulations.
We consider linear discrete-time descriptor systems, i.e., systems of linear equations of the form $E_{k+1} x^{k+1} = A_k x^k + f^k$ for $k \in \IZ$, where all $E_k$ and $A_k$ are matrices, $f_k$ are vectors and $x_k$ are the vectors of the solution we are looking for. We study the existence and uniqueness of solutions. A strangeness index is defined for such systems. Compared to the continuous-time case, it turns out, that in the discrete-time case it makes a difference, if one has an initial condition and one wants a solution in the future or if one has an initial condition and one wants a solution into the past and future at the same time.
We consider quickest flows within a new model that is based on transportation applications. In contrast to other models, it is forbidden to store flow in nodes and to cross nodes with more than one flow unit simultaneously. We work on undirected graphs. Grid graphs are of special interest because they typically arise in practice. Our model allows to close edges temporarily by time windows, and considers waiting on edges.
We solve several quickest s,t–flow problems without time windows polynomially. We prove that time windows make these problems NP–hard and even not approximable. In a multicommodity environment, all quickest flow variants are shown to be NP–hard even in grid graphs with uniform edge transit times. An alternative proof shows NP-hardness already for a small number of commodities in the case that waiting is not allowed and transit times are edge–specific. Finally, we propose two approximation algorithms in the case that time windows do not occur.
A refined a posteriori error analysis for symmetric eigenvalue problems and the convergence of the first-order adaptive finite element method (AFEM) is presented. The $H^1$ stability of the $L^2$ projection provides reliability and efficiency of the edge-contribution of standard residual-based error estimators for $P_1$ finite element methods. In fact, the volume contributions and even oscillations can be omitted for Courant finite element methods. This allows for a refined averaging scheme and so improves [Dong Mao, Lihua Shen and Aihui Zhou, Adaptive finite element algorithms for eigenvalue problems based on local averaging type a posteriori error estimates, Advanced in Computational Mathematics, 2006, 25: 135-160]. The proposed AFEM
monitors the edge-contributions in a bulk criterion and so enables a contraction property up to higher-order terms and global convergence. Numerical experiments exploit the remaining $L^2$ error contributions and confirm our theoretical findings. The averaging schemes show a high accuracy and the AFEM leads to optimal empirical convergence rates.
We propose a model for phase transformations that are driven by changes in the temperature. We consider the temperature as a prescribed prescribed quantity like an applied load. The model is based on the energetic formulation for rate-independent systems and thus allows for finite-strain elasticity. Time-dependent Dirichlet boundary conditions can be treated by decomposing the deformation as a composition of a given deformation satisfying the time-dependent boundary conditions and a part coinciding with the identity on the Dirichlet boundary.
A general abstract approximation scheme for rate-independent processes in the
energetic formulation is proposed and its convergence is proved under various
rather mild data qualifications. The abstract theory is illustrated on several
examples: plasticity with isotropic hardening, damage, debonding,
magnetostriction, and two models of martensitic transformation in
shape-memory alloys.
Studying high-dimensional Hamiltonian systems with microstructure, it is an important and challenging problem to identify reduced macroscopic models that describe some effective dynamics on large spatial and temporal scales. This paper concerns the question how reasonable macroscopic Lagrangian and Hamiltonian structures can by derived from the microscopic system. In the first part we develop a general approach to this problem by considering non-canonical Hamiltonian structures on the tangent bundle. This approach can be applied to all Hamiltonian lattices (or Hamiltonian PDEs) and involves three building blocks: (i) the embedding of the microscopic system, (ii) an invertible two-scale transformation that encodes the underlying scaling of space and time, (iii) an elementary model reduction that is based on a Principle of Consistent Expansions. In the second part we exemplify the reduction approach and derive various reduced PDE models for the atomic chain. The reduced equations are either related to long wave-length motion or describe the macroscopic modulation of an oscillatory microstructure.
Here we analyze algebraic multilevel methods applied to non-symmetric M-matrices.
We consider two types of multilevel approximate block factorizations.
The first one is related to the AMLI method.
The second method
is the multiplicative counterpart of the AMLI approach which we call
multiplicative algebraic multilevel method, the MAMLI method. The MAMLI method is closely related to certain geometric
and algebraic multigrid methods like the AMGr method. Although these
multilevel methods work very well
in practice for many problems, there is not that much known about
theoretical convergence
properties for non-symmetric problems.
Here, we establish
convergence results and comparison results between AMLI and MAMLI
multilevel methods
applied to non-symmetric M-matrices.
We establish theoretical comparison results for algebraic multi-level
methods applied
to nonsingular non-symmetric M-matrices.
We consider two types of multi-level approximate block factorizations or AMG methods, the
AMLI and the MAMLI method.
We compare
the spectral radii
of the iteration matrices of these methods. This comparison
shows, that the spectral radius of the MAMLI method is less than or equal to
the spectral radius of the AMLI method.
Moreover, we establish how the quality of the approximations
in the block factorization effects the spectral radii of the
iteration
matrices. We prove comparisons results
for different approximation of the fine grid block as well as for the
used Schur
complement. We also establish a theoretical comparison between the
AMG methods and the classical block Jacobi and block Gauss-Seidel methods.
Propagation of short optical pulses in a nonlinear dispersive medium is considered without the use of slow envelope and
unidirectional propagation approximations. The existence of uniformly moving solitary solutions is predicted in the anomalous
dispersion domain. A four-parametric family of such solutions is found that contains the classical envelope soliton in the limit of
large pulse durations. In the opposite limit we get another family member, which in contrast to the envelope soliton strongly depends on nonlinearity model and represents the shortest and the most intense pulse which can propagate in a stationary manner.
We study both theoretically and experimentally typical operation
regimes of 40 GHz monolithic mode-locked lasers. The underlying Traveling Wave Equation model reveals quantitative agreement for characteristics of the fundamental mode-locking as pulse width and repetition frequency tuning, as well as qualitative agreement with the experiments for other dynamic regimes. Especially the appearance of stable harmonic mode-locking at 80 GHz
has been predicted theoretically and confirmed by measurements.
Furthermore, we derive and apply a simplified Delay-Differential-Equation model
which guides us to a qualitative analysis of bifurcations responsible for the appearance
and the breakup of different mode-locking regimes. Higher harmonics of mode-locking are predicted by this model as well.
We explore the concept of passive-feedback lasers for direct signal
modulation at 40 Gbit/s. Based on numerical simulation and bifurcation
analysis, we explain the main mechanisms in these devices which are
crucial for modulation at high speed. The predicted effects are
demonstrated experimentally by means of correspondingly designed
devices. In particular a significant improvement of the modulation
bandwidth at low injection currents can be demonstrated.
We investigate a semiconductor laser with delayed optical feedback due
to an external cavity formed by a regular mirror. We discuss
similarities and differences of the well-known Lang-Kobayashi delay
differential equation model and the traveling wave partial
differential equation model. For comparison we locate the continuous
wave states in both models and analyze their stability.
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.
We consider Backward Stochastic Differential Equations (BSDEs) with generators that grow quadratically in the control variable. In a more abstract setting, we first allow both the terminal condition and the generator to depend on a vector parameter x. We give sufficient conditions for the solution pair of the BSDE to be differentiable in x. These results can be applied to systems of forward-backward SDE. If the terminal condition of the BSDE is given by a sufficiently smooth function of the terminal value of a forward SDE, then its solution pair is differentiable with respect tot the initial vector of the forward equation. Finally we prove sufficient conditions for solutions of quadratic BSDEs to be differentiable in the variational sense (Malliavin differentiable).
This paper is concerned with the study of insurance related derivatives on financial markets that are based on non-tradable underlyings, but are correlated with tradable assets. We calculate exponential utility-based indifference prices, and corresponding derivative hedges. We use the fact that they can be represented in terms of solutions of forward-backward stochastic differential equations (FBSDE) with quadratic growth generators. We derive the Markov property of such FBSDE and generalize results on the differentiability relative to the initial value of their forward components. In this case the optimal hedge can be represented by the price gradient multiplied with the correlation coefficient. This way we obtain a generalization of the classical ‘delta hedge’ in complete markets.
Optimality Conditions for State-Constrained PDE Control Problems with Time-Dependent Controls
(2008)
The paper deals with optimal control problems for semilinear
elliptic and parabolic PDEs subject to pointwise state constraints.
The main issue is that the controls are taken from a restricted
control space. In the parabolic case, they are vector-valued
functions of the time, while they are vectors in elliptic
problems. Under natural assumptions, first- and second-order
sufficient optimality conditions are derived. The main result is the
extension of second-order sufficient conditions to semilinear
parabolic equations in domains of arbitrary dimension. In the
elliptic case, the problems can be handled by known results of
semi-infinite optimization. Here, different examples are discussed
that exhibit different forms of active sets and where second-order
sufficient conditions are satisfied at the optimal solution.
The extent to which catastrophic weather events occur strongly depends on global climate conditions such as average sea surface temperatures (SST) or sea level pressures. Some of the factors can be predicted up to a year in advance, and should therefore be taken into account in any reasonable management of weather related risk. In this paper we first set up a risk model that integrates climate factors. The we show how variance minimizing hedging strategies explicitly depend on the factors' prediction. Our analysis is based on a detailed study of the predictable representation property on the combined Poisson and Wiener spaces. Using tools of the stochastic calculus of variations we derive a representation formula of the Clark-Ocone type. Finally, we exemplify the theory developed in a case study of US hurricane risk. We derive hedging strategies taking into account that US hurricane activity strongly depends on the SST of the Pacific Ocean.
A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the Lr-distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.
In a rather general setting of Itô-Lévy processes we study a class of transforms (Fourier for example) of the state variable of a process which are holomorphic in some disc around time zero in the complex plane. We show that such transforms are related to a system of analytic vectors for the generator of the process, and we state conditions which allow for holomorphic extension of these transforms into a strip which contains the positive real axis. Based on these extensions we develop a functional series expansion of these transforms in terms of the constituents of the generator. As application, we show that for multidimensional affine Itô-Lévy processes with state dependent jump part the Fourier transform is holomorphic in a time strip under some stationarity conditions, and give log-affine series representations for the transform.
In the past, much research had been dedicated to compute optimum railway timetables. A typical objective was the minimization of passenger waiting times. But only the planned nominal waiting times were addressed, whereas delays, as they occur in daily operation, were neglected. Rather, conceptually, delays were treated mainly in an online-context, and solved as a separate optimization problem, called delay management.
We provide the first computational study which aims at computing delay resistant periodic timetables. In particular we assess the delay resistancy of a timetable by evaluating it subject to several delay scenarios, to which optimum delay management will be applied.
We arrive at computing delay resistant timetables by selecting a new objective function which we design to be in the middle of the traditional simple timetabling objective and the sophisticated delay management objective. This is a slight extension of the concept of "Light Robustness", as it was proposed by Fischetti and Monaci (2006). Moreover, in our application we are able to provide accurate interpretations for the ingredients of Light Robustness.
We apply this new technique to real-world data of a part of the German railway network of Deutsche Bahn AG. Our computational results suggest that a significant decrease of passenger delays could be obtained at a relatively small price of robustness.
In the Minimum Strictly Fundamental Cycle Basis (MSFCB) problem one is looking for a spanning tree such that the sum of the lengths of its induced fundamental circuits is minimum.
We identify square planar grid graphs as being very challenging testbeds for the MSFCB. The best lower and upper bounds for this problem are due to Alon, Karp, Peleg, and West (1995) and to Amaldi et~al. (2004).
We improve significantly their bounds, both empirically and asymptotically. Ideally, these new benchmarks will serve as a reference for the performance of any new heuristic for the MSFCB problem which will be designed only in the future.
Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length O(n2) for any unweighted graph, whence proving the conjecture of Deo et al. (1982).
For weighted graphs, we construct cycle bases of length O(W log(n) log(log(n))), where W denotes the sum of the weights of the edges. This improves the upper bound that follows from the result of Elkin et al. (2005) by a logarithmic factor and, for comparison from below, some natural classes of large girth graphs are known to exhibit minimum cycle bases of length Ω(W log(n)).
We achieve this bound for weighted graphs by not restricting ourselves to strictly fundamental cycle bases - as it is inherent to the approach of Elkin et al. - but rather also considering weakly fundamental cycle bases in our construction. This way we profit from some nice properties of Hierarchically Well-Separated Trees that were introduced by Bartal (1998).
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).
In many applications such as data compression, imaging or
genomic data analysis,
it is important to approximate a given $m\times n$ matrix $A$
by a matrix $B$ of rank at most $k$ which is much smaller than $m$ and $n$.
The best rank $k$ approximation can be determined via
the singular value decomposition
which, however, has prohibitively
high computational complexity and storage requirements
for very large $m$ and $n$.
We present an optimal least squares algorithm for computing a rank $k$
approximation to an $m\times n$ matrix $A$ by reading
only a limited number of rows and columns of $A$.
The algorithm has complexity $\mathcal O(k^2\max(m,n))$ and
allows to iteratively improve given rank $k$
approximations by reading additional rows and
columns of $A$. We also show how this approach can be extended
to tensors and present numerical results.
We propose a model reduction method for positive systems that ensures the positivity of the reduced-order model. In the standard as well as in the descriptor case, for 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. Positivity and stability are preserved and an error bound in the $\mathcal{H}_\infty$-norm is provided.
In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed.
This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but
is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the
implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version.
Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence.
We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques.
A well-known discrete approach to modeling biological regulatory networks is the logical framework developed by R. Thomas. The network structure is captured in an interaction graph, which, together with a set of Boolean parameters, gives rise to a state transition graph describing the dynamical behavior. Together with E. H. Snoussi, Thomas later extended the framework by including singular values representing the threshold values of interactions. A systematic approach was taken in \cite{AB07} to link circuits in the interaction graph with character and number of attractors in the state transition graph by using the information inherent in singular steady states. In this paper, we employ the concept of local interaction graphs to strengthen the results in \cite{AB07}. Using the local interaction graph of a singular steady state, we are able to construct attractors of the regulatory network from attractors of certain subnetworks. As a comprehensive generalization of the framework introduced in \cite{AB07}, we
drop constraints concerning the choice of parameter values to include so-called context sensitive networks.
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.
In "classical optimization" it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so "nice" to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of "online optimization" which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not
the result of bad data handling but an inevitable phenomenon.
We introduce new elevator group control algorithms that can be implemented to be real-time compliant on embedded microcontrollers. The algorithms operate a group of elevators in a destination call system, i.e. passengers specify the destination floor instead of the travel direction only. The aim is to achieve small waiting and travel times for the passengers. We provide evidence, using simulation, that the algorithms offer good performance. One of our algorithms has been implemented by our industry partner and is used in real-world systems.
Diffusion Tensor Imaging (DTI) data is characterized by a high noise level. Thus,
estimation errors of quantities like anisotropy indices or the main diffusion direction
used for fiber tracking are relatively large and may significantly confound the accuracy
of DTI in clinical or neuroscience applications. Besides pulse sequence optimization,
noise reduction by smoothing the data can be pursued as a complementary approach
to increase the accuracy of DTI. Here, we suggest an anisotropic structural adaptive
smoothing procedure, which is based on the Propagation-Separation method and preserves
the structures seen in DTI and their different sizes and shapes. It is applied
to artificial phantom data and a brain scan. We show that this method significantly
improves the quality of the estimate of the diffusion tensor and hence enables one
either to reduce the number of scans or to enhance the input for subsequent analysis
such as fiber tracking.
In this paper we carry over the concept of reverse probabilistic representa-
tions developed in Milstein, Schoenmakers, Spokoiny (2004) for diffusion pro-
cesses, to discrete time Markov chains. We outline the construction of reverse
chains in several situations and apply this to processes which are connected
with jump-diffusion models and finite state Markov chains. By combining
forward and reverse representations we then construct transition density esti-
mators for chains which have root-N accuracy in any dimension and consider
some applications.
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.
In this paper we propose a Libor model with a high-dimensional specially structured system of
driving CIR volatility processes. A stable calibration procedure which takes into account
a given local correlation structure is presented. The calibration algorithm is FFT based, so fast and easy
to implement.
We consider regular polynomial interpolation algorithms on recursively defined sets of interpolation points which approximate global solutions of arbitrary well-posed systems of linear partial differential equations. Convergence of the "limit" of the recursively constructed family of polynomials to the solution and error estimates are obtained from a priori estimates for some standard classes of linear partial differential equations, i.e. elliptic and hyperbolic equations. Another variation of the algorithm allows to construct polynomial interpolations which preserve systems of linear partial differential equations at the interpolation points. We show how this can be applied in order to compute higher order terms of WKB-approximations of fundamental solutions of a large class of linear parabolic equations. The error estimates are sensitive to the regularity of the solution. Our method is compatible with recent developments for solution of higher dimensional partial differential equations, i.e. (adaptive) sparse grids, and weighted Monte-Carlo, and has obvious applications to mathematical finance and physics.
A class of nonlinear elliptic optimal control
problems with mixed control-state constraints arising, e.g., in Lavrentiev-type
regularized state constrained optimal control is considered. Based
on its first order necessary optimality conditions, a semismooth
Newton method is proposed and its fast local convergence in
function space as well as a mesh-independence principle for
appropriate discretizations are proved. The paper ends by a
numerical verification of the theoretical results including a study of the
algorithm in the case of vanishing Lavrentiev-parameter. The latter process is
realized numerically by a combination of a nested iteration concept and an extrapolation technique for
the state with respect to the Lavrentiev-parameter.
In this paper we introduce efficient Monte Carlo estimators for the valuation
of high-dimensional derivatives and their sensitivities (”Greeks”).
These estimators are based on an analytical, usually approximative representation
of the underlying density. We study approximative densities
obtained by the WKB method. The results are applied in the context of
a Libor market model.
A state-constrained optimal control problem arising in the context of sublimation crystal growth is considered. The presence of pointwise state-constraints and nonlocal radiation interface conditions
constitutes the major issue of this problem. A regularity result of the state is presented that allows to
derive the optimality condition.
The numerical solution of the Dirichlet boundary optimal control problem of the Navier-Stokes equations in presence of
pointwise state constraints is investigated. A Moreau-Yosida regularization of the problem is proposed to obtain regular
multipliers. Optimality conditions are derived and the convergence of the regularized solutions towards the original one is
presented. The paper is ended with a numerical experiment.
Sensitivity analysis (with respect to the regularization parameter)
of the solution of a class of regularized state constrained
optimal control problems is performed. The theoretical results are
then used to establish an extrapolation-based numerical scheme for
solving the regularized problem for vanishing regularization
parameter. In this context, the extrapolation technique provides
excellent initialization along the sequence of reducing
regularization parameters. Finally, the favorable numerical
behavior of the new method is demonstrated in a nested iteration
environment.
We study an optimal control problem (OCP) subject to a PDE of elliptic type as well as state constraints. The resulting optimality system contains two PDEs, one algebraic equation and the so called complementary slackness conditions, i.e. dual products between function spaces. At this point different regularization techniques come into use.
In this paper we introduce a Barrier method as one possible way to regularize state constraints, which leads to an easily implementable path-following algorithm.
To illustrate this method, we solve first a constructed problem with known solution. Here, we can verify the rate of convergence of the path-following method. Second, a simplified hyperthermia problem in 3D is solved by using COMSOL Multiphysics.
Three properties of matrices: the spark, the mutual incoherence and the restricted isometry property have recently been introduced in the context of compressed sensing. We study these properties for matrices that are Kronecker products and show how these properties relate to those of the factors. For the mutual incoherence we also
discuss results for sums of Kronecker products.
We study the global spatial regularity of solutions of elasto-plastic models with linear hardening. In order to point out the main idea, we consider a model problem on a cube, where we describe Dirichlet and
Neumann boundary conditions on the top and the bottom, respectively, and periodic boundary conditions on the
remaining faces. Under natural smoothness assumptions on the data we obtain
$u\in L^\infty((0,T);H^{3/2-\delta}(\Omega))$ for the displacements and
$z\in L^\infty((0,T);H^{1/2-\delta}(\Omega))$ for the internal variables.
The proof is based on a difference quotient technique and a reflection argument.
Stochastic Optimization of Electricity Portfolios: Scenario Tree Modeling and Risk Management
(2008)
We present recent developments in the field of stochastic programming with regard to application in power management. In particular we discuss issues of scenario tree modeling, i.e., appropriate discrete approximations of the underlying stochastic parameters. Moreover, we suggest risk avoidance strategies via the incorporation of
so-called polyhedral risk functionals into stochastic programs. This approach, motivated through tractability of the resulting problems, is a constructive framework providing particular flexibility with respect to the dynamic aspects of risk.
We prove an optimal regularity result for elliptic operators $-\nabla \cdot \mu \nabla:W^1,q_0 \rightarrow W^-1,q$ for a $q>3$ in the case when the coefficient function $\mu$ has a jump across a $C^1$ interface and is continuous elsewhere. A counterexample shows that the $C^1$ condition cannot be relaxed in general. Finally, we draw some conclusions for corresponding parabolic operators.
Let $\Upsilon$ be a three-dimensional Lipschitz polyhedron, and assume that the matrix function $\mu$ is piecewise constant on a polyhedral partition of $\Upsilon$. Based on regularity results for solutions to two-dimensional anisotropic transmission problems near corner points we obtain conditions on $\mu$ and the intersection angles between interfaces and $\partial \Upsilon$ ensuring that the operator $-\nabla \cdot \mu \nabla$ maps the Sobolev space $W^1,q_0(\Upsilon)$ isomorphically onto $W^-1,q(\Upsilon)$ for some $q > 3$.
Using a classical theorem of Sobolevskii on equations of parabolic type in a Banach space and recently obtained results on elliptic operators with discontinuous coefficients including mixed boundary conditions we prove that quasilinear parabolic systems in diagonal form admit a local, classical solution in the space of p-integrable functions, for some p greater than 1, over a bounded two dimensional space domain. As applications we have in mind systems of reaction diffusion equations, e.g. van Roosbroeck's system. The treatment of such equations in a space of integrable functions enables us to define the normal component of the flow across any part of the Dirichlet boundary by Gauss' theorem.
For an operator-valued block-matrix model, which is called in quantum physics a Feshbach decomposition, a scattering theory is considered. Under trace class perturbation the channel scattering matrices are calculated. Using Feshbach's optical potential it is shown that for a given spectral parameter the channel scattering matrices can be recovered either from a dissipative or from a Lax-Phillips scattering theory.
The paper is devoted to Schroedinger operators on bounded intervals of the real axis with dissipative boundary conditions. In the framework of the Lax-Phillips scattering theory the asymptotic behaviour of the phase shift is investigated in detail and its relation to the spectral shift is discussed, in particular, trace formula and Birman-Krein formula are verified directly. The results are used for dissipative Schroedinger-Poisson systems.
Electronic structure and optoelectronic properties of strained InAsSb/GaSb multi quantum-wells
(2008)
A study of the optical properties of a set of InAsxSb1-x/Al0.15In0.85As0.77Sb0.23/GaSb multiple quantum-wells (for x between 0.82 and 0.92) with build-in strains in the -0.62% to +0.05%-range is presented. The energy of the lowest quantum-confined optical transition is calculated by kp perturbation theory and experimentally determined by absorption measurements. Stokes shift of photoluminescence, photocurrent and of the emission from light emitting devices against the absorption edge of the quantum-well are quantified. The impact of the decreasing carrier confinement in the InAsxSb1-x quantum well system with increasing mole fraction is analyzed theoretically, and experimentally demonstrated by photoluminescence measurement. Our results allow for the improvement of optoelectronic devices, in particular for tailoring emission spectra of light emitting diodes.
We describe an embedding of a quantum mechanically described structure into a macroscopic flow. The open quantum system is partly driven by an adjacent macroscopic flow acting on the boundary of the bounded spatial domain designated to quantum mechanics. This leads to an essentially non-selfadjoint Schroedinger-type operator, the spectral properties of which will be investigated.
We study in detail Schroedinger-type operators on a bounded interval of the real axis with dissipative boundary conditions. The characteristic function of such operators is computed, its minimal self-adjoint dilation is constructed and the generalized eigenfunction expansion for the dilation is developed. The problem is motivated by semiconductor physics.
Non-selfadjoint operators play an important role in the modeling of open quantum systems. We consider a one-dimensional Schroedinger-type operator with dissipative boundary conditions and dissipative delta potentials. An explicit description of the characteristic function, the minimal dilation and the generalized eigenfunctions of the dilation is given. The quantities of carrier and current densities are rigorously defined. Furthermore we will show that the current is not constant and that the variation of the current depend essentially on the chosen density matrix and imaginary parts of the delta potentials. This correspondence can be used to model a recombination-generation rate in the open quantum system.
The classical singular value decomposition for a matrix $A\in\Cmn$ is a
canonical form for $A$ that also displays the eigenvalues
of the Hermitian matrices $AA^\ast$ and $A^\ast A$. In this paper, we develop
a corresponding decomposition for $A$ that provides the Jordan canonical forms
for the complex symmetric matrices $AA^T$ and $A^TA$. More generally, we consider
the matrix triple $(A,G_1,G_2)$, where $G_1\in\CC{m}, G_2\in\CC{n}$
are invertible and either complex symmetric and complex skew-symmetric, and we
provide a canonical form under transformations of the form
$(A,G_1,G_2)\mapsto(X^T A Y, X^T G_1X, Y^T G_2Y)$, where $X,Y$ are nonsingular.
Relating Attractors and Singular Steady States in the Logical Analysis of Bioregulatory Networks
(2007)
In 1973 R. Thomas introduced a logical approach to modeling and analysis of
bioregulatory networks. Given a set of Boolean functions describing the
regulatory interactions, a state transition graph is constructed that captures
the dynamics of the system. In the late eighties, Snoussi and Thomas extended
the original framework by including singular values corresponding to
interaction thresholds. They showed that these are needed for a refined
understanding of the network dynamics.
In this paper, we study systematically singular steady states, which are
characteristic of feedback circuits in the interaction graph, and relate them
to the type, number and cardinality of attractors in the state transition
graph. In particular, we derive sufficient conditions for regulatory networks
to exhibit multistationarity or oscillatory behavior, thus giving a partial
converse to the well-known Thomas conjectures.
We derive formulas for the minimal positive solution of a
particular non-symmetric Riccati
equation arising in transport theory. The formulas are based
on the eigenvalues of an
associated matrix. We use the formulas to explore some new
properties of the minimal positive solution and to derive
fast and highly accurate numerical methods. Some numerical tests
demonstrate the properties of the new methods.
We apply the general framework developed by John et al. in [15] to
analyze the convergence of multi-level methods for mixed finite element
discretizations of the generalized Stokes problem using the
Scott-Vogelius element. Having in mind that semi-implicit operator
splitting schemes for the Navier-Stokes equations lead to this class of
problems, we take symmetric stabilization operators into account. The use
of the class of Scott-Vogelius elements seems to be promising since
discretely divergence-free functions are pointwise divergence-free.
However, to satisfy the Ladyzhenskaya-Babuska-Brezzi stability
condition, we have to deal in the multi-grid analysis with non-nested
families of meshes which are derived from nested macro element
triangulations.
Adjoint Broyden a la GMRES
(2007)
It is shown here that a compact storage implementation of a quasi-Newton
method based on the adjoint Broyden update reduces in the affine
case exactly to the well established GMRES procedure. Generally,
storage and linear algebra effort per step are small multiples of $n\cdot k$,
where $n$ is the number of variables and $k$ the number of steps taken
in the current cycle. In the affine case the storage is exactly $(n+k)\cdot k$
and in the nonlinear case the same bound can be achieved if adjoints,
i.e. transposed Jacobian-vector products are available. A
transposed-free variant that relies exclusively on Jacobian-vector
products (or possibly their approximation by divided differences)
requires roughly twice the storage and turns out to be somewhat slower
in our numerical experiments reported at the end.
We construct and analyze multigrid methods
for discretized self-adjoint elliptic problems on triangular surfaces in $\RR^3$.
The methods involve the same weights for restriction and prolongation as in the case of planar triangulations
and therefore are easy to implement. We prove logarithmic bounds of the convergence
rates with constants solely depending on the ellipticity, the smoothers and on the
regularity of the triangles forming the triangular surface.
Our theoretical results are illustrated by numerical computations.