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 method for noise removal of arbitrary surfaces
meshes is presented which focuses on the preservation
and sharpening of non-linear geometric features such
as curved surface regions and feature lines. Our method
uses a prescribed mean curvature flow (PMC) for simplicial
surfaces which is based on three new contributions:
1. the definition and efficient calculation of a
discrete shape operator and principal curvature properties
on simplicial surfaces that is fully consistent with
the well-known discrete mean curvature formula, 2. an
anisotropic discrete mean curvature vector that combines
the advantages of the mean curvature normal with
the special anisotropic behaviour along feature lines of
a surface, and 3. an anisotropic prescribed mean curvature
flow which converges to surfaces with an estimated
mean curvature distribution and with preserved nonlinear
features. Additionally, the PMC flow prevents
boundary shrinkage at constrained and free boundary
segments.
We study perturbations of a stochastic program with a probabilistic constraint and r-concave original probability distribution. First we improve our earlier results substantially and provide conditions implying Hölder continuity properties of the solution sets w.r.t. the Kolmogorov distance of probability distributions. Secondly, we derive an upper Lipschitz continuity property for solution sets under more restrictive conditions on the original program and on the perturbed probability measures. The latter analysis applies to linear-quadratic models and is based on work by Bonnans and Shapiro. The stability results are illustrated by numerical tests showing the different asymptotic behaviour of parametric and nonparametric estimates in a program with a normal probabilistic constraint.
We consider stochastic programs with risk measures in the objective and study
stability properties as well as decomposition structures. Thereby we place emphasis on dynamic
models, i.e., multistage stochastic programs with multiperiod risk measures. In this context, we
define the class of polyhedral risk measures such that stochastic programs with risk measures taken
from this class have favorable properties. Polyhedral risk measures are defined as optimal values of
certain linear stochastic programs where the arguments of the risk measure appear on the right-hand
side of the dynamic constraints. Dual representations for polyhedral risk measures are derived and
used to deduce criteria for convexity and coherence. As examples of polyhedral risk measures we
propose multiperiod extensions of the Conditional-Value-at-Risk.
We consider multistage stochastic optimization models containing nonconvex constraints, e.g.,
due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding
decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on
convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes.
The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal
decomposition. The second group of results concerns large stochastic optimization models with loosely coupled
components. The results provide conditions implying relations between the duality gaps of geographical
decomposition and the duality gaps for scenario and nodal decomposition, respectively.
Portfolio and risk management problems of power
utilities may be modeled by multistage stochastic programs. These
models use a set of scenarios and corresponding probabilities
to model the multivariate random data process (electrical load,
stream flows to hydro units, and fuel and electricity prices). For
most practical problems the optimization problem that contains
all possible scenarios is too large. Due to computational complexity
and to time limitations this program is often approximated by
a model involving a (much) smaller number of scenarios. The proposed
reduction algorithms determine a subset of the initial scenario
set and assign new probabilities to the preserved scenarios.
The scenario tree construction algorithms successively reduce the
number of nodes of a fan of individual scenarios by modifying the
tree structure and by bundling similar scenarios. Numerical experience
is reported for constructing scenario trees for the load
and spot market prices entering a stochastic portfolio management
model of a German utility
We present a mixed-integer multistage stochastic programming model for the short term unit commitment of a hydro-thermal power system under uncertainty in load, inflow to reservoirs, and prices for fuel and delivery contracts. The model is implemented for uncertain load and tested on realistic data from a German power utility. Load scenario trees are generated by a procedure consisting of two steps: (i) Simulation of load scenarios using an explicit respresentation of the load distribution and (ii) construction of a tree out of these scenarios. The dimension of the corresponding mixed-integer programs ranges up to 200,000 binary and 350,000 continuous variables. The model is solved by a Lagrangian-based decomposition strategy exploiting the loose coupling structure. Solving the Lagrangian dual by a proximal bundle method leads to a successive decomposition into single unit subproblems, which are solved by specific algorithms. Finally, Lagrangian heuristics are used to construct nearly optimal first stage decisions.
Mathematical models for the electricity portfolio
management of a utility that owns a hydro-thermal generation system
and trades on the power market often lead to complex stochastic
optimization problems. We present a new approach to solving
stochastic hydro-storage subproblems that occur when stochastic
Lagrangian relaxation is applied to solving such models. The special
structure of such hydro-storage subproblems allows the design
of a stochastic network flow algorithm. The algorithm represents
a stochastic extension of a relaxation method, that algorithmically
solves the linear minimum cost flow problem. It is based on the
iterative improvement of dual costs. Numerical experience of the
new algorithm is reported and its performance is compared with
that of standard LP software .
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
have to be constructed for the discrete scheme, in order to maintain stability and to avoid
numerical re
ections. The discrete transparent boundary conditions (DTBCs) are constructed
using the solution of the exterior problem with Laplace and Z-transformation respectively.
Hence we will analyse the numerical error caused by the inverse Z-transformation. Since
these DTBCs are non-local in time and thus very costly, we present approximate DTBCs,
that allow a fast calculation of the boundary terms.
It is known that for each combinatorial type of convex 3-dimensional
polyhedra, there is a representative with edges tangent to the unit sphere.
This representative is unique up to projective transformations that fix the unit
sphere. We show that there is a unique representative (up to congruence) with
edges tangent to the unit sphere such that the origin is the barycenter of the
points where the edges touch the sphere.
Given a set of service requests (events), a set of guided servers (units),
and a set of unguided service contractors (conts), the vehicle dispatching problem
VDP is the task to find an assignment of events to units and conts as well as tours
for all units starting at their current positions and ending at their home positions
(dispatch) such that the total cost of the dispatch is minimized.
The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit
costs consist of driving costs, service costs and overtime costs; cont costs consist of
a fixed cost per service; event costs consist of late costs linear in the late time, which
occur whenever the service of the event starts later than its deadline.
The program ZIBDIP based on dynamic column generation and set partitioning
yields solutions on heavy-load real-world instances (215 events, 95 units) in less
than a minute that are no worse than 1% from optimum on state-of-the-art personal
computers.
We consider a particle constrained to a submanifold ? of the configuration space
Rm. Using that the notion of holonomic constraints coincides with integrability of the corresponding
vector field, we show how this property naturally determines local coordinates on ? . We give a
rigorous justification for the calculation of the mean force along the constrained coordinates, and
we provide a concise geometrical interpretation of the different contributions to the mean force.
Our approach gives rise to a generalisation of the Fixman Theorem which is well known and widely
used in molecular dynamics applications. It further allows for working out a Hybrid Monte-Carlo
based algorithm that can be used to compute arbitrary statistical quantities from constrained
simulations such as the mean force in the context of thermodynamic free energy statistics.
Models for physical systems often take the form of implicit or behavioral models. One important problem is the
identification of which combinations of variables are good candidtates for control variables. This paper first provides one
solution to this problem for linear time varying systems. The solution is shown to be related to a general optimization
problem. It is then shown how these same algorithms can be extended to a large and important class of nonlinear systems.
In this paper the numerical approximation of solutions of Itô stochastic differential
equations is considered, in particular for equations with a small parameter ? in the noise coex-
cient. We construct stochastic linear multi-step methods and develop the fundamental numerical
analysis concerning their mean-square consistency, numerical stability in the mean-square sense and
mean-square convergence. For the special case of two-step Maruyama schemes we derive conditions
guaranteeing their mean-square consistency. Further, for the small noise case we obtain expansions
of the local error in terms of the stepsize and the small parameter ?. Simulation results using several
explicit and implicit stochastic linear k-step schemes, k = 1; 2, illustrate the theoretical findings.
A strategy for controlling the stepsize in the numerical integration of stochastic
differential equations (SDEs) is presented. It is based on estimating the p-th mean of
local errors. The strategy leads to deterministic stepsize sequences that are identical
for all paths. For the family of Euler schemes for SDEs with small noise we derive
computable estimates for the dominating term of the p-th mean of local errors
and show that the strategy becomes efficient for reasonable stepsizes. Numerical
experience is reported for test examples including scalar SDEs and a stochastic
circuit model.
Single-hop WDM networks with a central Passive Star Coupler (PSC), as well as single-hop networks with
a central Arrayed-Waveguide Grating (AWG) and a single transceiver at each node, have been extensively
studied as solutions for the quickly increasing amounts of unicast and multicast traffic in the metropolitan
area. The main bottlenecks of these networks are the lack of spatial wavelength reuse in the studied PSC
based networks and the single transceiver in the studied AWG based metro WDM networks. In this paper
we develop and evaluate the FT EE ???? FREE AWG network, which is based on a central AWG and has arrays
of fixed-tuned transmitters and receivers at each node. Transceiver arrays are a mature technology, making
the proposed network practical. In addition, the transmitter arrays allow for high speed signaling over the
AWG while the receiver arrays relieve the receiver bottleneck arising from multicasting in conjunction with
spatial wavelength reuse on the AWG. Our results from probabilistic analysis and simulation indicate that
the FTEE ???? FREE AWG network gives particularly good throughput-delay performance for a mix of unicast
and multicast traffic.
Metastability in reversible diffusion processes I. Sharp asymptotics for capcities and exit times
(2004)
We develop a potential theoretic approach to the problem of metastability for reversible diffusion processes with generators of the form +rF ( )r on R or subsets of , where F is a smooth function with finitely many local minima. In analogy to previous work in discrete Markov chains, we show that metastable exit times from the attractive domains of the minima of F can be related, up to multiplicative errors that tend to one as # 0, to the capacities of suitably constructed sets. We show that this capacities can be computed, again up to multiplicative errors that tend to one, in terms of local characteristics of F at the starting minimum and the relevant saddle points. As a result, we are able to give the first rigorous proof of the classical Eyring-Kramers formula in dimension larger than 1. The estimates on capacities make use of their variational representation and monotonicity properties of Dirichlet forms. The methods developed here are extensions of our earlier work on discrete Markov chains to continuous diffusion processes.
We continue the analysis of the problem of metastability for reversible diffusion processes,
initiated in [BEGK3], with a precise analysis of the low-lying spectrum of the generator.
Recall that we are considering processes with generators of the form 1+rF()r on Rd or subsets
of Rd , where F is a smooth function with finitely many local minima. Here we consider only
the generic situation where the depths of all local minima are different. We show that in general
the exponentially small part of the spectrum is given, up to multiplicative errors tending to one, by
the eigenvalues of the classical capacity matrix of the array of capacitors made of balls of radius
centered at the positions of the local minima of F. We also get very precise uniform control on the
corresponding eigenfunctions. Moreover, these eigenvalues can be identified with the same precision
with the inverse mean metastable exit times from each minimum. In [BEGK3] it was proven
that these mean times are given, again up to multiplicative errors that tend to one, by the classical
Eyring–Kramers formula.
In this survey, we show that various stochastic optimization problems arising in
option theory, in dynamical allocation problems, and in the microeconomic theory
of intertemporal consumption choice can all be reduced to the same problem of
representing a given stochastic process in terms of running maxima of another
process. We describe recent results of Bank and El Karoui (2002) on the general
stochastic representation problem, derive results in closed form for Lévy processes
and diffusions, present an algorithm for explicit computations, and discuss some
applications.
This paper is concerned with the effficient implementation of transparent boundary conditions
(TBCs) for wide angle parabolic equations (WAPEs) assuming cylindrical symmetry.
In [1] a discrete TBC of convolution type was derived from the fully discretized whole?space
problem that is reflection?free and yields an unconditionally stable scheme. Since the discrete
TBC includes a convolution with respect to range with a weakly decaying kernel, its
numerical evaluation becomes very costly for long-range simulations.
As a remedy we construct new approximative transparent boundary conditions involving
exponential sums as an approximation to the convolution kernel. This special approximation
enables us to use a fast evaluation of the convolution type boundary condition.
This new approach was outlined in detail in [2] for the standard "parabolic" equation.
Differential algebraic equations with properly stated leading term are equations of the form A(x(t),t)(d(x(t),t))'+b(x(t),t)=0 with in some sense well-matched coefficients. Systems resulting from the modified nodal analysis (MNA) in circuit simulation promptly fit into this form. Recent results concerning solvability and numerical treatment of those equations are discussed. An index notion that works via linearization is given. This allows for index criteria just in terms of the coefficients A,d,b and their first partial derivatives, no further derivative arrays are used.
We present a way to efficiently treat the well-known transparent boundary
conditions for the Schrödinger equation. Our approach is based on two ideas:
firstly, to derive a discrete transparent boundary condition (DTBC) based on the
Crank-Nicolson finite difference scheme for the governing equation. And, secondly,
to approximate the discrete convolution kernel of DTBC by sum-of-exponentials for
a rapid recursive calculation of the convolution. We illustrate the efficiency of the
proposed method on several examples.
The index of DAE systems arising from linear quadratic optimal control problems is considered. Necessary and sufficient conditions ensuring regularity with tractability index one are proved. Then, it is shown that if the control problem DAE is regular with index one and if the leading term of the DAE to be controlled is given by one full-column-rank and one full-row-rank matrix, then it has a Hamiltonian inherent explicit ODE. For problems with regular index zero or index one DAEs to be controlled, the DAE of the control problem is shown to be regular with tractability index one or three, depending on whether the control coefficient R is singular.
By the use of the corresponding shift matrix, the paper gives a criterion for the unique solvability of linear boundary value problems posed for linear differential algebraic equations up to index 2 with well-matched leading coefficients. The solution is constructed by a proper Green function. Another characterization of the solutions is based upon the description of arbitrary affine linear subspaces of solutions to linear differential algebraic equations in terms of solutions to the adjoint equation. When applied to boundary value problems, the result provides a constructive criterion for unique solvability and allows reducing the problem to initial value problems and linear algebraic equations.
We consider a particle constrained to a submanifold ? of the
configuration space Rm. Using that the notion of holonomic constraints coincides
with integrability of the corresponding vector field, we show how this property
naturally determines local coordinates on ?. We give a rigorous justification for
the calculation of the mean force along a constrained coordinate, and we provide
a concise geometrical interpretation of the different contributions to the mean
force in terms of the unconstrained vector field and extrinsic curvature properties
of ? in Rm. Our approach gives rise to a Hybrid Monte-Carlo based algorithm
that can be used to compute the mean force acting on selected coordinates in the
context of thermodynamic free energy statistics.
We analyze an interactive model of credit ratings where external shocks, initially
affecting only a small number of firms, spread by a contagious chain reaction to the
entire economy. Counterparty relationships along with discrete adjustments of credit
ratings generate a transition mechanism that allows the financial distress of one firm
to spill over to its business partners. Such a contagious infectious of financial distress
constitutes a source of intrinsic risk for large portfolios of credit sensitive securities that
cannot be “diversified away.” We provide a complete characterization of the fluctuations
of credit ratings in large economies when adjustments follow a threshold rule. We also
analyze the effects of downgrading cascades on aggregate losses of credit portfolios. We
show that the loss distribution has a power-law tail if the interaction between different
companies is strong enough.
Stability of Linear Stochastic Difference Equations in Strategically Controlled Random Environments
(2004)
We consider the stochastic sequence fYtgt2N defined recursively by the linear relation
Yt+1 = AtYt+Bt in a random environment. The environment is described by the stochastic
process f(At;Bt)gt2N and is under the simultaneous control of several agents playing a
discounted stochastic game. We formulate sufficient conditions on the game which ensure
the existence of Nash equilibrium in Markov strategies which has the additional property
that, in equilibrium, the process fYtgt2N converges in distribution to a stationary regime.
We study the effect of investor inertia on stock price fluctuations with a market microstructure
model comprising many small investors who are inactive most of the time.
It turns out that semi-Markov processes are tailor made for modelling inert investors.
With a suitable scaling, we show that when the price is driven by the market imbalance,
the log price process is approximated by a process with long range dependence
and non-Gaussian returns distributions, driven by a fractional Brownian motion. Consequently,
investor inertia may lead to arbitrage opportunities for sophisticated market
participants. The mathematical contributions are a functional central limit theorem for
stationary semi-Markov processes, and approximation results for stochastic integrals
of continuous semimartingales with respect to fractional Brownian motion.
We consider a financial market model with a large number of interacting
agents. Investors are heterogeneous in their expectations
about the future evolution of an asset price process. Their current
expectation is based on the previous states of their “neighbors” and
on a random signal about the “mood of the market.” We analyze the
asymptotics of both aggregate behavior and asset prices. We give sufficient
conditions for the distribution of equilibrium prices to converge to
a unique equilibrium, and provide a microeconomic foundation for the
use of diffusion models in the analysis of financial price fluctuations.
We consider general economies in which rational agents interact locally. The local aspect
of the interactions is designed to represent in a simple abstract way social interactions, that
is, socioeconomic environments in which markets do not mediate all of agents' choices, and
each agent's choice might be in part determined, for instance, by family, peer group, or ethnic
group effects. We study static as well as dynamic infinite horizon economies; we allow for
economies with incomplete information, and we consider jointly global and local interactions,
to integrate e.g., global externalities and markets with peer and group effects. We provide
conditions under which such economies have rational expectations equilibria.
We illustrate the effects of local interactions when agents are rational by studying in detail
the equilibrium properties of a simple economy with quadratic preferences which captures, in
turn, local preferences for conformity, habit persistence, and preferences for status or adherence
to aggregate norms of behavior.
We give sufficient conditions for a non-zero sum discounted stochastic game with
compact and convex action spaces and with norm-continuous transition probabilities,
but with possibly unbounded state space, to have a Nash equilibrium in homogeneous
Markov strategies that depends in a Lipschitz continuous manner on the current state. If
the underlying state space is compact this yields the existence of a stationary equilibrium.
Stochastic games with weakly interacting players provide a probabilistic framework within
which to study strategic behavior in models of non-market interactions.
This paper addresses the regularization of pointwise state constraints in optimal
control problems. By analyzing the associated dual problem, it is shown that the regularized problems
admit Lagrange multipliers in L2-spaces. Under a certain boundedness assumption, the solution of
the regularized problem converges to the one of the original state constrained problem. The results
of our analysis are confirmed by numerical tests.
An optimal control problem for a 2-d elliptic equation is investigated with pointwise control constraints.
This paper is concerned with discretization of the control by piecewise constant functions. The state and
the adjoint state are discretized by linear finite elements. Approximations of the optimal solution of the continuous
optimal control problem will be constructed by a projection of the discrete adjoint state. It is proved that these
approximations have convergence order h2.
We provide a number of new construction techniques for cubical complexes and cubical
polytopes, and thus for cubifications (hexahedral mesh generation). As an application we
obtain an instance of a cubical 4-polytope that has a non-orientable dual manifold (a Klein
bottle). This confirms an existence conjecture of Hetyei (1995).
More systematically, we prove that every normal crossing codimension one immersion of
a compact 2-manifold into R3 is PL-equivalent to a dual manifold immersion of a cubical
4-polytope. As an instance we obtain a cubical 4-polytope with a cubation of Boy's surface
as a dual manifold immersion, and with an odd number of facets. Our explicit example has
17 718 vertices and 16 533 facets. Thus we get a parity changing operation for 3-dimensional
cubical complexes (hexa meshes); this solves problems of Eppstein, Thurston, and others.
We discuss solvers for Sylvester, Lyapunov, and Stein equations
that are available in the SLICOT Library (Subroutine
Library In COntrol Theory). These solvers offer improved
efficiency, reliability, and functionality compared to corresponding
solvers in other computer-aided control system design
packages. The performance of the SLICOT solvers is
compared with the corresponding MATLAB solvers.
The paper presents a unified approach to local likelihood estimation
for a broad class of nonparametric models, including e.g. the regression,
density, Poisson and binary response model. The method extends
the adaptive weights smoothing (AWS) procedure introduced in Polzehl
and Spokoiny (2000) in context of image denoising. Performance of the
proposed procedure is illustrated by a number of numerical examples
and applications to density or volatility estimation, classification and
estimation of the tail index parameter. We also establish a number of
important theoretical results on properties of the proposed procedure.
The adaptive weights smoothing (AWS) procedure was introduced in
Polzehl and Spokoiny (2000) in the context of image denoising. The
procedure has some remarkable properties like preservation of edges and
contrast, and (in some sense) optimal reduction of noise. The procedure
is fully adaptive and dimension free. Simulations with artificial images
show that AWS is superior to classical smoothing techniques especially
when the underlying image function is discontinuous and can be well
approximated by a piecewise constant function. However, the latter as-
sumption can be rather restrictive for a number of potential applications.
Here the AWS method is generalized to the case of an arbitrary local lin-
ear parametric structure. We also establish some important results about
properties of the AWS procedure including the so called "propagation
condition" and spatial adaptivity. The performance of the procedure is
illustrated by examples for local polynomial regression in univariate and
bivariate situations.
Error estimates for the numerical approximation of boundary semilinear elliptic control problems
(2004)
We study the numerical approximation of boundary optimal control problems governed
by semilinear elliptic partial differential equations with pointwise constraints on the control.
The analysis of the approximate control problems is carried out. The uniform convergence of discretized
controls to optimal controls is proven under natural assumptions by taking piecewise constant
controls. Finally, error estimates are established.
Regular Lagrange multipliers for control problems with mixed pointwise control-state constraints
(2004)
A class of quadratic optimization problems in Hilbert spaces is considered, where
pointwise box constraints and constraints of bottleneck type are given. The main focus is to prove the
existence of regular Lagrange multipliers in L2-spaces. This question is solved by investigating the
solvability of a Lagrange dual quadratic problem. The theory is applied to different optimal control
problems for elliptic and parabolic partial differential equations with mixed pointwise control-state
constraints.
Let Ex be a collection of i.i.d. exponential random
variables. Symmetric Bouchaud’s model on Z2 is a Markov chain
X(t) whose transition rates are given by wxy = ν exp(−βEx ) if x,
y are neighbours in Z2 . We study the behaviour of two correlation functions: P[X(tw + t) = X(tw )] and P X(t ) = X(tw )∀t ∈
[tw , tw + t] . We prove the (sub)aging behaviour of these functions
when β > 1.
A popular model to describe credit risk in practice is CreditRisk
+
and in
this paper a Fourier inversion to obtain the distribution of the credit loss is
proposed. A deeper analysis of the Fourier transformation showed that there
are at least two methods to obtain the distribution although the corresponding
characteristic function is not integrable.
The CreditRisk
+
model will be extended such, that general dependent sec-
tor variables can be taken into consideration, for example dependent lognormal
sector variables. Then the transfer to a continuous time model will be per-
formed and the sector variables become processes, more precisely geometric
Brownian motions.
To have a time continuous credit risk model is an important step to combine
this model with market risk. Additionally a portfolio model will be presented
where the changes of the spreads are driven by the sector variables. Using a
linear expansion of the market risk, the distribution of this portfolio can be
determined. In the special case that there is no credit risk, this model yields
the well known Delta normal approach for market risk, hence a link between
credit risk and market risk has been established.
The CreditRisk model launched by CSFB in 1997 is widely used by practitioners in the banking sector as a simple means for the quantification of credit
risk, primarily of the loan book. We present an alternative numerical recursion scheme for CreditRisk, equivalent to an algorithm recently proposed by
Giese, based on well-known expansions of the logarithm and the exponential
of a power series. We show that it is advantageous to the Panjer recursion
advocated in the original CreditRisk
document, in that it is numerically stable. The crucial stability arguments are explained in detail. Furthermore, the
computational complexity of the resulting algorithm is stated.
We introduce a new Monte Carlo method for constructing the exercise
boundary of an American option in a generalized Black-Scholes framework.
Based on a known exercise boundary, it is shown how to price and hedge the
American option by Monte Carlo simulation of suitable probabilistic represen-
tations in connection with the respective parabolic boundary value problem.
The methods presented are supported by numerical simulation experiments.
In this paper we investigate the use of parallel computing to deal with the high computational cost of numerical algorithms for model reduction of large linear descriptor systems. The state-space truncation methods considered here are composed of iterative schemes which can be efficiently implemented on parallel architectures using existing parallel linear algebra libraries. Our experimental results on a cluster of Intel Pentium processors show the performance of the parallel algorithms.
We discuss a parallel library of efficient algorithms for model reduction of largescale
systems with state-space dimension up to O(104). We survey the numerical
algorithms underlying the implementation of the chosen model reduction methods.
The approach considered here is based on state-space truncation of the system
matrices and includes absolute and relative error methods for both stable and unstable
systems. In contrast to serial implementations of these methods, we employ
Newton-type iterative algorithms for the solution of the major computational tasks.
Experimental results report the numerical accuracy and the parallel performance of
our approach on a cluster of Intel Pentium II processors.
We describe a prototype web service for model reduction of very large-scale linear systems, with
dimension in the order of millions of states, that includes a user-friendly interface designed so that the computation
can be easily performed via the HTTP protocol. Access via a web browser isolates the user of the service from the
complexities of installing and using the parallel model reduction codes and the maintenance of the hardware. In case
the routines are found to be appropriate for the problem the user needs to solve, the library can be then downloaded
and installed on the user’s own computing resources.
This paper illustrates the major issues of the access procedure by means of graphical examples, and describes
the structure and implementation of the remote model reduction service. The service is offered in a cluster of Linux
machines.
A Structure-Preserving Method for Generalized Algebraic RiccatiEquations Based on Pencil Arithmetic
(2004)
This paper describes a numerical method for extracting the stable
right deflating subspace of a matrix pencil Z Y using
a spectral projection method. It has several advantages compared
to other spectral projection methods like the sign function
method. In particular it avoids the rounding error induced
loss of accuracy associated with matrix inversions. The new algorithm
is particularly well adapted to solving continuous-time
algebraic Riccati equations. In numerical examples, it solves
Riccati equations to high accuracy.
We study the optimization of three dimensional curved rods and of shells
under minimal regularity assumptions for the geometry. The results that we
establish concern the existence of optimal shapes and the sensitivity analysis.
We also compute several numerical examples for the curved rods. The models
that we use have been investigated in our previous work [11], [16] and a
complete study of the Kirchhoff-Love arches and their optimization has been
performed in [10].
We prove new properties for the linear isotropic elasticity system and for
thickness minimization problems. We also present very recent results concerning
shape optimization problems for three-dimensional curved rods and
for shells. The questions discussed in this paper are related to the control
variational method and to control into coefficients problems.
In this paper a nonlocal phase-field model for non-isothermal phase transitions
with a non-conserved order parameter is studied. The paper complements
recent investigations by S. Zheng and the second author and treats
the case when the part of the free energy density forcing the order parameter
to attain values within the physically meaningful range [0; 1] is not given
by a logarithmic expression but by the indicator function of [0; 1] . The resulting
field equations form a system of integro-partial differential inclusions
that are highly nonlinearly coupled. For this system, results concerning global
existence, uniqueness and large-time asymptotic behaviour are derived. The
main results are proved by first transforming the system of inclusions into an
equivalent system of equations in which hysteresis operators occur, and then
employing techniques similar to those recently developed by the authors for
phase-field systems involving hysteresis operators.
Motivated by optimal investment problems in mathematical finance, we consider
a variational problem of Neyman-Pearson type for law-invariant robust utility functionals
and convex risk measures. Explicit solutions are found for quantile-based coherent
risk measures and related utility functionals. Typically, these solutions exhibit a critical
phenomenon: If the capital constraint is below some critical value, then the solution will
coincide with a classical solution; above this critical value, the solution is a superposition
of a classical solution and a less risky or even risk-free investment. For general risk measures
and utility functionals, it is shown that there exists a solution that can be written
as a deterministic increasing function of the price density.
We study a stationary Schrödinger-Poisson system on a bounded interval of the real axis. The Schrödinger operator is defined on the bounded domain with transparent boundary conditions. This allows us to model a non-zero current through the boundary of the interval. We prove that the system always admits a solution and give explicit a priori estimates for the solutions.
We suggest a new model for the design of telecommunication networks which integrates
decisions about the topology, configuration of the switching hardware, link dimensioning,
and protected routing of communication demands. Applying the branch-andcut-
algorithm implemented in our network planning and optimization tool discnet, we
demonstrate that real-world based network planning instances of such an enhanced model
can be solved.
In this article, we present a mathematical model and an algorithm to support one of the central
strategic planning decisions of network operators: How to organize a large number of locations into
an hierarchy of network levels? We propose a mixed-integer program and a Lagrangian relaxation
based algorithm to model and solve this planning task. As one big advantage of this approach, not
only solutions but also worst-case quality gurarantees can be provided. We present a solution for
a G-WiN planning instance of DFN with 759 locations which has been computed in less than 30
minutes and which is (provably) less than 0.5 percent away from optimality.
Der scharfeWettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu,
ihre Investitionen genau zu planen und immer wieder Einsparungsmaßnahmen durchzuführen.
Gleichzeitig ist es jedoch wichtig, die Qualität der angebotenen Dienste zu verbessern, um neue
Kunden zu gewinnen und langfristig an sich zu binden.
Die mathematische Optimierung bietet sich für viele solcher Aufgabenstellungen als hervorragend
geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung
speziell zur Kosten- und Qualitätsoptimierung in Kommunikationsnetzen vorzustellen. Anhand
von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie
sich komplexe Zusammenhänge in flexiblen mathematischen Modellen abbilden lassen und welche
Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden können. Die hier vorgestellten
Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen Lösungen
auch eine Qualitätsgarantie liefern, mit der sich die Lösungen fundiert bewerten lassen. Die dokumentierten
Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und Güte der
mathematischen Optimierung für die Praxis.
This paper demonstrates simulation tools for edge-emitting multi quantum well (MQW) lasers.
Properties of the strained MQW active region are simulated by eight-band kp calculations. Then, a 2D
simulation along the transverse cross section of the device is performed based on a drift-diffusion model,
which is self-consistently coupled to heat transport and equations for the optical field. Furthermore, a
method is described, which allows for an efficient quasi 3D simulation of dynamic properties of multisection
edge-emitting lasers.
Let H be a semi–bounded self–adjoint operator in a separable Hilbert space.
For a certain class of positive, continuous, decreasing, and convex functions
F we show the convexity of trace functionals tr(F (H + U − ε(U ))) − ε(U ),
where U is a bounded self–adjoint operator on H and ε(U ) is a normalizing
real function—the Fermi level—which may be identical zero. If additionally
F is continuously differentiable, then the corresponding trace functional is
Fréchet differentiable and there is an expression of its gradient in terms off
the derivative of F . The proof of the differentiability of the trace functional
is based upon Birman and Solomyak’s theory of double Stieltjes operator
integrals. If, in particular, H is a Schrödinger–type operator and U a real-valued function, then the gradient of the trace functional is the quantum
mechanical expression of the particle density with respect to an equilibrium
distribution function f = −F . Thus, the monotonicity of the particle density
in its dependence on the potential U of Schrödinger’s operator—which has
been understood since the late 1980s—follows as a special case.
We propose a class of Markovian agent based models for the time evolution of a share price in an interactive market. The models rely on a microscopic description of a market of buyers and sellers who change their opinion about the stock value in a stochastic way. The actual price is determined in realistic way by matching (clearing) offers until no further transactions can be performed. Some analytic results for a non-interacting model are presented. We also propose basic interaction mechanisms and show in simulations that these already reproduce certain particular features of prices in real stock markets.
For a refined network analysis, we are interested in circuit simulation
including distributed models of semiconductors. We construct a mathematical
model for nonlinear electric networks containing semiconductors
described by the drift-diffusion equations. The focus lies on the coupling
of the network DAEs and the semiconductor PDEs.
Furthermore, we study the behavior of the coupled systems with respect to
time dependent perturbations using an index concept for abstract DAEs.
We present a network topological criterion that guarantees index-1 systems.
We consider the problem of utility maximization for small traders on incomplete
financial markets. As opposed to most of the papers dealing with this
subject, the investors’ trading strategies we allow underly constraints described
by closed, but not necessarily convex, sets. The final wealths obtained by trading
under these constraints are identified as stochastic processes which usually are
supermartingales, and even martingales for particular strategies. These strategies
are seen to be optimal, and the corresponding value functions determined
simply by the initial values of the supermartingales. We separately treat the
cases of exponential, power and logarithmic utility.
We consider financial markets with agents exposed to an external source of
risk which cannot be hedged through investments on the capital market alone.
The sources of risk we think of may be weather and climate. Therefore we face
a typical example of an incomplete financial market. We design a model of a
market on which the external risk becomes tradable. In a first step we complete
the market by introducing an extra security which valuates the external risk
through a process parameter describing its market price. If this parameter is
fixed, risk has a price and every agent can maximize the expected exponential
utility with individual risk aversion obtained from his risk exposure on the one
hand and his investment into the financial market consisting of an exogenous set
of stocks and the insurance asset on the other hand. In the second step, the
market price of risk parameter has to be determined by a partial equilibrium
condition which just expresses the fact that in equilibrium the market is cleared
of the second security. This choice of market price of risk is performed in the
framework of nonlinear backwards stochastic differential equations.
Equilibrium trading of climate and weather risk and numerical simulation in a Markovian framework
(2004)
We consider financial markets with agents exposed to external sources of risk
caused for example by short term climate events such as the South Pacific sea
surface temperature anomalies widely known under the name El Nino. Since
such risks cannot be hedged through investments on the capital market alone,
we face a typical example of an incomplete financial market. In order to make
this risk tradable, we use a financial market model in which an additional insurance
asset provides another possibility of investment besides the usual capital
market. Given one of many possible market prices of risk each agent can maximize
his individual exponential utility from his income obtained from trading in
the capital market, the additional security, and his risk exposure function. Under
the equilibrium market clearing condition for the insurance security the market
price of risk is uniquely determined by a backward stochastic differential equation.
We translate these stochastic equations via the Feynman-Kac formalism
into semi-linear parabolic partial differential equations. Numerical schemes are
available by which these semilinear pde can be simulated. We choose two simple
qualitatively interesting models to describe sea surface temperature, and with
an ENSO risk exposed fisher and farmer and a climate risk neutral bank three
model agents with simple risk exposure functions. By simulating the expected
appreciation price of risk trading, the optimal utility of the agents as a function
of temperature, and their optimal investment into the risk trading security we
obtain first insight into the dynamics of such a market in simple situations.
We consider financial markets with two kinds of small traders: regular traders
who perceive the asset price process S through its natural filtration, and insid-
ers who possess some information advantage which makes the filtrations through
which they perceive the evolution of the market richer. The basic question we dis-
cuss is the link between (NFLVR), the semimartingale property of S viewed from
the agent’s perspective, and bounded expected utility. We show that whenever
an agent’s expected utility is finite, S is a semimartingale with a Doob-Meyer
decomposition featuring a martingale part and an information drift. The ex-
pected utility gain of an insider with respect to a regular trader is calculated in
a completely general setting. In particular, for the logarithmic utility function,
utility gain is a function of the relative information drift alone, regardless of the
completeness of the market.
Invariant measures of dynamical systems generated e. g. by difference equations
can be computed by discretizing the originally continuum state space, and
replacing the action of the generator by the transition mechanism of a Markov
chain. In fact they are approximated by stationary vectors of these Markov
chains. Here we extend this well known approximation result and the underlying
algorithm to the setting of random dynamical systems, i.e. dynamical systems
on the skew product of a probability space carrying the underlying stationary
stochasticity and the state space, a particular non-autonomous framework. The
systems are generated by difference equations driven by stationary random processes
modelled on a metric dynamical system. The approximation algorithm
involves spatial discretizations and the definition of appropriate random Markov
chains with stationary vectors converging to the random invariant measure of
the system.
The work presents a novel method for the detection of mutual
phase synchronization in non-stationary time series. We show how the
application of a cluster algorithmthat considers spatio-temporal struc-
tures of data follows from the general condition of phase-synchronized
data. In view of the topology of phasic data, we re-formulate the
K-Means cluster algorithm on a flat torus and apply a segmentation
index derived in an earlier work (Physica D 177,203-232(2003)). This index is extended by means of averaging in order to reflect phase syn-
chronization in ensembles of multivariate time series. The method is
illustrated using simulated multivariate phase dynamics and arrays of
chaotic systems, in which temporal segments of phase-synchronized
states are registered. A comparison with results from an existing bi-
variate synchronization index reveals major advantages of our method.
A stability analysis is presented for neural field equations in the presence
of axonal delays and for a general class of connectivity kernels and synap-
tic properties. Sufficient conditions are given for the stability of equilibrium
solutions. It is shown that the delays play a crucial role in non-stationary
bifurcations of equilibria, whereas the stationary bifurcations depend only on
the kernel. Bounds are determined for the frequencies of bifurcating periodic
solutions. A perturbative scheme is used to calculate the types of bifurca-
tions leading to spatial patterns, oscillatory solutions, and traveling waves.
For high transmission speeds a simple method is derived that allows the de-
termination of the bifurcation type by visual inspection of the Fourier trans-
forms of the connectivity kernel and its first moment. Results are numerically
illustrated on a class of neurologically plausible second order systems with
combinations of Gaussian excitatory and inhibitory connections.
This work studies dynamical properties of spatially extended neu-
ronal ensembles. We first derive an evolution equation from tem-
poral properties and statistical distributions of synapses and somata.
The obtained integro-differential equation considers both synaptic and
axonal propagation delay, while spatial synaptic connectivities ex-
hibit gamma-distributed distributions. This familiy of connectivity
kernels also covers the cases of divergent, finite, and negligible self-
connections. The work derives conditions for both stationary and
nonstationary instabilities for gamma-distributed kernels.It turns out
that the stability conditions can be formulated in terms of the mean spatial interaction ranges and the mean spatial interaction times. In
addition, a numerical study examines the evoked spatiotemporal re-
sponse activity caused by short local stimuli and reveals maximum
response activity after the mean interaction time at a distance from
stimulus offset location equal to the mean interaction range. These
findings propose new insights to neuronal mechanisms of experimen-
tally observed evoked brain activity.
An optimal control problem for a 2-d elliptic equation is investigated with pointwise control constraints.
This paper is concerned with discretization of the control by piecewise linear functions. The state and the
adjoint state are discretized by linear finite elements. Approximation of order h in the L1-norm is proved in the
main result.
This work studies the stability of spatially extended neuronal ensembles. We first
derive the model equation from statistical properties of the neuron population. The
obtained integro-differential equation considers synaptic and space-dependent transmission
delay for both general and gamma-distributed synaptic connectivities. The
latter connectivity type reveals infinite, finite and vanishing self-connectivities. The
work derives conditions for stationary and nonstationary instabilities for both kernel
types. In addition, a nonlinear analysis for general kernels yields the order parameter
equation of the Turing instability. To compare the results to findings for partial
differential equations (PDEs), two typical PDE-types are derived from the examined
model equation. In case of the gamma-distributed kernels, the stability conditions
are formulated in terms of the mean excitatory and inhibitory interaction ranges. As
a novel finding, we obtain Turing instabilities in fields with local inhibition-lateral
excitation, while wave instabilities occur in fields with local excitation and lateral
inhibition. Numerical simulations support the analytical results.
Single–hop WDM networks with a central Passive
Star Coupler (PSC), as well as single–hop networks with a central
Arrayed–Waveguide Grating (AWG) and a single transceiver at
each node, have been extensively studied as solutions for the
quickly increasing amounts of unicast and multicast traffic in
the metropolitan area. The main bottlenecks of these networks
are the lack of spatial wavelength reuse in the studied PSC based
networks and the single transceiver in the studied AWG based
metro WDM networks. In this paper we develop and evaluate
the FT? ? FR? AWG network, which is based on a central
AWG and has arrays of fixed–tuned transmitters and receivers
at each node. Transceiver arrays are a mature technology, making
the proposed network practical. In addition, the transmitter
arrays allow for high speed signaling over the AWG while
the receiver arrays relieve the receiver bottleneck arising from
multicasting in conjunction with spatial wavelength reuse on the
AWG. Our results from probabilistic analysis and simulation
indicate that the FT? ? FR? AWG network gives particularly
good throughput–delay performance for multicast traffic with
small multicast group sizes or localized destination nodes, as
well as for a mix of unicast and multicast traffic.
We investigate the impact of link and path restoration
on the cost of telecommunication networks. The surprising
result is the following: the cost of an optimal network configuration
is almost independent of the restoration concept if (i)
the installation of network elements (ADMs, DXCs, or routers)
and interface cards, (ii) link capacities, and (iii) working and
restoration routings are simultaneously optimized.
We present a mixed-integer programming model which integrates
all these decisions. Using a branch-and-cut algorithm
(with column generation to deal with all potential routing paths),
we solve structurally different real-world problem instances and
show that the cost of optimal solutions is almost independent of
the used restoration concept.
In addition, we optimize spare capacities for given shortest
working paths which are predetermined with respect to different
link metrics. In comparison to simultaneous optimization of
working and restoration routings, it turns out that this approach
does not allow to obtain predictably good results.
We investigate the impact of hop-limited routing
paths on the total cost of a telecommunication network. For
different survivability settings (no survivability, link and path
restoration), the optimal network cost without restrictions on
the admissible path set is compared to the results obtained with
two strategies to impose hop limits on routing paths.
Based on optimal solutions for 10 real-world based problem
instances, we show that hop limits may lead to an unpredictable
raise in total network cost - even with large hop limits. The total
network cost with a hop limit of 7 hops for all demands can be up
to 25% higher than without restrictions on the admissible path
set. With our second strategy, which imposes demand-dependent
hop limits based on the shortest hop count, we obtain similar
results. This indicates that column generation techniques should
be applied to deal with all admissible paths.
Balancing a matrix by a simple and accurate similarity transformation can improve
the speed and accuracy of numerical methods for computing eigenvalues. We describe
balancing strategies for a large and sparse Hamiltonian matrix H. It is first shown how
to permute H to irreducible form while retaining its structure. This form can be used to
decompose the Hamiltonian eigenproblem into smaller-sized problems. Next, we discuss
the computation of a symplectic scaling matrix D so that the norm of D 1 HD is reduced.
The considered scaling algorithm is solely based on matrix-vector products and thus particularly
suitable if the elements of H are not explicitly given. The merits of balancing
for eigenvalue computations are illustrated by several practically relevant examples.
The periodic QR algorithm is a strongly backward stable method for computing the
eigenvalues of products of matrices, or equivalently for computing the eigenvalues of
block cyclic matrices. The main purpose of this paper is to show that this algorithm
is numerically equivalent to the standard QR algorithm. It will be demonstrated
how this connection may be used to develop a better understanding of the periodic
QR algorithm.
Two algorithms for the solution of discrete-time periodic Lyapunov
equations are presented. The first one is a variant of the
squared Smith iteration, which is solely based on matrix multiplications
and thus attractive to parallel computing environments.
The second algorithm is based on Krylov subspaces and
employs a recently developed variant of the block Arnoldi algorithm.
It is particularly suited for periodic Lyapunov equations
with large and sparse coefficient matrices. We also demonstrate
how these methods can be applied to balanced truncation model
reduction of periodic discrete-time systems and the solution of
periodic Riccati equations.
For linear differential-algebraic equations (DAEs) with properly
stated leading terms the property of being numerically qualified
guarantees that qualitative properties of DAE solutions are reflected
by the numerical approximations. In this case BDF and Runge-Kutta
methods integrate the inherent regular ODE.
Here, we extend these results to general linear methods. We show
how general linear methods having stiff accuracy can be applied to
linear DAEs of index 1 and 2. In addition to the order conditions for
ODEs, general linear methods for DAEs have to satisfy additional
conditions.
As general linear methods require a starting procedure to start the
integration we put special emphasis on finding suitable starting
methods for index-2 DAEs.
Cyclic timetabling for public transportation companies is usually modeled by the periodic
event scheduling problem. To deduce a mixed-integer programming formulation, artificial integer
variables have to be introduced. There are many ways to define these integer variables.
We show that the minimal number of integer variables required to encode an instance is
achieved by introducing an integer variable for each element of some integral cycle basis. An
integral cycle basis consists of |A|-|V|+1 oriented cycles of a directed graph D = (V;A) that
enable any oriented cycle of the directed graph to be expressed as an integer linear combination.
The solution times for the originating application vary extremely with different integral
cycle bases. However, our computational studies show that the width of integral cycle bases
is a good empirical measure for the solution time of the MIP. Clearly, integral cycle bases
permit a much wider choice than the former standard approach, in which integer variables are
associated with the co-tree arcs of some spanning tree. Hence, to formulate better solvable
integer programs, we present algorithms that construct integral cycle bases of small width.
To that end, we investigate classes of directed cycle bases that are closely related to integral
cycle bases, namely (generalized) fundamental and undirected cycle bases. This gives rise to
both, a compact classification of directed cycle bases and notable reductions of running times
for cyclic timetabling.
Periodic timetabling for railway networks is usually modeled by the Periodic Event Scheduling
Problem (PESP). This model permits to express many requirements that practitioners impose
on periodic railway timetables. We discuss a requirement practitioners are asking for, but which,
so far, has not been the topic of mathematical studies: the concept of symmetry.
Several motivations why symmetric timetables might seem promising will be given. However,
we provide examples showing that symmetry leads to suboptimality.
To integrate symmetry into the graph model of the PESP, there are many obstacles to overcome.
Nevertheless, adding symmetry requirements to mixed-integer programming formulations
explicitly, enables MIP solvers such as CPLEX
to terminate earlier with good solutions.
This paper is concerned with transparent boundary conditions
(TBCs) for the time-dependent Schrödinger equation in one and two
dimensions. Discrete TBCs are introduced in the numerical simulations
of whole space problems in order to reduce the computational
domain to a finite region. Since the discrete TBC for the Schrödinger
equation includes a convolution w.r.t. time with a weakly decaying
kernel, its numerical evaluation becomes very costly for large-time
simulations.
As a remedy we construct approximate TBCs with a kernel having
the form of a finite sum-of-exponentials, which can be evaluated
in a very efficient recursion. We prove stability of the resulting initialboundary
value scheme, give error estimates for the considered approximation
of the boundary condition, and illustrate the efficiency of
the proposed method on several examples.
In this paper we introduce the notion of smoothed competitive analysis of online
algorithms. Smoothed analysis has been proposed by Spielman and Teng [22] to explain
the behaviour of algorithms that work well in practice while performing very poorly
from a worst case analysis point of view. We apply this notion to analyze the Multi-
Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of
jobs released over time when the processing time of a job is only known at time of
completion.
The initial processing times are integers in the range [1, 2K ]. We use a partial bit
randomization model, where the initial processing times are smoothened by changing
the k least significant bits under a quite general class of probability distributions. We
show that MLF admits a smoothed competitive ratio of O(max((2k /σ)3 , (2k /σ)2 2K−k )),
where σ denotes the standard deviation of the distribution. In particular, we obtain a
competitive ratio of O(2K−k ) if σ = Θ(2k ). We also prove an Ω(2K−k ) lower bound for
any deterministic algorithm that is run on processing times smoothened according to
the partial bit randomization model. For various other smoothening models, including
the additive symmetric smoothening model used by Spielman and Teng [22], we give a
higher lower bound of Ω(2K ).
A direct consequence of our result is also the first average case analysis of MLF. We
show a constant expected ratio of the total flow time of MLF to the optimum under
several distributions including the uniform distribution.
The paper presents a new affine invariant theory on asymptotic mesh
independence of Newton’s method for discretized nonlinear operator equations.
Compared to earlier attempts, the new approach is both much simpler
and more intuitive from the algorithmic point of view. The theory
is exemplified at collocation methods for ODE boundary value problems
and at finite element methods for elliptic PDE problems.
In this article, we use numerical simulation to investigate transient temperature
phenomena during sublimation growth of SiC single crytals via physical
vapor transport (also called the modified Lely method). We consider the evolution
of temperatures at the SiC source and at the SiC seed crystal, which
are highly relevant to the quality of the grown crystals, but inaccessible to
direct measurements. The simulations are based on a transient mathematical
model for the heat transport, including heat conduction, radiation, and radio
frequency (RF) induction heating. Varying the position of the induction coil
as well as the heating power, it is shown that the measurable temperature difference
between the bottom and the top of the growth apparatus can usually
not be used as a simple indicator for the respective temperature difference
between SiC source and seed. Moreover, it is shown that there can be a time
lack of 1.5 hours between the heating of the temperature measuring points
and the heating of the interior of the SiC source.
We discuss the problem to count, or, more modestly, to estimate
the number f(m; n) of unimodular triangulations of the planar grid of
size m * n.
Among other tools, we employ recursions that allow one to compute
the (huge) number of triangulations for small m and rather large n by
dynamic programming; we show that this computation can be done in
polynomial time if m is fixed, and present computational results from
our implementation of this approach.
We also present new upper and lower bounds for large m and n,
and we report about results obtained from a computer simulation of
the random walk that is generated by
ips.
We investigate the worst-case behavior of the simplex algorithm on linear programs
with 3 variables, that is, on 3-dimensional simple polytopes. Among the
pivot rules that we consider, the “random edge” rule yields the best asymptotic
behavior as well as the most complicated analysis. All other rules turn out to be
much easier to study, but also produce worse results: Most of them show essentially
worst-possible behavior; this includes both Kalai’s “random-facet” rule, which is
known to be subexponential without dimension restriction, as well as Zadeh’s deterministic
history-dependent rule, for which no non-polynomial instances in general
dimensions have been found so far.
Abstract. Let Xd,n be an n-element subset of {0, 1}d chosen uniformly
at random, and denote by Pd,n := conv Xd,n its convex hull. Let ∆d,n
be the density of the graph of Pd,n (i.e., the number of one-dimensional
faces of Pd,n divided by n ). Our main result is that, for any function 2
n(d), the expected value of ∆d,n(d) converges (with d → ∞) to one if, √
for some arbitrary ε < 0, n(d) ≤ ( 2 − ε)d holds for all large d, while it √
converges to zero if n(d) ≥ ( 2 + ε)d holds for all large d.
Abstract. Let P be a random 0/1-polytope in Rd with n(d) vertices, and denote by νr (P ) the
quotient of the number of faces of P with exactly r vertices and n(d) (the r-density of P ). For each
r
r ≥ 3, we establish the existence of a sharp threshold for the r-density and determine the values of
the threshold numbers τr such that, for all ε > 0,
E [νr (P )] =
1 − o(1)
o(1)
if n(d) ≤ 2(τr −ε)d for all d
if n(d) ≥ 2(τr +ε)d for all d
holds for the expected value of νr (P ). The threshold for r = 2 has already been determined in [8].
In particular, these results indicate that the high densities often encountered in polyhedral com-
binatorics (e.g., the cut-polytope has both 2- and 3-density equal to one) is due to the geometry of
0/1-polytopes rather than to the special combinatorics of the underlying problems.
We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.
How to Whack Moles
(2004)
In the classical whack-a-mole game moles that pop up at
certain locations must be whacked by means of a hammer before they
go under ground again. The goal is to maximize the number of moles
caught. This problem can be formulated as an online optimization problem:
Requests (moles) appear over time at points in a metric space and
must be served (whacked) by a server (hammer) before their deadlines
(i.e., before they disappear). An online algorithm learns each request
only at its release time and must base its decisions on incomplete information.
We study the online whack-a-mole problem (wham) on the real
line and on the uniform metric space. While on the line no deterministic
algorithm can achieve a constant competitive ratio, we provide competitive
algorithms for the uniform metric space. Our online investigations
are complemented by complexity results for the offline problem.
In this paper we analyze decompositions of reversible nearly uncoupled
Markov chains into rapidly mixing subchains. We state upper
bounds on the 2nd eigenvalue for restriction and stochastic complementation
chains of reversible Markov chains, as well as a relation between
them. We illustrate the obtained bounds analytically for bunkbed
graphs, and furthermore apply them to restricted Markov chains that
arise when analyzing conformation dynamics of a small biomolecule.
Fractional multistep methods were introduced by C. Lubich for the quadrature of Abel integral operators and the solution of weakly singular Volterra integral equations of the first kind with exactly given right-hand sides. In the current paper, we consider the regularizing properties of these methods to solve the mentioned integral equations of the first kind for perturbed right-hand sides. Finally, numerical results are presented.
We present an algorithm that constructs parametrizations of boundary
and interface surfaces automatically. Starting with high-resolution triangulated
surfaces describing the computational domains, we iteratively
simplify the surfaces yielding a coarse approximation of the boundaries
with the same topological type. While simplifying we construct a function
that is defined on the coarse surface and whose image is the original
surface. This function allows access to the correct shape and surface normals
of the original surface as well as to any kind of data defined on it.
Such information can be used by geometric multigrid solvers doing adaptive
mesh refinement. Our algorithm runs stable on all types of input
surfaces, including those that describe domains consisting of several materials.
We have used our method with success in different fields and we
discuss examples from structural mechanics and biomechanics.
We use a numerical optimization method to determine the control parameters
frequency, power, and coil position for the radio frequency (RF) induction
heating of the growth apparatus during sublimation growth of SiC single crystals
via physical vapor transport (PVT) (also called the modified Lely method). The
control parameters are determined to minimize a functional, tuning the radial
temperature gradient on the single crystal surface as well as the vertical temperature
gradient between SiC source and seed, both being crucial for high-quality
growth. The optimization is subject to constraints with respect to a required
temperature difference between source and seed, a required temperature range at
the seed, and an upper bound for the temperature in the entire apparatus. The
numerical computations use a stationary mathematical model for the heat transport,
including heat conduction, radiation, and RF heating to solve the forward
problem, and a Nelder-Mead method for optimization. A minimal radial temperature
gradient is found to coincide with a minimal temperature at the single
crystal surface, and a maximal temperature gradient between source and seed is
found to coincide with a low coil position.
The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results.
Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\% on average for concrete example networks are achievable.
Relaying - allowing multiple wireless hops - is a protocol extension
for cellular networks conceived to improve data throughput. Its benefits have only
been quantfied for small example networks. For assessing its general potential,
we define a complex resource allocation/scheduling problem. Several mathematical
models are presented for this problem; while a time-expanded MIP approach turns
out intractable, a sophisticated column generation scheme leads to good computational
results. We thereby show that for selected cases relaying can increase data
throughput by 30% on the average.