Refine
Year of publication
- 2005 (111) (remove)
Language
- English (111) (remove)
Keywords
- optimal stopping (2)
- stability (2)
- American options (1)
- BSDE (1)
- Becker-Doering equations (1)
- Finance (1)
- Hidden Markov Model (1)
- Hierarchical matrices (1)
- IP (1)
- Instances (1)
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.
We present a new mathematical approach to metabolic pathway analysis, characterizing a metabolic network by minimal metabolic behaviors and the reversible metabolic space. Our method uses an outer description of the steady state flux cone, based on sets of irreversible reactions. This is different from existing approaches, such as elementary flux modes or extreme pathways, which use an inner description, based on sets of generating vectors. The resulting description of the flux cone is much more compact. By focussing on the reversible and irreversible reactions, our approach provides a different view of the network, which may also lead to new biological insights.
Descriptor systems present a general
mathematical framework for the modelling, simulation and control of complex dynamical systems arising in many areas of mechanical,
electrical and chemical engineering. This
paper presents a survey of the current theory of descriptor systems,concerning
solvability, stability, model reduction, controllability, observability and optimal control.
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 a model for scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling
as a special case. The particular setting we consider is non-preemptive parallel machine scheduling, with the objective to
minimize the total weighted completion times of jobs. We analyze
simple, combinatorial online scheduling policies for that model, and
derive performance guarantees that match performance guarantees previously
known for stochastic and online parallel machine scheduling, respectively.
For processing times that follow NBUE distributions, we
improve upon previously best known performance bounds from
stochastic scheduling, even though we consider a more general
setting.
In this paper we discuss the stability and model order reduction of coupled linear
time-invariant systems. Sufficient conditions for a closed-loop system to be asymptotically stable are
given. We present a model reduction approach for coupled systems based on reducing the order of the
subsystems and coupling the reduced-order subsystems by the same interconnection matrices as for
the original model. Such an approach allows to obtain error bounds for the reduced-order closed-loop
system in terms of the errors in the reduced-order subsystems. Model reduction of coupled systems
with unstable subsystems is also considered. Numerical examples are given.
We present structure preserving algorithms for the numerical com-
putation of structured staircase forms of skew-symmetric/symmetric
matrix pencils along with the Kronecker indices of the associated skew-
symmetric/symmetric Kronecker-like canonical form. These methods
allow deflation of the singular structure and deflation of infinite eigenvalues with index greater than one. Two algorithms are proposed: one
for general skew-symmetric/symmetric pencils and one for pencils in
0
which the skew-symmetric matrix is a direct sum of 0 and J = −I I .
0
We show how to use the structured staircase form to solve boundary
value problems arising in control applications and present numerical
examples.
Classical results about the local existence and uniqueness of
DAE solutions are based on the derivative array [2] or on a geometrical
approach [13]. Thus these results can't be applied to equations with nonsmooth
coefficients. Also, sufficient conditions that guarantee solvability
are hard to check in general [6, 13]. In this paper a new approach to proving
local existence and uniqueness of DAE solutions is presented. The
main tool is a decoupling procedure that makes it possible to split DAE
solutions into their characteristic parts. Thus it is possible to weaken
the smoothness requirements considerably. In order for the decoupling
procedure to work we require a certain structural condition to hold. In
contrast to results already known, this condition can be easily verified.
We introduce FreeLence, a lossless single-rate connectivity compression algorithm for triangle surface meshes. Based upon a geometry-driven traversal scheme we present two novel and simple concepts: free-valence connectivity encoding and entropy coding based on geometric context. Together these techniques yield signicantly smaller rates for connectivity compression than current state of the art approaches - valence-based algorithms and Angle- Analyzer, with an average of 36% improvement over the former and an average of 18% over the latter on benchmark 3D models, combined with the ability to well adapt to the regularity of meshes. We also prove that our algorithm exhibits a smaller worst case entropy
for a class of ”well-behaved” triangle meshes than valence-driven connectivity encoding approaches.
Many constraint satisfaction problems have a natural formulation as a homomorphism problem. For a fixed relational structure Gamma we consider the following computational problem: Given a structure S with the same relational signature as Gamma, is there a homomorphism from S to Gamma? This problem is known as the constraint satisfaction problem CSP(Gamma) for the so-called template Gamma and is intensively studied for relational structures Gamma with a finite domain. However, many constraint satisfaction problems can not be formulated with a finite template.
If we allow arbitrary infinite templates, constraint satisfaction is very expressive. We show that it contains undecidable problems, even if the constraint language is binary. In general, a computational problem can be described as the constraint satisfaction problem of an infinite template if and only if it is closed under inverse homomorphisms and disjoint unions. It is also easy to see that we can restrict our attention to countable templates.
In this thesis we study the computational complexity of constraint satisfaction with templates that are omega-categorical. A structure Gamma is omega-categorical if all countable models of the first-order theory of Gamma are isomorphic to Gamma. This concept is central and well-studied in model-theory. On the one hand, omega-categoricity is a rather strong model-theoretic assumption on a relational structure, and we can use them to show that many techniques for constraint satisfaction with finite templates extend to omega-categorical templates.
We prove sufficient and essentially necessary conditions in terms of the
minimum degree for a graph to contain planar subgraphs with many edges.
For example, for all positive γ every sufficiently large graph G with minimum
degree at least (2/3 + γ)|G| contains a triangulation as a spanning
subgraph, whereas this need not be the case when the minimum degree is
less than 2|G|/3.
The Steiner tree problem is to nd a shortest subgraph
that spans a given set of vertices in a graph. This problem
is known to be NP-hard and it is well known that a polynomial time
2-approximation algorithm exists. In 1996 Zelikovsky [11] suggested
an approximation algorithm for the Steiner tree problem that is called
the relative greedy algorithm. Till today the performance ratio of this
algorithm is not known. Zelikovsky provided 1.694 as an upper bound
and Gröpl, Hougardy, Nierho and Prömel [6] proved that 1.333 is a
lower bound. In this paper we improve the lower bound for the performance
ratio of the relative greedy algorithm to 1.385.
The terminal Steiner tree problem is a special version of
the Steiner tree problem, where a Steiner minimum tree has to be found
in which all terminals are leaves. We prove that no polynomial time approximation
algorithm for the terminal Steiner tree problem can achieve
an approximation ratio less than (1 - o(1)) ln n unless NP has slightly superpolynomial
time algorithms. Moreover, we present a polynomial time
approximation algorithm for the metric version of this problem with a performance
ratio of 2 , where denotes the best known approximation ratio
for the Steiner tree problem. This improves the previously best known
approximation ratio for the metric terminal Steiner tree problem of +2.
Approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be
solved in polynomial time. The weighted matching problem is to find a matching in an
edge weighted graph that has maximum weight. The first polynomial time algorithm for this problem was given by Edmonds in 1965. The fastest known algorithm for the weighted matching problem has a running time of O(nm + n2 log n). Many real world problems require graphs of such large size that this running time is too costly. Therefore there is considerable need for faster approximation algorithms for the weighted matching problem. We present a linear time approximation algorithm for the weighted matching problem with a performance ratio arbitrarily close to 2/3 . This improves the previously best performance ratio of 1/2. Our algorithm is not only of theoretical interest but because it is easy to implement and the constants involved are quite small it is also useful in practice.
We study semirandom k-colorable graphs made up as follows. Partition the vertex set
V = {1, ... , n} randomly into k classes V1, ... , Vk of equal size and include each Vi-Vj -edge
with probability p independently (1 ≤ i < j ≤ k) to obtain a graph G0. Then, an adversary may
add further Vi-Vj -edges (i 6= j) to G0, thereby completing the semirandom graph G = G ∗ n,p,k.
We show that if np ≥ max{(1 + ε)k ln n,C0k2} for a certain constant C0 > 0 and an arbitrarily
small but constant ε > 0, an optimal coloring of G ∗ n,p,k can be found in polynomial time with high
probability. Furthermore, if np ≥ C0 max{k ln n, k2}, a k-coloring of G ∗ n,p,k can be computed in
polynomial expected time. Moreover, an optimal coloring of G ∗ n,p,k can be computed in expected
polynomial time if k ≤ ln1/3 n and np ≥ C0k ln n. By contrast, it is NP-hard to k-color G ∗ n,p,k
w.h.p. if np ≤ (1/2 − ε)k ln(n/k).
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.
We consider instances of the maximum independent set problem that are constructed
according to the following semirandom model. Let Gn,p be a random graph, and let
S be a set of k vertices, chosen uniformly at random. Then, let G0 be the graph
obtained by deleting all edges connecting two vertices in S. Finally, an adversary may
add edges to G0 that do not connect two vertices in S, thereby producing the instance
G = G ∗ n,p,k . We present an algorithm that on input G = G ∗ n,p,k finds an independent
set of size ≥ k within polynomial expected time, provided that k ≥ C(n/p)1/2 for a
certain constant C > 0. Moreover, we prove that in the case k ≤ (1 − ε) ln(n)/p this
problem is hard.
An instance of a constraint satisfaction problem is k-consistent if any k constraints of it can be simultaneously satisfied. We focus on constraint languages with a single binary constraint. In this case, the constraint satisfaction problem is equivalent to the question whether there is a homomorphism from an input digraph G to a fixed target digraph H. The instance corresponding to G is k-consistent if every subgraph of G of size at most k is homomorphic to H. Let r_k(H) be the largest r such that every k-consistent G contains a subgraph G' of size at least r ||E(G)|| that is homomorphic to H. The ratio r_k(H) reflects the fraction of constraints of a k-consistent instance that can be always satisfied. We determine r_k(H) for all digraphs H that are not acyclic and show that lim r_k(H)=1 for k tending to infinity if H has tree duality. For the latter case we design an efficient algorithm that computes in linear time for a given input graph G and epsilon>0 either a homomorphism from almost the entire graph G to H or a subgraph of G of bounded size that is not homomorphic to H.
Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm solving these constraints more efficiently, in quadratic time per solved form. It also applies to weakly normal dominance constraints as needed for an application to computational linguistics. Subquadratic running time can be achieved employing decremental graph biconnectivity algorithms.
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.
Recently, Dreyer and Duderstadt have proposed a modification of the
Becker-Doering cluster equations which now have a nonconvex
Lyapunov function. We start with existence and uniqueness results
for the modified equations. Next we derive an explicit criterion for
the existence of equilibrium states and solve the minimization
problem for the Lyapunov function. Finally, we discuss the long time
behavior in the case that equilibrium solutions do exist.
We report on a novel approach to the automatic identification
of metastable states from long term simulation of complex
molecular systems. The new approach is based on a hierarchical concept
of metastability: metastable states are understood as subsets of
state or configuration space from which the dynamics exits only very rarely;
subsets with the smallest exit probabilities are of most interest, their
further decomposition then may reveal subsets from which exiting
is less but comparably difficult for the system under investigation.
The article gives a survey of the theoretical foundation of
the approach and its algorithmic realization that generalizes
the well-known concept of Hidden Markov Models.
The performance of the resulting algorithm are illustrated by
application to a 100 ns simulation of penta-alanine with explicit water.
We demonstrate the resulting metastable states allow to
reveal the conformation dynamics of the moelcule.
We provide conditions for convergence of polyhedral surfaces and their
discrete geometric properties to smooth surfaces embedded in R^3. The
notion of totally normal convergence is shown to be equivalent to the convergence
of either one of the following: surface area, intrinsic metric, and
Laplace-Beltrami operators. We further show that totally normal convergence
implies convergence results for shortest geodesics, mean curvature,
and solutions to the Dirichlet problem. This work provides the justifi-
cation for a discrete theory of differential geometric operators defined on
polyhedral surfaces based on a variational formulation.
In this work we deal with the numerical solution of some problems of air pollution.
Since the problems are posed on unbounded domains we have to introduce
artificial boundaries to confine the computational region.
We construct and analyse (discrete) transparent boundary conditions
for an implicit difference scheme.
We discuss the concepts of positivity and monotonicity of
difference schemes and briefly consider these
properties of difference schemes for advection-diffusion equations
arising in problems of air (and water) pollution.
The efficiency and accuracy of our method is illustrated by an example.
We introduce a forward scheme to simulate backward SDEs. Compared
to existing schemes, we avoid high order nestings of conditional
expectations backwards in time. In this way the error, when
approximating the conditional expectation, in dependence of the
time partition is significantly reduced. Besides this generic
result, we present an implementable algorithm and provide an error
analysis for it. Finally, we demonstrate the strength of the new
algorithm by solving some financial problems numerically.
In this paper a method for solving large-scale Sylvester equations is presented. The method is based on the sign function iteration and is particularly
effective for Sylvester equations with factorized right-hand side. In this case, the solution will be computed in factored form as it is for instance required in model reduction.
The hierarchical matrix format and the corresponding formatted arithmetic is integrated in the iteration scheme to make the method feasible for large-scale computations.
We comment on two different notions of the thermodynamical free energy
that are used in Hamiltonian molecular dynamics. Both concepts have
different scopes of applications as was pointed out recently in the
context of high--friction Langevin dynamics. We show that problems
that rely on either definition can be treated in a uniform way using
constrained molecular dynamics. Not only proves this useful in
designing algorithms that sample the free energy landscape, but it
also clarifies the relation between seemingly contradictory results
that are present in the literature.
We consider the problem of designing a network that employs a non-bifurcated shortest path routing
protocol. The network's nodes and the set of potential links are given together with a set of forecasted endto-
end traffc demands. All relevant hardware components installable at links or nodes are considered. The
goal is to simultaneously choose the network's topology, to decide which hardware components to install
on which links and nodes, and to find appropriate routing weights such that the overall network cost is
minimized.
In this paper, we present a mathematical optimization model for this problem and an algorithmic solution
approach based on a Lagrangian relaxation. Computational results achieved with this approach for several
real-world network planning problems are reported.
In diesem Artikel werden die Optimierungsmodelle und -verfahren beschrieben, die bei der Pla-
nung des Kernnetzes und der Zugangsinfrastruktur des X-WiN verwendet wurden. Bis spätestens Januar 2006 wird das
G-WiN als technische Plattform des Deutschen Forschungsnetzes durch das Nachfolgenetz X-WiN abgelöst. Bei der Pla-
nung des X-WiN müssen zahlreiche Entscheidungen getroffen werden, um ein
funktionstüchtiges, qualitativ hochwertiges und wirtschaftliches Netz zu erhalten. Die Auswahl der Kernnetzstandorte
ist dabei von besonderer Bedeutung, da
diese Entscheidung langfristige und große Auswirkungen auf den Netzbetrieb
sowie alle nachfolgenden Planungsschritte hat.
Die dabei zu berücksichtigenden technischen und organisatorischen Alternativen
und Randbedingungen sind jedoch so vielfältig und komplex, dass eine manuelle
Planung mit großen methodischen Unzulänglichkeiten behaftet wäre. Nur durch
den Einsatz mathematisch fundierter Lösungsansätze und weitgehend automatisierter
Verfahren können eine hohe Planungsqualität und -sicherheit gewährleistet und
die vorhandenen Optimierungspotentiale voll ausgeschöpft werden.
Real polynomially normal matrices are studied, i.e., matrices whose adjoint with
respect to the indefinite inner product is a polynomial in the matrix. The set of these matrices is
a subset of indefinite inner product normal matrices that contains all selfadjoint, skew-adjoint, and
unitary matrices, but that is small enough such that all elements can be completely classified. The
essential decomposition of a real polynomially normal matrix is introduced. This is a decomposition
into three parts, one part having real spectrum only and two parts that can be described by two
complex matrices that are polynomially normal with respect to a sesquilinear and bilinear form,
respectively. In the paper, the essential decomposition is used as a tool in order to derive a sufficient
condition for existence of invariant semidefinite subspaces and to obtain canonical forms for real
polynomially normal matrices. In particular, canonical forms for real matrices that are selfadjoint,
skewadjoint, or unitary with respect to an indefinite inner product are recovered.
We present the mathematical theory of general over- and underdetermined
hybrid (switched) systems of differential-algebraic equations
(HDAEs). We give a systematic formulation of HDAEs and discuss existence
and uniqueness of solutions, the numerical computation of the switch
points and how to perform consistent initialization at switch points. We
show how numerical solution methods for DAEs can be adapted for HDAEs
and present a comparison of these methods for the real world example of
simulating an automatic gearbox.
Classes of Cycle Bases
(2005)
In the last years, new variants of the minimum cycle basis (MCB)
problem and new classes of cycle bases have been introduced, as motivated
by several applications from disparate areas of scientific and technological
inquiries. At present, the complexity status of the MCB problem has been
settled only for undirected, directed, and strictly fundamental cycle bases.
In this paper, we over an unitary classification accommodating these
3 classes and further including the following 4 relevant classes: 2-bases (or
planar bases), weakly fundamental cycle bases, totally unimodular cycle
bases, and integral cycle bases. The classification is complete in that, for
each ordered pair (A;B) of classes considered, we either prove that A ? B
holds for every graph or provide a counterexample graph for which A ? B.
The seven notions of cycle bases are distinct (either A ? B or B ? A is
exhibited for each pair (A;B)).
All counterexamples proposed have been designed to be ultimately effective
in separating the various algorithmic variants of the MCB problem
naturally associated to each one of these seven classes. We even provide
a linear time algorithm for computing a minimum 2-basis of a graph. Finally,
notice that the resolution of the complexity status of some of the
remaining three classes would have an immediate impact on practical applications,
as for instance in periodic railway timetabling, only integral
cycle bases are of direct use.
In this work we construct and analyse transparent boundary conditions (TBCs)
for general systems of parabolic equations. These TBCs are constructed for the
fully discrete scheme (-method, finite differences), in order to maintain unconditional
stability of the scheme and to avoid numerical re
ections. The discrete
transparent boundary conditions (DTBCs) are discrete convolutions in time and
are constructed using the solution of the Z{transformed exterior problem. We will
analyse the numerical error of these convolution coefficients caused by the inverse
Z{transformation. Since the DTBCs are non{local in time and thus very costly to
evaluate, we present approximate DTBCs of a sum{of{exponentials form that allow
for a fast calculation of the boundary terms. Finally, we will use our approximate
DTBCs for an example of a
uid stochastic Petri net and present numerical results.
The use of point sets instead ofmeshes becamemore popular during
the last years. We present a new method for anisotropic fairing of a
point sampled surface using an anisotropic geometric mean curvature
flow. The main advantage of our approach is that the evolution
removes noise from a point set while it detects and enhances geometric
features of the surface such as edges and corners. We derive
a shape operator, principal curvature properties of a point set, and
an anisotropic Laplacian of the surface. This anisotropic Laplacian
reflects curvature properties which can be understood as the point
set analogue of Taubin’s curvature-tensor for polyhedral surfaces.
We combine these discrete tools with techniques from geometric
diffusion and image processing. Several applications demonstrate
the efficiency and accuracy of our method.
The operator-splitting methods are based on splitting of the complex problem into a sequence of simpler tasks. A useful method is the iterative splitting method which ensures a consistent approximation in each step. In our paper, we suggest a new method which is based on the combination of the splitting time interval and the traditional iterative operator splitting. We analyse the local splitting error of the method. Numerical examples are given in order to demonstrate the method.
We show that it is not possible to approximate the minimum Steiner tree problem within 1+1/162 unless RP=NP. The currently best known lower bound is 1+ 1/400. The reduction is from Hastad’s nonapproximability result for maximum satisfiability of linear equation modulo 2. The improvement on the nonapproximability ratio is mainly based on the fact that our reduction does not use variable gadgets. This idea was introduced by Papadimitriou and Vempala.
We study the evolution of the size of the largest and the second largest
component in the random intersection graph model which is suited to re
ect
the transitivity (or clustering property) visible in real-world networks. We
show that certain random intersection graphs differ from Gn;p in that they
have only a polynomial jump in the evolution of the size of the largest
component. On the other hand the moment for the jump is still at the
point where the expected vertex degree becomes 1 which is similar to Gn;p.
We also describe a test of our result on a protein network.
The paper provides a condition for differentiability as well as an equivalent criterion
for Lipschitz continuity of singular normal distributions. Such distributions are of interest,
for instance, in stochastic optimization problems with probabilistic constraints, where
a comparatively small (nondegenerate-) normally distributed random vector induces a large
number of linear inequality constraints (e.g. networks with stochastic demands). The criterion
for Lipschitz continuity is established for the class of quasi-concave distributions which
the singular normal distribution belongs to.
We develop and experimentally compare policies for the control of a system
of k elevators with capacity one in a transport environment with ` floors, an idealized
version of a pallet elevator system in a large distribution center of the Herlitz PBS AG
in Falkensee. Each elevator in the idealized system has an individual waiting queue of
infinite capacity. On each floor, requests arrive over time in global waiting queues of
infinite capacity. The goal is to find a policy that, without any knowledge about future
requests, assigns an elevator to each request and a schedule to each elevator so that certain
expected cost functions (e.g., the average or the maximal flow times) are minimized. We
show that a reoptimization policy for minimizing average squared waiting times can be
implemented to run in real-time (1 s) using dynamic column generation. Moreover, in
discrete event simulations with Poisson input it outperforms other commonly used policies
like multi-server variants of greedy and nearest neighbor.
We consider empirical approximations of two-stage stochastic mixed-integer linear programs and derive central
limit theorems for the objectives and optimal values. The limit theorems are based on empirical process theory
and the functional delta method. We also show how these limit theorems can be used to derive confidence intervals
for optimal values via a certain modification of the bootstrapping method.
Quantitative stability of linear multistage stochastic programs is studied. It
is shown that the infima of such programs behave (locally) Lipschitz continuous
with respect to the sum of an Lr-distance and of a distance measure for the filtrations
of the original and approximate stochastic (input) processes. Various issues
of the result are discussed and an illustrative example is given. Consequences for
the reduction of scenario trees are also discussed.
We investigate the problem of maximizing the robust utility functional inf QEQ EQu(X).
We give the dual characterization for its solution for both a complete and an incomplete
market model. To this end, we introduce the new notion of reverse f-projections and
use techniques developed for f-divergences. This is a suitable tool to reduce the robust
problem to the classical problem of utility maximization under a certain measure: the
reverse f-projection. Furthermore, we give the dual characterization for a closely related
problem, the minimization of expenditures given a minimum level of expected utility in
a robust setting and for an incomplete market.
We analyse financial market models in which agents form their demand for an asset on
the basis of their forecasts of future prices and where their forecasting rules may change
over time, as a result of the influence of other traders. Agents will switch from one rule to
another stochastically, and the price and profits process will reflect these switches. Among
the possible rules are “chartist” or extrapolatory rules. Prices can exhibit transient behaviour
when chartists predominate. However, if the probability that an agent will switch to being a
“chartist” is not too high then the process does not explode. There are occasional bubbles
but they inevitably burst. In fact, we prove that the limit distribution of the price process
exists and is unique. This limit distribution may be thought of as the appropriate equilibrium
notion for such markets. A number of characteristics of financial time series can be captured
by this sort of model. In particular, the presence of chartists fattens the tails of the stationary
distribution.
For a nice Markov process such as Brownian motion on a bounded domain, we introduce a non-linear potential operator defined in terms of running
suprema, and we prove a non-linear Riesz representation of a given function as
the sum of a harmonic function and a non-linear potential. The proof involves
a family of optimal stopping problems in analogy to the general construction
of Bank and El Karoui [3], but here the analysis is carried out in terms of
probabilistic potential theory.
In the first part of the article, we characterize distribution-invariant risk measures with convex
acceptance and rejection sets on the level of distributions. It is shown that these risk measures
are closely related to utility-based shortfall risk.
In the second part of the paper, we provide an axiomatic characterization for distribution-invariant
dynamic risk measures of terminal payments. We prove a representation theorem and
investigate the relation to static risk measures. A key insight of the paper is that dynamic consistency
and the notion of "measure convex sets of probability measures" are intimately related.
This result implies that under weak conditions dynamically consistent dynamic risk measures can
be represented by static utility-based shortfall risk.
We derive a continuous time approximation of the evolutionary market selection model of Blume &
Easley (1992). Conditions on the payoff structure of the assets are identified that guarantee convergence. We show that the continuous
time approximation equals the solution of an integral equation
in a random environment. For constant asset returns, the integral equation reduces to an autonomous
ordinary differential equation. We analyze its long-run asymptotic behavior using techniques related to
Lyapunov functions, and compare our results to the benchmark of profit-maximizing investors.
The numerical simulation of very large scale integrated
circuits is an important tool in the development of new
industrial circuits. This topic has received increasing attention
within the last years. The main problem in circuit simulation is
that the model equations lead to differential algebraic equations
(DAEs). One known property of circuit DAEs is that they
may have an index larger than one, i.e., they may contain socalled
hidden constraints. The increased index has numerous
disadvantages on the numerical treatment of circuit DAEs.
The determination of these hidden constraints can be done
investigating the circuit topology. Until now, this information
has only been used for the consistent initialization of the circuit
equations. A recent approach has been to reduce the index of the
circuit DAE in order to improve their numerical behaviour. This
paper will give graph theoretical methods that lead to constraints
in a favorable formulation. Furthermore, the index reduction via
minimal extension will be performed for circuit DAEs, using these
constraints.
Element-based Topological Index Reduction for Differential-Algebraic Equations in Circuit Simulation
(2005)
The numerical simulation of very large scale integrated
circuit is an important tool in the development of new
industrial circuits. In the course of the last years, this topic has
received increasing attention. Common modeling approaches for
circuits lead to differential-algebraic systems (DAEs). In circuit
simulation, these DAEs are known to have index 2, given some
topological properties of the network. This higher index leads
to several undesirable effects in the numerical solution of the
DAEs. Recent approaches try to lower the index to improve
the numerical behaviour. These methods usually involve costly
algebraic transformations of the differential-agebraic equations.
Especially, for large scale circuit equations, these transformations
become too costly to be efficient.
We will present methods that change the topology of the network
itself, while replacing certain elements in oder to obtain a
network that leads to a DAE of index 1. This procedure can
be performed prior to the actual numerical simulation. The
decreasing of the index usually leads to significantly improved
numerical behaviour.
This paper deals with the efficient numerical solution of the two-dimensional one
way Helmholtz equation posed on an unbounded domain. In this case one has to
introduce artificial boundary conditions to confine the computational domain. The
main topic of this work is the construction of so{called discrete transparent boundary
conditions for state-of-the-art parabolic equations methods, namely a split-step
discretization of the high{order parabolic approximation and the split-step Padle
algorithm of Collins. Finally, several numerical examples arising in optics and underwater
acoustics illustrate the efficiency and accuracy of our approach.
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.
We consider a control constrained optimal control problem governed by a semilinear
elliptic equation with nonlocal interface conditions. These conditions occur during the modeling of
diffuse-gray conductive-radiative heat transfer. After stating first-order necessary conditions, secondorder
sufficient conditions are derived that account for strongly active sets. These conditions ensure
local optimality in a Ls-neighborhood whereby the underlying analysis allows to use weaker norms
than L?.
A linear-quadratic elliptic control problem with pointwise box constraints on the
state is considered. The state-constraints are treated by a Lavrentiev type regularization. It is
shown that the Lagrange multiplier associated with the regularized state-constraints are functions
in L2. Moreover, the convergence of the regularized controls is proven for regularization parameter
tending to zero. To solve the problem numerically, an interior point method and a primal-dual active
set strategy are implemented and treated in function space.
Laplace transforms which admit a holomorphic extension to some sector strictly
containing the right half plane and exhibiting a potential behavior are considered. A spectral order,
parallelizable method for their numerical inversion is proposed. The method takes into account the
available information about the errors arising in the evaluations. Several numerical illustrations are
provided.
A new MATLAB toolbox for computing eigenvalues
and invariant subspaces of Hamiltonian and skew-Hamiltonian
matrices is described. Based on orthogonal symplectic decompositions,
the implemented algorithms are both numerically backward
stable and structure-preserving. It will be demonstrated
how this toolbox can be used to address a number of tasks
in systems and control theory, including some model reduction
methods and the computation of the H? norm.
Bei der Produktions- und Handelsplanung treffen Energieversorgungsunternehmen eine Reihe von Entscheidungen unter unsicheren Randbedingungen. Ein Optimierungsmodell für einen mittelfristigen Planungshorizont muss diese Unsicherheiten berücksichtigen, etwa durch Einbeziehung von statistischen Modellen für die zufallsbehafteten Eingangsdaten. Dadurch ist es prinzipiell möglich, Risikobetrachtungen direkt in die Optimierung zu integrieren. Wir demonstrieren in dieser Arbeit die Möglichkeit, spezielle dynamische Risikomaße, so genannte polyedrische Risikomaße, in die Zielfunktion der Optimierung mit aufzunehmen. Im Gegensatz zu vielen anderen Ansätzen wird dadurch die Komplexität des Problems nicht wesentlich erhöht. Das vorgestellte Modell stellt ein Werkzeug zur Entscheidungsunterstützung für kleinere Marktteilnehmer hinsichtlich der Beschaffungsplanung dar. Dabei werden insbesondere konkrete mittelfristig bindende Bezugsverträge mit der Möglichkeit verglichen, die Versorgung in erster Linie auf der Basis von Spot- und Futuremarkt zu planen.
We present an applied mathematical model with stochastic input data for mean-risk optimization of electricity portfolios containing electricity futures as well as several components to satisfy a stochastic electricity demand: electricity spot market, two different types of supply contracts offered by a large power producer, and a combined heat and power production facility with limited capacity. Stochasticity enters the model via uncertain electricity demand, heat demand, spot prices, and future prices. The model is set up as a decision support system for a municipal power utility (price taker) and considers a medium term optimization horizon of one year in hourly discretization. The objective is to maximize the expected overall revenue and, simultaneously, to minimize risk in terms of multiperiod risk measures. Such risk measures take into account intermediate cash values in order to avoid uncertainty and liquidity problems at any time. We compare the effect of different multiperiod risk measures taken from the class of polyhedral risk measures which was suggested in our earlier work.
Transparent boundary conditions (TBCs) are an important tool for the truncation of the compu-
tational domain in order to compute solutions on an unbounded domain. In this work we want
to show how the standard assumption of `compactly supported data' could be relaxed and derive
TBCs for the wide angle parabolic equation directly for the numerical scheme on the discrete level.
With this inhomogeneous TBCs it is not necessary that the starting field lies completely inside the
computational region. However, an increased computational effort must be accepted.
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.
Let (Gt) be an enlargement of the filtration (Ft). Jeulin and Jacod
discussed a sufficient criterion for the inheritance of the semimartingale property
when passing to the larger filtration. We provide alternative proofs of their results
in a more general setting by using decoupling measures and Girsanov's changes of
measure. We derive necessary and sufficient conditions for the embedding of vector
spaces of (Ft)-semimartingales into spaces of (Gt)-semimartingales to be continuous
in terms of generalized entropies of the information increment.
The subject of the present paper is a simplified model for a symmetric bistable system with memory
or delay, the reference model, which in the presence of noise exhibits a phenomenon similar to what
is known as stochastic resonance. The reference model is given by a one dimensional parametrized
stochastic differential equation with point delay, basic properties whereof we check.
With a view to capturing the effective dynamics and, in particular, the resonance-like behavior of
the reference model we construct a simplified or reduced model, the two state model, first in discrete
time, then in the limit of discrete time tending to continuous time. The main advantage of the
reduced model is that it enables us to explicitly calculate the distribution of residence times which
in turn can be used to characterize the phenomenon of noise-induced resonance.
Drawing on what has been proposed in the physics literature, we outline a heuristic method for
establishing the link between the two state model and the reference model. The resonance characteristics
developed for the reduced model can thus be applied to the original model.
We consider potential type dynamical systems in finite dimensions with two meta-stable states.
They are subject to two sources of perturbation: a slow external periodic perturbation of period T
and a small Gaussian random perturbation of intensity ", and therefore mathematically described as
weakly time inhomogeneous diffusion processes. A system is in stochastic resonance provided the small
noisy perturbation is tuned in such a way that its random trajectories follow the exterior periodic
motion in an optimal fashion, i.e. for some optimal intensity "(T). The physicists' favorite measures
of quality of periodic tuning -- and thus stochastic resonance -- such as spectral power amplification or
signal-to-noise ratio have proven to be defective. They are not robust w.r.t. effective model reduction,
i.e. for the passage to a simplified finite state Markov chain model reducing the dynamics to a pure
jumping between the meta-stable states of the original system. An entirely probabilistic notion of
stochastic resonance based on the transition dynamics between the domains of attraction of the meta-
stable states -- and thus failing to suffer from this robustness defect -- was proposed before in the
context of one-dimensional discusions. It is investigated for higher dimensional systems here, by using
extensions and refinements of the Freidlin-Wentzell theory of large deviations for time homogeneous
diffusions. Large deviation principles developed for weakly time inhomogeneous diffusions prove to be
key tools for a treatment of the problem of diffusion exit from a domain and thus for the approach of
stochastic resonance via transition probabilities between meta-stable sets.
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.
A primal interior point method for control constrained optimal control problems
with PDE constraints is considered. Pointwise elimination of the control
leads to a homotopy in the remaining state and dual variables, which is addressed
by a short step pathfollowing method. The algorithm is applied to the
continuous, infinite dimensional problem, where discretization is performed
only in the innermost loop when solving linear equations. The a priori elimination
of the least regular control permits to obtain the required accuracy with
comparatively coarse meshes. Convergence of the method and discretization
errors are studied, and the method is illustrated at two numerical examples.
The paper introduces an identification problem arising in modern regional hyperthermia, a cancer
therapy aiming at heating the tumor by microwave radiation. The task is to identify the highly
individual perfusion, which affects the resulting temperature distribution, from MR measurements.
The identification problem is formulated as an optimization problem. Existence of a solution and
optimality conditions are analyzed. Different regularizations and problem variants are considered. For
the numerical solution, a standard SQP method is used. Sufficient conditions for the convergence of
the method are derived. Finally, numerical examples on artificial as well as clinical data are presented.
The line planning problem is one of the fundamental problems in strategic
planning of public and rail transport. It consists in finding lines
and corresponding frequencies in a transport network such that a given
travel demand can be satisfied. There are (at least) two objectives. The
transport company wishes to minimize operating costs, the passengers
want to minimize travel times. We propose a new multi-commodity
ow model for line planning. Its main features, in comparison to existing
models, are that the passenger paths can be freely routed and
that the lines are generated dynamically. We discuss properties of this
model and investigate its complexity. Results with data for the city of
Potsdam, Germany, are reported.
In this paper we introduce the fare planning problem for public
transport which consists in designing a system of fares maximizing
revenue. We propose a new simple general model for this problem.
It is based on a demand function and constraints for the different
fares. The constraints define the structure of the fare system, e.g.,
distance dependent fares or zone fares. We discuss a simple example
with a quadratic demand function and distance dependent fares. Then
we introduce a more realistic discrete choice model in which passengers
choose between different alternatives depending on the number
of trips per month. We demonstrate the examples by computational
experiments.
Can OR methods help the public transport industry to break even?
How would you build a public transport system? For example, have a look at
Berlin. The BVG, Berlin's public transport company, maintains a network
of 2,423 km, operates 197 lines with 3,286 stops, using 1,554 busses, 1,391
subway cars, and 599 trams from 12 depots, and has 13,409 employees [7].
The BVG currently transports about 800 million passengers per year and
covers about 40% of the total non-pedestrian traffic volume of the city [18].
Does Berlin have a "reasonable" public transportation network? Does
the BVG run a "good" transportation system? Is it "efficient"?
These are difficult questions. In fact, politicians, transportation managers,
customers, taxpayers, etc. frequently employ judgments such as "good"
and "efficient", but nobody can give a defiition what this exactly means.
Since almost every public transportation system in the world is in the red,
the cheapest system is no public transportation at all. On the other hand,
the most convenient system for the passenger - a stop in front of every house
with direct connections to everywhere - is much too expensive. What is the
right compromise? Operations Research has no good answer either - so far.
But OR can improve aspects of public transportation significantly, as we
want to demonstrate in the following.
On the Efficient Generation of Taylor Expansions for DAE Solutions by Automatic Differentiation
(2005)
Under certain conditions the signature method suggested by
Pantiledes and Pryce facilitates the local expansion of DAE solutions
by Taylor polynomials of arbitrary order. The successive calculation of
Taylor coefficients involves the solution of nonlinear algebraic equations
by some variant of the Gauss-Newton method. Hence, one needs to evaluate
certain Jacobians and several right hand sides. Without advocating
a particular solver we discuss how this information can be efficiently
obtained using ADOL-C or similar automatic differentiation packages.3
MIPLIB 2003
(2005)
This paper is about the fourth version of the Mixed Integer Programming Library (MIPLIB).
More than 7 years have been past since the last update. Since the focus of the MIPLIB is to provide a concise set of challenging problems, it became again necessary to purge the library from instances that have become too easy due to improvements in optimizers and computing machinery.
The free slots have been filled by 27 new challenging instances. We give an overview of the new problems and present statistical data for all 60 instances included in the MIPLIB 2003.
A finite volume scheme suitable for nonlinear heat transfer in materials with anisotropic thermal conductivity is formulated, focussing on the difficulties arising from the discretization of complex domains which are typical in the simulation of industrially relevant processes. The discretization is based on unstructured constrained Delaunay triangulations of the domain. For simplicity, it is assumed that the thermal conductivity tensor has vanishing off-diagonal entries and that the anisotropy is independent of the temperature. Numerical simulations verify the accuracy of the method in two test cases where a closed-form solution is available. Further results demonstrate the effectiveness of the method in computing the heat transfer in a complex growth apparatus used in crystal growth.
Using a mathematical heat transfer model including anisotropic heat conduction, radiation, and radio frequency (RF) heating, we perform numerical computations of the temperature field in an axisymmetric growth apparatus during sublimation growth of silicon carbide (SiC) bulk single crystals by physical vapor transport (PVT) (modified Lely method). Because it is not unusual for the thermal insulation of a PVT growth apparatus to possess an anisotropic thermal conductivity, we numerically study the influence that this anisotropic thermal conductivity has on the temperature field in the growth chamber. Moreover, we also study the influence of the thickness of the insulation. Our results show that, depending on the insulation's orientation, even a moderate anisotropy in the insulation can result in temperature variations of more than 100 K at the growing crystal's surface, which should be taken into account for the simulation as well as for the design of a PVT growth apparatus.
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.
Palindromic polynomial eigenvalue problems and related classes of structured eigenvalue problems are
considered. These structures generalize the concepts of symplectic and Hamiltonian matrices to matrix polynomials.
We discuss several applications where these matrix polynomials arise, and show how linearizations can be derived that
re
ect the structure of all these structured matrix polynomials and therefore preserve symmetries in the spectrum.
Given a directed graph D = (V;A), we consider its cycle space CD, i.e. the vector
subspace of Q|A| spanned by the incidence vectors of the oriented cycles of D. An
oriented cycle of D is just any cycle of the underlying undirected graph of D along
with an orientation; its incidence vector is 0 on the arcs not included, while, for the
included arcs, it is +1 on the arcs oriented according to the orientation and -1 on
the arcs going backward. Assume a nonnegative weight wa ? R+ is associated to
each arc a of D. We can extend the weighting w to subsets F of A and to families F
of such subsets by dening w(F) := ?f?F w(f) and w(F) := ?F?F w(F). Given
the pair (D;w), we are interested in computing a minimum weight basis of CD.
This problem is strongly related to the classical problem of computing a minimum
cycle basis of an undirected graph. In 1987, Horton developed the first polynomial
time algorithm for computing a minimum cycle basis of an undirected graph. As for
directed graphs, the first algorithm for computing a minimum directed cycle basis
is due to Kavitha and Mehlhorn. Its asymptotic complexity is ~O (m4n).
In this paper, we show how the original approach of Horton can be actually pursued
also in the context of directed graphs, while retaining its simplicity. This both
allows for a practical ~O(m4n) adaptation of Horton's original algorithm requiring
only minor modifications in the actual code and for a more involved ~O(mw+1n)
solution. At the end, we discuss the applicability of this approach to more specialized
classes of directed cycle bases, namely, integral cycle bases and generalized
fundamental cycle bases.
We discuss the nonstandard problem of using the finite difference
method to solve numerically a partial differential equation posed on
an unbounded domain. We propose different strategies to construct
so-called discrete articial boundary conditions (ABCs) and present
an efficient implementation by the sum-of-exponential ansatz. The
derivation of the ABCs is based on the knowledge of the exact solution,
the construction of asymptotic solutions or the usage of a continued
fraction expansion to a second-order difference equation. Our approach
is explained by means of three different types of partial differential
equations arising in option pricing, in quantum mechanics and
in (underwater) acoustics. Finally, we conclude with an illustrating
numerical example from underwater acoustics showing the superiority
of our new approach.
We consider the problem of satisfying the maximum number of constraints
of an instance of the Periodic Event Scheduling Problem (PESP). This is
a key issue in periodic railway timetable construction, and has many other applications,
e.g. for traffic light scheduling.
We generalize two (in-) approximability results, which are known for MAXIMUM-
K-COLORABLE-SUBGRAPH. Moreover, we present a deterministic combinatorial
polynomial time algorithm. Its output violates only very few constraints
for five real-world instances.
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.
A class of optimal control problems for a semilinear elliptic equations with mixed
control-state constraints is considered. The existence of bounded and measurable Lagrange multipliers
is proven. As a particular application, the Lavrentiev type regularization of pointwise state
constraints is discussed. Here, the existence of associated regular multipliers is shown, too.
In this work we are interested in the numerical solution of a coupled model of
differential algebraic equations (DAEs) and partial differential equations (PDEs).
The DAEs describe the behavior of an electrical circuit that contains semiconductor
devices and the partial differential equations constitute drift-diffusion equations
modelling the semiconductor devices in the circuit.
After space discretization using a finite element method, the coupled system results
in a differential-algebraic system with a properly stated leading term. We
investigate the structure and the properties of this DAE system. In particular, we
develop structural criteria for the DAE index. This is of basic interest since DAE
properties like stability, existence and uniqueness of solutions depend strongly on
its index.
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.
Revlex-Initial 0/1-Polytopes
(2005)
Modern electricity portfolio and risk management models represent multistage stochastic programs. The input of such programs consists in a finite set of scenarios having the form of a scenario tree. They model the probabilistic information on random data (electrical load, stream flows to hydro units, market prices of fuel and electricity). Since the corresponding deterministic equivalents of multistage stochastic programs are mostly large scale, one has to find significant tree-structured scenarios. Our approach to generate multivariate scenario trees is based on recursive deletion and bundling of scenarios out of some given (possibly large) scenario set originating from historical or simulated data. The procedure makes use of certain Monge-Kantorovich transportation distances for multivariate probability distributions. We report on computational results for generating load-inflow scenario
trees based on realistic data of EDF Electricité de France.
An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, forward and backward approaches are developed for generating scenario trees out of an initial fan of individual scenarios. Both approaches are motivated by the recent stability result in [15] for optimal values of multistage stochastic programs. They are based on upper bounds for the two relevant ingredients of the stability estimate, namely, the probabilistic and the filtration distance, respectively. These bounds allow to control the process of recursive scenario reduction [13] and branching. Numerical experience is reported for constructing multivariate scenario trees in electricity portfolio management.
We consider a time-dependent optimal control problem, where the state
evolution is described by an ODE. There is a variety of methods for the treatment
of such problems. We prefer to view them as boundary value problems and apply to
them the Riccati approach for non-linear BVPs with separated boundary conditions.
There are many relationships between multiple shooting techniques, the Riccati
approach and the Pantoja method, which describes a computationally efficient
stage-wise construction of the Newton direction for the discrete-time optimal control
problem.
We present an efficient implementation of this approach. Furthermore, the wellknown
checkpointing approach is extended to a `nested checkpointing` for multiple
transversals. Some heuristics are introduced for an efficient construction of nested
reversal schedules. We discuss their benefits and compare their results to the optimal
schedules computed by exhaustive search techniques.
Systems of stiff ordinary differential equations (ODEs) can be integrated
properly only by implicit methods. For that purpose, one usually has to
solve a system of nonlinear equations at each time step. This system of equations
may be solved by variants of Newton's method. Here, the main computing effort lies
in forming and factoring the Jacobian or a suitable approximation to it.
In this paper, we examine a new approach of constructing an appropriate quasi-
Newton approximation for solving stiff ODEs. The method makes for the first time
explicit use of tangent and adjoint information that can be obtained using the forward
and the reverse mode of algorithmic differentiation (AD). We elaborate the
conditions for invariance with respect to linear transformations of the state space
and thus similarity transformations of the Jacobian. One new updating variant that
yields such an invariant method is presented. Numerical results for Runge-Kutta
methods and linear multi-step methods are discussed.
We present a mathematical model with stochastic input data for mean-risk optimization of electricity portfolios containing
several physical components and energy derivative products. The model is designed for a medium term optimization horizon
of one year in hourly discretization. With the objective of maximization of the mean book value of the portfolio at the end of
optimization horizon simultaneously several risk measures are taken into account. We present numerical results for a largescale
realistic problem adapted to a municipal utility and study the effects of varying weighting of risk on the book value of
the portfolio during the whole time horizon.
One-shot optimization aims at attaining feasibility and optimality simultane-
ously, especially on problems where even the linearized constraint equations
cannot be resolved economically. Here we consider a scenario where forming
and factoring the active Jacobian is out of the question, as is for example the
case when the constraints represent some discretization of the Navier Stokes
equation. Assuming that the 'user' provides us with a linearly converging solver
that gradually restores feasibility after each change in the design variables, we
derive a corresponding adjoint iteration and attach an optimization (sub)step.
The key question addressed is how the approximate reduced gradient generated
by the adjoint iteration should be preconditioned in order to achieve overall
convergence at a reasonable speed. An eigenvalue analysis yields necessary
conditions on the preconditioning matrix, which are typically not satised by
the familiar reduced Hessian. Some other projection of the Lagrangian Hessian
appears more promising and is found to work very satisfactorily on a nonlinear
test problem.
The analyzed approach is one-step in that the normal, dual and design variables
are always updated simultaneously on the basis of one function evaluation and
its adjoint. Multi-step variants are promising but remain to be investigated.
Canonical forms are developed for several sets of complex matrices that are normal
with respect to an indefinite inner product induced by a nonsingular Hermitian,
symmetric, or skew-symmetric matrix. The most general result covers the case of
polynomially normal matrices, i.e., matrices whose adjoint with respect to the indefinite
inner product is a polynomial of the original matrix. From this result, canonical
forms for matrices that are selfadjoint, skewadjoint, or unitary with respect to the
given indefinite inner product are derived.
This work is concerned with transparent boundary conditions (TBCs) for systems of Schrödinger-type equations, namely
the time-dependent kp-Schrödinger equations. These TBCs are constructed for the fully discrete scheme (Crank-Nicolson,
finite differences), in order to maintain unconditional stability of the scheme and to avoid numerical reflections. The discrete
transparent boundary conditions (DTBCs) are discrete convolutions in time and are constructed using the Z-transformed
solution of the exterior problem. We will analyse the numerical error of these convolution coeffficients caused by the inverse
Z-transformation. Since the DTBCs are non-local in time and thus very costly to evaluate, we present approximate DTBCs
of a sum-of-exponentials form that allow for a fast calculation of the boundary terms.
We discuss the state of the art in numerical solution methods for large scale polynomial or
rational eigenvalue problems. We present the currently available solution methods such as
the Jacobi-Davidson, Arnoldi or the rational Krylov method and analyze their properties.
We briefly introduce a new linearization technique and demonstrate how it can be used to
improve structure preservation and with this the accuracy and efficiency of linearization based
methods. We present several recent applications where structured and unstructured nonlinear
eigenvalue problems arise and some numerical results.
In Kolodko & Schoenmakers (2004) and Bender & Schoenmakers (2004) a policy iteration was introduced which allows to achieve tight lower approximations of the price for early exercise options via a nested Monte-Carlo simulation in a Markovian setting. In this paper we enhance the algorithm by a scenario selection method. It is demonstrated by numerical examples that the scenario selection can significantly reduce the number of actually performed inner simulations, and thus can heavily speed up the method (up to factor 10 in some examples). Moreover, it is shown that the modified algorithm retains the desirable properties of the original one such as the monotone improvement property, termination after a finite number of iteration steps, and numerical stability.
We propose a valuation method for callable structures in a multi-factor Libor model which are path-dependent in the sense that, after calling, one receives a sequence of cash-flows in the future, instead of a well specified cash-flow at the calling date. The method is based on a Monte Carlo procedure for standard Bermudans recently developed in Kolodko & Schoenmakers (2004), and is applied to the cancelable snowball interest rate swap. The proposed procedure is quite generic, straightforward to implement, and can be easily adapted to other related path-dependent products.
Polzehl and Spokoiny (2000) introduced the adaptive weights smoothing
(AWS) procedure 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 assumption
can be rather restrictive for a number of potential applications. Here we
present a new method based on the ideas of propagation and separation
which extends the AWS procedure to the case of an arbitrary local linear
parametric structure. We also establish some important results about
properties of the new ‘propagation-separation’ procedure including rate
optimality in the pointwise and global sense. The performance of the
procedure is illustrated by examples for local polynomial regression and
by applications to artificial and real images.