Refine
Year of publication
Language
- English (1103)
- German (10)
- Multiple languages (1)
Keywords
- optimal control (27)
- stability (14)
- integer programming (11)
- Stochastic programming (9)
- finite elements (9)
- mixed integer programming (9)
- Hamiltonian matrix (8)
- finite element method (8)
- model reduction (8)
- state constraints (8)
Solving Time-Dependent Optimal Control Problems in Comsol Multiphyiscs ba Space-Time Discretizations
(2009)
We use COMSOL Multiphysics to solve time-dependent optimal control problems for par-
tial differential equations whose optimality conditions can be formulated as a PDE. For a
class of linear-quadratic model problems we summarize known analytic results on existence
of solutions and first order optimality conditions that exhibit the typical feature of time-dependent control problems, namely the fact that a part of the optimality system has to be
integrated backward in time. We present a strategy that is based on the treatment of the
coupled optimality system in the space-time cylinder. A brief motivation of this approach is
given by showing that the optimality system is elliptic in some sence. Numerical examples
show advantages and limits of the usage of COMSOL Multiphysics and of our approach.
The stochastic dynamics of a well-stirred mixture of molecular species
interacting through different biochemical reactions can be
accurately modelled by the chemical master equation (CME). Research in
the biology and scientific computing community has
concentrated mostly on the development of numerical techniques to
approximate the solution of the CME via many realizations of the associated
Markov jump process. The domain of exact and/or efficient methods for
directly solving the CME is still widely open, which is due to its
large dimension that grows exponentially with the number of molecular
species involved. In this article, we present an exact solution
formula of the CME for arbitrary initial conditions in the case where
the underlying system is governed by monomolecular reactions. The
solution can be expressed in terms of the convolution of multinomial
and product Poisson distributions with time-dependent parameters
evolving according to the traditional reaction-rate equations. This
very structured representation allows to deduce any property of the
solution. The model class includes many interesting examples and may
also be used as the starting point for the design of new numerical
methods for the CME of more complex reaction systems.
Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field.
In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.
This paper presents concepts and implementation of the finite element toolbox Kaskade 7, a flexible C++ code for solving elliptic and parabolic PDE systems. Issues such as problem formulation, assembly and adaptivity are discussed at the example of optimal control problems. Trajectory compression for parabolic optimization problems is considered as a case study.
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.
In this paper we study BSDEs arising from a special class of backward stochastic partial differential equations (BSPDEs) that is intimately related to utility maximization problems with respect to arbitrary utility functions. After providing existence and uniqueness we discuss the numerical realizability. Then we study utility maximization problems on incomplete financial markets whose dynamics are governed by continuous semimartingales. Adapting standard methods that solve the utility maximization problem using BSDEs, we give solutions for the portfolio optimization problem which involve the delivery of a liability at maturity. We illustrate our study by numerical simulations for selected examples. As a byproduct we prove existence of a solution to a very particular quadratic growth BSDE with unbounded terminal condition. This complements results on this topic obtained in [6,7,8].
In the case of the equidistant discretization of the Airy differential equation (\discrete
Airy equation") the exact solution can be found explicitly. This fact is used
to derive a discrete transparent boundary condition (TBC) for a Schroedinger
equation with linear varying potential, which can be used in \parabolic equation"
simulations in (underwater) acoustics and for radar propagation in the troposphere.
We propose different strategies for the discrete TBC and show an efficient implementation.
Finally a stability proof for the resulting scheme is given. A numerical
example in the application to underwater acoustics shows the superiority of the new
discrete TBC.
Propagation of short optical pulses in a nonlinear dispersive medium is considered without the use of slow envelope and
unidirectional propagation approximations. The existence of uniformly moving solitary solutions is predicted in the anomalous
dispersion domain. A four-parametric family of such solutions is found that contains the classical envelope soliton in the limit of
large pulse durations. In the opposite limit we get another family member, which in contrast to the envelope soliton strongly depends on nonlinearity model and represents the shortest and the most intense pulse which can propagate in a stationary manner.
Particle methods have become indispensible in conformation dynamics to compute transition rates in protein folding, binding processes and molecular design, to mention a few. Conformation dynamics requires at a decomposition of a molecule's position space into metastable conformations. In this paper, we show how this decomposition can be obtained via the design of either ``soft'' or ``hard'' molecular conformations. We show, that the soft approach results in a larger metastabilitiy of the decomposition and is thus more advantegous. This is illustrated by a simulation of Alanine Dipeptide.
Sobolev stability of plane wave solutions to the cubic nonlinear Schrödinger equation on a torus
(2013)
It is shown that plane wave solutions to the cubic nonlinear Schrödinger equation on a torus behave orbitally stable under generic perturbations of the initial data that are small in a high-order Sobolev norm, over long times that extend to arbitrary negative powers of the smallness parameter. The perturbation stays small in the same Sobolev norm over such long times. The proof uses a Hamiltonian reduction and transformation and, alternatively, Birkhoff normal forms or modulated Fourier expansions in time.
We give an exposition of recent results on regularity and Fredholm properties for first-order one-dimensional hyperbolic PDEs. We show that large classes of boundary operators cause an effect that smoothness increases with time. This property is the key in finding regularizers
(parametrices) for hyperbolic problems. We construct regularizers for periodic problems for dissipative first-order linear hyperbolic PDEs and show that these problems are modeled by Fredholm operators of index zero.
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.
Many applications give rise to matrix polynomials whose coefficients have
a kind of reversal symmetry, a structure we call palindromic.
Several properties of scalar palindromic polynomials are derived,
and together with properties of compound matrices, used to
establish the Smith form of regular and singular T-palindromic matrix polynomials,
over arbitrary fields.
The invariant polynomials are shown to
inherit palindromicity,
and their structure is described in detail.
Jordan structures of palindromic matrix polynomials are characterized,
and necessary conditions for the
existence of structured linearizations established.
In the odd degree case, a constructive procedure for building
palindromic linearizations shows that the necessary conditions are sufficient as well.
The Smith form for *-palindromic polynomials is also analyzed. Finally, results for palindromic matrix polynomials over fields of
characteristic two are presented.
Using Freidlin-Wentzell sample path large deviations theory, we characterise the small-time behaviour of probabilities of a process following an uncorrelated local-stochastic volatility model.
As a corollary, we determine the small-maturity behaviour of the implied volatility under this class of processes.
We characterize the Smith form of skew-symmetric matrix polynomials
over an arbitrary field $\F$,
showing that all elementary divisors occur with even multiplicity.
Restricting the class of equivalence transformations to unimodular congruences,
a Smith-like skew-symmetric canonical form
for skew-symmetric matrix polynomials is also obtained.
These results are used to analyze the eigenvalue and elementary divisor structure
of matrices expressible as products of two skew-symmetric matrices,
as well as the existence of structured linearizations
for skew-symmetric matrix polynomials.
By contrast with other classes of structured matrix polynomials
(e.g., alternating or palindromic polynomials),
every regular skew-symmetric matrix polynomial
is shown to have a structured strong linearization.
While there are singular skew-symmetric polynomials of even degree
for which a structured linearization is impossible,
for each odd degree we develop a skew-symmetric companion form
that uniformly provides a structured linearization
for every regular and singular skew-symmetric polynomial
of that degree.
Finally, the results are applied to the construction of minimal
symmetric factorizations of skew-symmetric rational matrices.
The classical singular value decomposition for a matrix $A\in\Cmn$ is a
canonical form for $A$ that also displays the eigenvalues
of the Hermitian matrices $AA^\ast$ and $A^\ast A$. In this paper, we develop
a corresponding decomposition for $A$ that provides the Jordan canonical forms
for the complex symmetric matrices $AA^T$ and $A^TA$. More generally, we consider
the matrix triple $(A,G_1,G_2)$, where $G_1\in\CC{m}, G_2\in\CC{n}$
are invertible and either complex symmetric and complex skew-symmetric, and we
provide a canonical form under transformations of the form
$(A,G_1,G_2)\mapsto(X^T A Y, X^T G_1X, Y^T G_2Y)$, where $X,Y$ are nonsingular.
Mehta, Roughgarden, and Sundararajan recently introduced a new class of cost sharing mechanisms called acyclic mechanisms. These mechanisms achieve a slightly weaker notion of truthfulness than the well-known Moulin mechanisms, but provide additional freedom to improve budget balance and social cost approximation guarantees. In this paper, we investigate the potential of acyclic mechanisms for combinatorial optimization problems. In particular, we study a subclass of acyclic mechanisms which we term singleton acyclic mechanisms. We show that every rho-approximate algorithm that is partially increasing can be turned into a singleton acyclic mechanism that is weakly group-strategyproof and rho-budget balanced. Based on this result, we develop singleton acyclic mechanisms for parallel machine scheduling problems with completion time objectives, which perform extremely well both with respect to budget balance and social cost.
We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost
installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context,
helping to increase the dual bound and to reduce the optimality gaps.
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.
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.
Im Zentrum der Arbeiten soll die Chaos- und Kohärenzkontrolle von Halbleiterlasern mit gegenseitiger optischer Kopplung stehen. Diese Fragestellung ist von erheblicher praktischer Relevanz, da Rauschen und chaotisches Verhalten generelle Probleme in der optischen Hochgeschwindigkeitskommunikation sind. Die Kontrolle von optischen Systemen mit komplexer Selbstorganisation stellt aber auch aus grundsätzlicher Sicht Neuland dar. Hierfür geeignete Konzepte sind bisher weder überzeugend theoretisch beschrieben noch experimentell umgesetzt.
We study the exact recovery of signals from quantized frame coefficients. Here, the basis of the quantization
is hard thresholding, and we present a simple algorithm for the recovery of reconstructable signals. The set of
non-reconstructable signals is shown to be star-shaped and symmetric with respect to the origin. Moreover, we
provide a criterion on the frame for the boundedness of this set. In this case, we also give a priori bounds.
A basic task in signal analysis is to character-
ize data in a meaningful way for analysis and classification
purposes. Time-frequency transforms are powerful strategies
for signal decomposition, and important recent generalizations
have been achieved in the setting of frame theory. In parallel
recent developments, tools from algebraic topology, traditionally
developed in purely abstract settings, have provided new insights
in applications to data analysis. In this report, we investigate some
interactions of these tools, both theoretically and with numerical
experiments, in order to characterize signals and their frame
transforms. We explain basic concepts in persistent homology
as an important new subfield of computational topology, as well
as formulations of time-frequency analysis in frame theory. Our
objective is to use persistent homology for constructing topo-
logical signatures of signals in the context of frame theory. The
motivation is to design new classification and analysis methods by
combining the strength of frame theory as a fundamental signal
processing methodology, with persistent homology as a new tool
in data analysis.
A basic task in signal analysis is to character-
ize data in a meaningful way for analysis and classification
purposes. Time-frequency transforms are powerful strategies
for signal decomposition, and important recent generalizations
have been achieved in the setting of frame theory. In parallel
recent developments, tools from algebraic topology, traditionally
developed in purely abstract settings, have provided new insights
in applications to data analysis. In this report, we investigate some
interactions of these tools, both theoretically and with numerical
experiments, in order to characterize signals and their frame
transforms. We explain basic concepts in persistent homology
as an important new subfield of computational topology, as well
as formulations of time-frequency analysis in frame theory. Our
objective is to use persistent homology for constructing topo-
logical signatures of signals in the context of frame theory. The
motivation is to design new classification and analysis methods by
combining the strength of frame theory as a fundamental signal
processing methodology, with persistent homology as a new tool
in data analysis.
We consider scheduling on a single machine with one non-availability period to minimize the weighted sum of completion times. We provide a preemptive algorithm with an approximation ratio arbitrarily close to the Golden Ratio,~$(1+\sqrt{5})/2+\eps$, which improves on a previously best known~$2$-approximation. The non-preemptive version of the same algorithm yields a~$(2+\eps)$-approximation.
We study the global spatial regularity of solutions of elasto-plastic models with linear hardening. In order to point out the main idea, we consider a model problem on a cube, where we describe Dirichlet and
Neumann boundary conditions on the top and the bottom, respectively, and periodic boundary conditions on the
remaining faces. Under natural smoothness assumptions on the data we obtain
$u\in L^\infty((0,T);H^{3/2-\delta}(\Omega))$ for the displacements and
$z\in L^\infty((0,T);H^{1/2-\delta}(\Omega))$ for the internal variables.
The proof is based on a difference quotient technique and a reflection argument.
We study a mechanical equilibrium problem for a material consisting of two components with different densities, which allows to change the outer shape by changing the interface between the subdomains. We formulate the shape design problem of compensating unwanted workpiece
changes by controlling the interface, employ regularity results for transmission problems for a rigorous derivation of optimality conditions based on the speed method, and conclude with some numerical results based on a spline approximation of the interface.
The derivation of multiplier-based optimality conditions for elliptic mathematical programs with equilibrium constraints (MPEC) is essential for the characterization of solutions and de- velopment of numerical methods. Though much can be said for broad classes of elliptic MPECs in both polyhedric and non-polyhedric settings, the calculation becomes significantly more com- plicated when additional constraints are imposed on the control. In this paper we develop three derivation methods for constrained MPEC problems: via concepts from variational analysis, via penalization of the control constraints, and via penalization of the lower-level problem with the subsequent regularization of the resulting nonsmoothness. The developed methods and obtained results are then compared and contrasted.
A class of optimal control problems for a semilinear parabolic partial differential equation
with control and mixed control-state constraints is considered.
For this problem, a projection formula is derived
that is equivalent to the necessary optimality
conditions. As main result, the superlinear convergence of a semi-smooth Newton method is shown.
Moreover we show the numerical treatment and several numerical experiments.
Cubature methods, a powerful alternative to Monte Carlo due to Kusuoka [Adv. Math. Econ. 6, 69–83, 2004] and Lyons–Victoir [Proc. R. Soc. Lond. Ser. A 460, 169–198, 2004], involve the solution to numerous auxiliary ordinary differential equations. With focus on the Ninomiya-Victoir algorithm [Appl. Math. Fin. 15, 107–121, 2008], which corresponds to a concrete level 5 cubature method, we study some parametric diffusion models motivated from financial applications, and exhibit structural conditions under which all involved ODEs can be solved explicitly and efficiently. We then enlarge the class of models for which this technique applies, by introducing a (model-dependent) variation of the Ninomiya-Victoir method. Our method remains easy to implement; numerical examples illustrate the savings in computation time.
The LSW model with encounters has been suggested by Lifshitz and
Slyozov as a regularization of their classical mean-field model for
domain coarsening to obtain universal self-similar long-time
behavior. We rigorously establish that an exponentially decaying
self-similar solution to this model exist, and show that this
solutions is isolated in a certain function space. Our proof relies
on setting up a suitable fixed-point problem in an appropriate
function space and careful asymptotic estimates of the solution to a
corresponding homogeneous problem.
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?.
We derive formulae for the second-order subdifferential of polyhedral norms. These formulae are fully explicit in terms of initial data. In a first step we rely on the explicit formula for the coderivative of normal cone mapping to polyhedra. Though being explicit, this formula is quite involved and difficult to apply. Therefore, we derive simple formulae for the 1-norm and - making use of a recently obtained formula for the second-order subdifferential of the maximum function - for the maximum norm.
This paper concerns second-order analysis for a remarkable class of variational systems in finite-dimensional and infinite-dimensional spaces, which is particularly important for the study of optimization and equilibrium problems with equilibrium constraints. Systems of this type are described via variational inequalities over polyhedral convex sets and allow us to provide a comprehensive local analysis by using appropriate generalized differentiation of the normal cone mappings for such sets. In this paper we efficiently compute the required coderivatives of the normal cone mappings exclusively via the initial data of polyhedral sets in reflexive Banach spaces. This provides the main tools of second-order variational analysis allowing us, in particular, to derive necessary and sufficient conditions for robust Lipschitzian stability of solution maps to parameterized variational inequalities with evaluating the exact bound of the corresponding Lipschitzian moduli. The efficient coderivative calculations and characterizations of robust stability obtained in this paper are the first results in the literature for the problems under consideration in infinite-dimensional spaces. Most of them are also new in finite dimensions.
We consider risk-averse formulations of multistage stochastic linear programs. For these formulations, based on convex combinations of spectral risk measures, risk-averse dynamic programming equations can be written. As a result, the Stochastic Dual Dynamic Programming
(SDDP) algorithm can be used to obtain approximations of
the corresponding risk-averse recourse functions. This allows us to define a risk-averse nonanticipative feasible policy for thestochastic linear program. Formulas for the cuts that approximate the recourse functions are given.
この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる.
We study two related problems in non-preemptive scheduling and packing of malleable tasks with precedence constraints to minimize the makespan. We distinguish the scheduling variant, in which we allow the free choice of processors, and the packing variant, in which a task must be assigned to a contiguous subset of processors.
For precedence constraints of bounded width, we completely resolve the complexity status for any particular problem setting concerning width bound and number of processors, and give polynomial-time algorithms with best possible performance. For both, scheduling and packing malleable tasks, we present an FPTAS for the NP-hard problem variants and exact algorithms for all remaining special cases. To obtain the positive results, we do not require the common monotonous penalty assumption on processing times, whereas our hardness results hold even when assuming this restriction.
With the close relation between contiguous scheduling and strip packing, our FPTAS
is the first (and best possible) constant factor approximation for (malleable) strip packing under special precedence constraints.
A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the Lr-distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.
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.
Stochastic optimization techniques are highly relevant for applications in electricity production and trading since, in particular after the deregulations of many electricity markets, there is a high number of uncertainty factors (e.g., demand, spot prices) to be considered that can be described reasonably by statistical models. Here, we want to highlight two aspects of this approach: scenario tree approximation and risk aversion. The former is a procedure to replace a general statistical model (probability distribution), which makes the optimization problem intractable, suitably by a finite discrete distribution (scenarios). This is typically an indispensable first step towards a solution of a stochastic optimization model. On the other hand, this is a highly sensitive concern, in particular if dynamic decision structures are involved (multistage stochastic programming). Then, the approximate distribution must exhibit tree structure. Moreover, it is of interest to get by with a moderate number of scenarios to have the resulting problem tractable. In any case, it has to be relied on suitably stability results to ensure that the obtained results are indeed related to the original (infinite dimensional) problem. These stability results involve probability distances and, for the multistage case, a filtration distance that evaluates the information increase over time. We present respective approximation schemes relying on Monte Carlo sampling and scenario reduction and combining techniques. The second topic of this talk is risk aversion. Namely, we present the approach of polyhedral risk measures which are given as (the optimal values of) certain simple stochastic programs. Well-known risk measures such as CVaR and expected polyhedral utility belong to this class and, moreover, multiperiod risk measures for multistage stochastic programs are suggested. For stochastic programs incorporating polyhedral risk measures it has been shown that numerical tractability as well as stability results known for classical (non-risk-averse) stochastic programs remain valid. In particular, the same scenario approximation methods can be used. Finally, we present illustrative numerical results from an electricity portfolio optimization model for a municipal power utility.
Stochastic programming problems appear as mathematical models for optimization problems under stochastic uncertainty. Most computational approaches for solving such models are based on approximating the underlying probability distribution by a probability measure with finite support. Since the computational complexity for solving stochastic programs gets worse when increasing the number of atoms (or scenarios), it is sometimes necessary to reduce their number. Techniques for scenario reduction often require fast heuristics for solving combinatorial subproblems. Available techniques are reviewed and open problems are discussed.
Discrete approximations to chance constrained and mixed-integer two-stage stochastic programs require moderately sized scenario
sets. The relevant distances of (multivariate) probability
distributions for deriving quantitative stability results for such stochastic programs are $\mathcal{B}$-discrepancies, where the class $\mathcal{B}$ of Borel sets depends on their structural properties.
Hence, the optimal scenario reduction problem for such models is stated with respect to $\mathcal{B}$-discrepancies. In this paper,
upper and lower bounds, and some explicit solutions for optimal scenario reduction problems are derived. In addition, we develop
heuristic algorithms for determining nearly optimally reduced probability measures, discuss the case of the cell discrepancy (or
Kolmogorov metric) in some detail and provide some numerical experience.
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
Stability-based methods for scenario generation in stochastic programming are reviewed. In particular, we briefly discuss Monte Carlo sampling, Quasi-Monte Carlo methods, quadrature rules based on sparse grids and optimal quantization. In addition, we provide some convergence results based on recent developments in multivariate integration. The method of optimal scenario reduction and techniques for scenario trees generation are also reviewed.
The paper is devoted to Schroedinger operators on bounded intervals of the real axis with dissipative boundary conditions. In the framework of the Lax-Phillips scattering theory the asymptotic behaviour of the phase shift is investigated in detail and its relation to the spectral shift is discussed, in particular, trace formula and Birman-Krein formula are verified directly. The results are used for dissipative Schroedinger-Poisson systems.
Scalable Frames
(2012)
Tight frames can be characterized as those frames which possess optimal numerical stability properties. In this paper, we consider the question of modifying a general frame to generate a tight frame by rescaling its frame vectors; a process which can also be regarded as perfect preconditioning of a frame by a diagonal operator. A frame is called scalable, if such a diagonal operator exists. We derive various characterizations of scalable frames, thereby including the infinite-dimensional situation. Finally, we provide a geometric interpretation of scalability in terms of conical surfaces.
We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL,
DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on realistic network topologies and node architectures as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial
benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A
sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks.