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.