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)
The identification of metastable conformations of molecules plays an
important role in computational drug design. One main difficulty is the
fact that the underlying dynamic processes take place in high dimensional
spaces. Although the restriction of degrees of freedom to a few dihedral
angles significantly reduces the complexity of the problem, the existing
algorithms are time-consuming. They are mainly based on the approximation
of a transfer operator by an extensive sampling of states according
to the Boltzmann distribution and short-time Hamiltonian dynamics simulations.
We present a method which can identify metastable conformations
without sampling the complete distribution. Our algorithm is based
on local transition rates and uses only pointwise information about the
potential energy surface. In order to apply the cluster algorithm PCCA+,
we compute a few eigenvectors of the rate matrix by the Jacobi-Davidson
method. Interpolation techniques are applied to approximate the thermodynamical
weights of the clusters. The concluding example illustrates
our approach for epigallocatechine, a molecule which can be described by
seven dihedral angles.
We give an introduction into the fascinating area of flows over time - also called "dynamic flows" in the literature. Starting from the early work of Ford and Fulkerson on maximum flows over time, we cover many exciting results that have been obtained over the last fifty years. One purpose of this paper is to serve as a possible basis for teaching network flows over time in an advanced course on combinatorial optimization.
This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently.
We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.
Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver.
Hybrid Branching
(2009)
State-of-the-art solvers for Constraint Satisfaction Problems (CSP), Mixed Integer Programs (MIP), and
satisfiability problems (SAT) are usually based on a branch-and-bound algorithm.
The question how to split a problem into subproblems (\emph{branching}) is in the core of any branch-and-bound algorithm.
Branching on individual variables is very common in CSP, MIP, and SAT. The rules, however, which variable to choose for
branching, differ significantly. In this paper, we present hybrid branching, which combines selection rules from all three fields.
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use.
We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.
In the first part of this article, we have shown how time-dependent optimal control for partial
differential equations can be realized in a modern high-level modeling and simulation package. In this second part we extend our approach to (state) constrained problems. "Pure" state constraints in a function space
setting lead to non-regular Lagrange multipliers (if they exist), i.e. the Lagrange multipliers are in general Borel
measures. This will be overcome by different regularization techniques.
To implement inequality constraints, active set methods and interior point methods (or barrier methods) are widely in use. We show how these techniques can be realized in the modeling and simulation package Comsol
Multiphysics.
In contrast to the first part, only the one-shot-approach based on space-time elements is considered. We implemented a projection method based on active sets as well as a barrier method and compare these methods
by a specialized PDE optimization program, and a program that optimizes the discrete version of the given problem.
In this paper we present a strategy to solve parabolic optimal control problems
using available specialized elliptic PDE solvers. We aim at an indirect solution
approach, i.e. developing optimality conditions in function spaces that are then
discretized and solved. Classes of problems where optimality conditions can be derived
as coupled systems of parabolic partial differential equations are considered.
We consider a simultaneous space-time discretization. We verify that for our model
problems the parabolic forward-backward system of PDEs can equivalently be expressed
by a single elliptic boundary value problem in the space-time domain. This
fact has been used as a motivation for space-time-multigrid solution approaches,
which may also be an option in our context.
The theoretical base developed for the example problems then allows to apply
specialized elliptic PDE solvers to the optimality system without much implementational
effort. Numerical experiments for some example problems are conducted and
underline the applicability of this approach.
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.
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.
In this paper we give an overview of the heuristics which are integrated into the open source branch-cut-and-price-framework SCIP.
We briefly describe the fundamental ideas of different categories of heuristics and present some computational results which demonstrate the impact of heuristics on the overall solving process of SCIP.
In the recent years, a couple of quite successful large neighborhood search heuristics for mixed integer programs has been published.
Up to our knowledge, all of them are improvement heuristics.
We present a new start heuristic for general MIPs working in the spirit of large neighborhood search.
It constructs a sub-MIP which represents the space of all feasible roundings of some fractional point - normally the optimum of the LP-relaxation of the original MIP.
Thereby, one is able to determine whether a point can be rounded to a feasible solution and which is the best possible rounding.
Furthermore, a slightly modified version of RENS proves to be a well-performing heuristic inside the branch-cut-and-price-framework SCIP.
The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor.
This paper proposes a slight modification of the algorithm in order to find better solutions.
Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies.
CIP is a generalization of MIP that supports the notion of general constraints as in CP.
This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving.
SCIP is available in source code and free for non-commercial use.
We demonstrate the usefulness of CIP on two tasks.
First, we apply the constraint integer programming approach to pure mixed integer programs.
Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers.
Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers.
The CIP approach is very effective here:
it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.
In a recent paper, Alfonsi, Schied and Schulz (ASS) propose a simple order book based model for the impact of large orders on stock prices. They use this model to derive optimal strategies for the execution of large orders. We test this model in the context of an agent based microscopic stochastic order book model that was recently proposed by Bovier, \v{C}ern\'{y} and Hryniv. While the ASS model captures some features of real markets, some assumptions in the model contradict our simulation results. In particular, from our simulations the recovery speed of the market after a large order is clearly depended on the order size, whereas the ASS model assumes the speed to be given by a constant. For this reason, we propose a generalisation of the model of ASS that incorporates this dependency, and derive the optimal investment strategies. We show that within our artificial market, correct fitting of this parameter leads to optimal hedging strategies that reduce the trading costs, compared to the ones produced by ASS. Finally, we show that the costs of applying the optimal strategies of the improved ASS model to the artificial market still differ significantly from the model predictions, indicating that even the improved model does not capture all of the relevant details of a real market.
We propose a simple model for the behaviour of longterm investors on a stock market. It consists of three particles that represent the stock's current price and the buyers', respectively sellers', opinion about the right trading price. As time evolves, both groups of traders update their opinions with respect to the current price. The speed of updating is controled by a parameter gamma; the price process is described by a geometric Brownian motion. We consider the market's stability in terms of the distance between the buyers' and sellers' opinion, and prove that the distance process is recurrent/transient in dependence on gamma.
A continuum model for the growth of self-assembled quantum dots that incorporates surface diffusion, an elastically deformable substrate, wetting interactions and anisotropic surface energy is presented.
Using a small slope approximation a thin film equation for the surface profile that describes facetted growth is derived.
A linear stability analysis shows that anisotropy acts to destabilize the surface. It lowers the critical height of flat films and there exists an anisotropy strength above which all thicknesses are unstable.
A numerical algorithm based on spectral differentiation is presented and simulation are carried out. These clearly show faceting of the growing islands and a logarithmically slow coarsening behavior.
A posteriori error estimators for non-symmetric eigenvalue model problems are discussed in [Heuveline and Rannacher, A posteriori error control for finite element approximations of elliptic eigenvalue problems, 2001] in the context of the dual-weighted residual method (DWR). This paper directly analyses the variational formulation rather than the non-linear ansatz of Becker and Rannacher for some convection-diffusion model problem and presents error estimators for the eigenvalue error based on averaging techniques. In the case of linear P1 finite elements and globally constant coefficients, the error estimates of the residual and averaging error estimators are refined. Moreover, several postprocessing techniques attached to the DWR paradigm plus two new dual-weighted error estimators are compared in numerical experiments. The first new estimator utilises an auxiliary Raviart-Thomas mixed finite element method and the second exploits an averaging technique in combination with ideas of DWR.
We propose an online model for general demand cost sharing games and identify critical properties for group-strategyproofness and weak group-strategyproofness of cost sharing mechanisms for these games. We define incremental online cost sharing mechanisms which can be derived from competitive algorithms.
Based on our general results, we develop online cost sharing mechanisms for several binary demand and general demand cost sharing games derived from network design and scheduling problems. Our results complement the work on incremental mechanisms by Moulin.
Optimal control of 3D state-constrained induction heating problems with nonlocal radiation effects
(2009)
The paper is concerned with a class of optimal heating problems in semiconductor single crystal growth processes. To model the heating process, time-harmonic Maxwell equations are considered in the system of the state. Due to the high temperatures characterizing crystal growth, it is necessary to include nonlocal radiation boundary conditions and a temperature-dependent heat conductivity in the description of the heat transfer process. The first goal of this paper is to prove the existence and uniqueness of the solution to the state equation. The regularity analysis associated with the time harmonic Maxwell equations is also studied. In the second part of the paper, the existence and uniqueness of the solution to the corresponding linearized equation is shown. With this result at hand, the differentiability of the control-to-state mapping operator associated with the state equation is derived. Finally, based on the theoretical results, first oder necessary optimality conditi!
ons for an associated optimal control problem are established.
In this work we consider the so-called Lur'e matrix equations that arise e.g. in model reduction and linear-quadratic infinite time horizon optimal control. We characterize the set of solutions in terms of deflating subspaces of even matrix pencils. In particular, it is shown that there exist solutions which are extremal in terms of definiteness. It is shown how these special solutions can be constructed deflating subspaces of even matrix pencils.
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.
In this article we study capacitated network design problems. We unify and extend polyhedral results for directed, bidirected and undirected link capacity models. Based on valid inequalities for a network cut we show that regardless of the link capacity model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investigation of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequalities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Library (SNDlib).
We consider the preemptive and non-preemptive problems of scheduling jobs with precedence constraints on parallel machines with the
objective to minimize the sum of~(weighted) completion times. We investigate an online model in which the scheduler learns about a
job when all its predecessors have completed. For scheduling on a single machine, we show matching lower and upper bounds of~$\Theta(n)$ and~$\Theta(\sqrt{n})$ for jobs with general and equal weights, respectively. We also derive corresponding results on parallel machines.
Our result for arbitrary job weights holds even in the more general stochastic online scheduling model where, in addition to the limited information about the job set, processing times are uncertain. For a
large class of processing time distributions, we derive also an improved performance guarantee if weights are equal.
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 describe a new software package for the numerical solution of general linear or nonlinear switched differential-algebraic equations (DAEs).
The package embeds the DAE solvers GELDA and GENDA into a hybrid mode controller that
determines the switch points, organizes the mode switching, and provides consistent initial values to restart the integration method at the switch point.
It can deal with systems of arbitrary index and with linear systems that do not have unique solutions or inconsistencies in the initial values or the inhomogeneity.
Nonuniqueness and inconsistencies are treated in a least square sense.
The package includes the possibility of sliding mode simulation that allows an efficient treatment of chattering behavior during the simulation of a hybrid system.
We give explicit descriptions how to use the package and include a numerical example.
We present a hierarchical a~posteriori error analysis for the
minimum value of the energy functional in symmetric obstacle
problems. The main result is that the energy of the exact solution
is, up to data oscillation, equivalent to an appropriate
hierarchical estimator. The proof of the main result does not
invoke any saturation assumption. Moreover, we prove an a
posteriori error estimate indicating that the estimator from
\cite{RHWHoppe_RKornhuber_1994a} is asymptotically reliable and we
give sufficient conditions for the validity of a saturation
assumption. Finally, we corroborate and complement our theoretical
results with numerical experiments.
We consider insurance derivatives depending on an external physical risk process, for example a temperature in a low dimensional climate model. We assume that this process is correlated with a tradable financial asset. We derive optimal strategies for exponential utility from terminal wealth, determine the indifference prices of the derivatives, and interpret them in terms of diversification pressure. Moreover we check the optimal investment strategies for standard admissibility criteria. Finally we compare the static risk connected with an insurance derivative to the reduced risk due to a dynamic investment into the correlated asset. We show that dynamic hedging reduces the risk aversion in terms of entropic risk measures by a factor related to the correlation.
Various applications in fluid dynamics and computational continuum mechanics motivate the development of reliable and efficient adaptive algorithms for mixed finite element methods. In order to save degrees of freedom, not all but just some selected set of finite element domains are refined. Hence the fundamental question of convergence as well as the question of optimality require new mathematical arguments. The presented adaptive algorithm for Raviart-Thomas mixed finite element methods solves the Poisson model problem, with optimal convergence rate.
Chen, Holst, and Xu presented "convergence and optimality of adaptive mixed finite element methods" (2008) following arguments of Rob Stevenson for the conforming finite element method. Their algorithm reduces oscillations separately, before approximating the solution by some adaptive algorithm in the spirit of W. Dörfler (1996). The algorithm proposed here appears more natural in switching to either reduction of the edge-error estimator or of the oscillations.
The paper considers the time integration of frictionless dynamical contact problems between viscoelastic bodies in the frame of the Signorini condition. Among the numerical integrators, interest focuses on the contact-stabilized Newmark method recently suggested by Deuflhard et al., which is compared to the classical Newmark method and an improved energy dissipative version due to Kane et al. In the absence of contact, any such variant is equivalent to the Störmer-Verlet scheme, which is well-known to have consistency order 2. In the presence of contact, however, the classical approach to discretization errors would not show consistency at all because of the discontinuity at the contact. Surprisingly, the question of consistency in the constrained situation has not been solved yet. The present paper fills this gap by means of a novel proof technique using specific norms based on earlier perturbation results due to the authors. The corresponding estimation of the local discretization error requires the bounded total variation of the solution. The results have consequences for the construction of an adaptive timestep control, which will be worked out subsequently in a forthcoming paper.
Lifted Domain Colorings
(2009)
Complex-valued functions are fundamental objects in complex analysis, algebra, differential geometry and in many other areas such as numerical mathematics and physics. Visualizing complex functions is a non-trivial task since maps between two-dimensional spaces are involved whose graph would be an unhandy submanifold
in four-dimensional space. The present paper improves the technique of “domain coloring” in several aspects: First, we lift domain coloring from the complex plane to branched Riemann surfaces, which are essentially the
correct domain for most complex functions. Second, we extend domain coloring to the visualization of general 2-valued maps on surfaces. As an application of such general maps we visualize the Gauss map of surfaces as domain colored plots and establish a link to current surface parametrization techniques and texture maps. Third, we adjust the color pattern in domain and in image space to produce higher quality domain colorings. The new color schemes specifically enhance the display of singularities, symmetries and path integrals, and give better qualitative measures of the complex map.
Structuring of surface meshes is a labor intensive task in reverse engineering. For example in CAD, scanned triangle meshes must be divided into characteristic/uniform patches to enable conversion into high-level spline surfaces. Typical industrial techniques, like rolling ball blends, are very labor intensive.
We provide a novel, robust and quick algorithm for the automatic generation of a patch layout based on a topology consistent feature graph. The graph separates the surface along feature lines into functional and geometric building blocks. Our algorithm then thickens thickens the edges of the feature graph and forms new regions with low varying curvature. Further these new regions - so called fillets and node patches - will have highly smooth boundary curves making it an ideal preprocessor for a subsequent spline fitting algorithm.
In semiconductor devices one basically distinguishes three spatial scales: The atomistic scale of the bulk semiconductor materials (sub-Angstroem), the scale of the interaction zone at the interface between two semiconductor materials together with the scale of the resulting size quantization (nanometer) and the scale of the device itself (micrometer). The paper focuses on the two scale transitions inherent in the hierarchy of scales in the device. We start with the description of the band structure of the bulk material by kp Hamiltonians on the atomistic scale. We describe how the envelope function approximation allows to construct kp Schroedinger operators describing the electronic states at the nanoscale which are closely related to the kp Hamiltonians. Special emphasis is placed on the possible existence of spurious modes in the kp Schroedinger model on the nanoscale which are inherited from anomalous band bending on the atomistic scale. We review results of the mathematical analysis of these multi-band kp Schroedinger operators. Besides of the confirmation of the main facts about the band structure usually taken for granted, key results are conditions on the coefficients of the kp Schroedinger operator for the nanostructure, which exclude spurious modes and an estimate of the size of the band gap. Using these results, we give an overview of properties of the electronic band structure of strained quantum wells. Further, the assumption of flat-band conditions across the nanostructure allows for upscaling of quantum calculations to state equations for semi-classical models. We demonstrate this approach for parameters such as the quantum corrected band-edges, the effective density of states, the optical response, and the optical peak gain. Further, we apply the kp Schroedinger theory to low gap quantum wells, a case where a proper rescaling of the optical matrix element is necessary to avoid spurious modes. Finally, we discuss the application of the kp Schroedinger models to biased quantum wells, the operation mode of electro-optic modulators.
The well known De Giorgi result on Hölder continuity for solutions of the Dirichlet problem is re-established for mixed boundary value problems, provided that the underlying domain is a Lipschitz domain and the border between the Dirichlet and the Neumann boundary part satisfies a very general geometric condition. Implications of this result for optimal control theory are presented.
We compute the length of geodesics on a Riemannian manifold by regular polynomial interpolation of the global solution of the eikonal equation related to the line element $ds^2=g_ijdx^idx^j$ of the manifold. Our algorithm approximates the length functional in arbitrarily strong Sobolev norms. Error estimates are obtained where the geometric information is used. It is pointed out how the algorithm can be used to get accurate approximations of solutions of linear parabolic partial differential equations leading to obvious applications in finance, physics and other sciences.
We show that elliptic second order operators $A$ of divergence type fulfill maximal parabolic regularity on distribution spaces, even if the underlying domain is highly non-smooth and $A$ is complemented with mixed boundary conditions. Applications to quasilinear parabolic equations with non-smooth data are presented.
We derive global analytic representations of fundamental solutions for a class of linear parabolic systems with full coupling of first order derivative terms where coefficients may depend on space and time. Pointwise convergence of the global analytic expansion is proved. This leads to analytic representations of solutions of initial-boundary problems of first and second type in terms of convolution integrals or convolution integrals and linear integral equations. The results have both analytical and numerical impact. Analytically, our representations of fundamental solutions of coupled parabolic systems may be used to define generalized stochastic processes. Moreover, some classical analytical results based on a priori estimates of elliptic equations are a simple corollary of our main result. Numerically, accurate, stable and efficient schemes for computation and error estimates in strong norms can be obtained for a considerable class of Cauchy- and initial-boundary problems of parabolic type. Furthermore, there are obvious and less obvious applications to finance and physics.
The Lang-Kobayashi model is a system of delay differential equations (DDEs) describing the dynamics of a semiconductor laser under delayed optical feedback. In this paper, we study the stability of so called external cavity modes (ECMs), which are harmonic oscillations corresponding to stationary lasing states. We focus on experimentally relevant situations, when the delay is large compared to the internal time scales of the laser. In this case, both the number of ECMs and the number of critical eigenvalues grows to infinity. Applying a newly developed asymptotic description for the spectrum of linearized DDEs with long delay, we are able to overcome this difficulty and to give a complete description of the stability properties of all ECMs. In particular, we distinguish between different types of weak and strong instabilities and calculate bifurcation diagrams that indicate the regions with different stability properties and the transitions between them.
We consider a new adaptive finite element (AFEM) algorithm for elliptic PDE-eigenvalue problems.
In contrast to other approaches we incorporate the iterative solution of the resulting finite dimensional
algebraic eigenvalue problems into the adaptation process.
In this way we can balance the costs of the adaption process
for the mesh with the costs for the iterative eigenvalue method. We present error estimates that incorporate
the discretization errors, approximation errors in the eigenvalue solver and roundoff errors and use
these for the adaptation process. We show that for the adaptation process it is possible to restrict to
very few iterations
of a Krylov subspace solver for the eigenvalue problem on coarse meshes.
We present several examples and show that this new approach achieves
much better complexity than previous AFEM approaches which assume that the algebraic
eigenvalue problem is solved to full accuracy.
We consider scheduling to minimize the weighted sum of completion
times on a single machine that may experience unexpected changes in
processing speed or even full breakdowns. We design a polynomial
time deterministic algorithm that finds a robust prefixed scheduling
sequence with a solution value within~$4$ times the value
an optimal clairvoyant algorithm can achieve, knowing the
disruptions in advance and even being allowed to interrupt jobs at
any moment. A randomized version of this algorithm attains in
expectation a ratio of~$e$ w.r.t. a clairvoyant optimum.
We show that such a ratio can never be achieved by any deterministic
algorithm by proving that the price of robustness of any such
algorithm is at least~$1+\sqrt{3} \approx 2.73205>e$.
As a direct consequence of our results, the question whether a
constant approximation algorithm exists for the problem with given
machine unavailability periods is answered affirmatively. We
complement this result by an FPTAS for the preemptive and non-preemptive special case with a single
non-available period.
For rather general thermodynamic equilibrium distribution functions the density of a statistical ensemble of quantum mechanical particles depends analytically on the potential in the Schrödinger operator describing the quantum system. A key to the proof is that the resolvent to a power less than one of an elliptic operator with non-smooth coefficients, and mixed Dirichlet/Neumann boundary conditions on a bounded up to three-dimensional Lipschitz domain factorizes over the space of essentially bounded functions.
A discrete model of a biological regulatory network can be represented as a discrete function f that contains all available information on interactions between network components and the rules governing the evolution of the network in the discrete state space. Both the information on the structure as well as the dynamics of the system can be represented as directed graphs. Since the state space size grows exponentially with the number of network components, analysis of large networks is a complex problem.
In this paper, we introduce the notion of symbolic steady state that allows us to identify subnetworks that govern the dynamics of the original network in at least a subset of state space. We then state rules to explicitly construct attractors of the system from subnetwork attractors. A further application of the underlying concept allows us to formulate sufficient conditions for the existence of multiple attractors resp. a cyclic attractor based on the existence of positive resp. negative feedback circuits in the structure graph. All results are discussed for dynamics derived from f via the synchronous as well as the asynchronous update rule.
We present an extension module for the Dune system. This module, called dune-subgrid, allows to mark elements of another Dune hierarchical grid. The set of marked elements can then be accessed as a Dune grid in its own right. dune-subgrid is free software and is available for download. We describe the functionality and use of dune-subgrid, comment on its implementation, and give two example applications.
First, we show how dune-subgrid can be used for micro-FE simulations of trabecular bone. Then we present an algorithm that allows to use exact residuals for the adaptive solution of the spatial problems of time-discretized evolution equations.
Interior Point Methods in Function Space for State Constraints - Inexact Newton and Adaptivity
(2009)
We consider an interior point method in function space for PDE constrained optimal control problems with state constraints. Our emphasis is on the construction and analysis of an algorithm that integrates a Newton path-following method with adaptive grid refinement. This is done in the framework of inexact Newton methods in function space, where the discretization error of each Newton step is controlled by adaptive grid refinement in the innermost loop. This allows to perform most of the required Newton steps on coarse grids, such that the overall computational time is dominated by the last few steps. For this purpose we propose an a-posteriori error estimator for a problem suited norm.
In this paper we are concerned with the application of interior point methods in function space to gradient constrained optimal control problems, governed by partial differential equations. We will derive existence of solutions together with first order optimality conditions. Afterwards we show continuity of the central path, together with convergence rates depending on the interior point parameter.
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 first order optimality conditions for state constrained optimal control problems. In particular we study the case where the state equation has not enough regularity to admit existence of a Slater point in function space. We overcome this difficulty by a special transformation. Under a density condition we show existence of Lagrange multipliers, which have a representation via measures and additional regularity properties.
Diffusion Weighted Imaging has become and will certainly continue to be an important tool in medical research and diagnostics. Data obtained with Diffusion Weighted Imaging are characterized by a high noise level. Thus, estimation of quantities like anisotropy indices or the main diffusion direction may be significantly compromised by noise in clinical or neuroscience applications. Here, we present a new package dti for R, which provides functions for the analysis of diffusion weighted data within the diffusion tensor model. This includes smoothing by a recently proposed structural adaptive smoothing procedure based on the Propagation-Separation approach in the context of the widely used Diffusion Tensor Model. We extend the procedure and show, how a correction for Rician bias can be incorporated. We use a heteroscedastic nonlinear regression model to estimate the diffusion tensor. The smoothing procedure naturally adapts to different structures of different size and thus avoids oversmoothing edges and fine structures. We illustrate the usage and capabilities of the package through some examples.
Increasing the spatial resolution in functional Magnetic Resonance Imaging (fMRI) inherently lowers the signal-to-noise ratio (SNR). In order to still detect functionally significant activations in high-resolution images, spatial smoothing of the data is required. However, conventional non-adaptive smoothing comes with a reduced effective resolution, foiling the benefit of the higher acquisition resolution. We show how our recently proposed structural adaptive smoothing procedure for functional MRI data can improve signal detection of high-resolution fMRI experiments regardless of the lower SNR. The procedure is evaluated on human visual and sensory-motor mapping experiments. In these applications, the higher resolution could be fully utilized and high-resolution experiments were outperforming normal resolution experiments by means of both statistical significance and information content
We present a thermodynamically consistent model to describe the austenite-ferrite phase transition in steel. We consider the influence of the mechanical displacement field due to eigenstrains caused by volumetric expansions. The model equations are derived in a systematical framework. They are based on the conservation laws for mass and momentum and the second law of thermodynamics. By means of numerical computations for a simplified interface-controlled model, we examine the influence of the mechanical contributions to the transformation kinetics and the equilibrium states.
In this paper, we consider the characterization of strong stationary solutions to
equilibrium problems with equilibrium constraints (EPECs). Assuming that the underlying
generalized equation satisfies strong regularity in the sense of Robinson, an explicit
multiplier-based stationarity condition can be derived. This is applied then
to an equilibrium model arising from ISO-regulated electricity spot markets.
Many problems in science and engineering require the evaluation of functionals of
the form $F(A) = u^T f(A)u$, where $A$ is a large symmetric matrix, $u$ a vector, and $f$ a nonlinear
function. A popular and fairly inexpensive approach to determining upper and lower bounds for
such functionals is based on first carrying out a few steps of the Lanczos procedure applied to $A$ with
initial vector $u$, and then evaluating pairs of Gauss and Gauss-Radau quadrature rules associated
with the tridiagonal matrix determined by the Lanczos procedure. The present paper extends this
approach to allow the use of rational Gauss quadrature rules.
Some aspects of reachability for parabolic boundary control problems with control constraints
(2009)
A class of one-dimensional parabolic optimal boundary control problems
is considered. The discussion includes Neumann, Robin, and Dirichlet
boundary conditions. The reachability of a given target state in final
time is discussed under box constraints on the control. As a mathematical
tool, related exponential moment problems are investigated. Moreover,
based on a detailed study of the adjoint state, a technique is presented
to find the location and the number of the switching points of optimal
bang-bang controls. Numerical examples illustrate this procedure.
We study a mathematical model for laser-induced thermotherapy,
a minimally invasive cancer treatment. The model consists of a
diffusion approximation of the radiation transport equation
coupled to a bio-heat equation and a model to describe the
evolution of the coagulated zone. Special emphasis is laid on
a refined model of the applicator device, accounting for the
effect of coolant flow inside. Comparisons between experiment
and simulations show that the model is able to predict the
experimentally achieved temperatures reasonably well.
This paper is concerned with the state-constrained optimal control of the
two-dimensional thermistor problem, a quasi-linear coupled system
of a parabolic and elliptic PDE with mixed boundary conditions.
This system models the heating of a conducting material by means of direct current.
Existence, uniqueness and continuity for the state system are derived by employing
maximal elliptic and parabolic regularity. By similar arguments the
linearized state system is discussed, while the adjoint system involving measures
is investigated using a duality argument. These results allow to derive
first-order necessary conditions for the optimal control problem.
We present two approximation methods for pricing of CMS spread options in Libor market models. Both approaches are based on approximating the underlying swap rates with lognormal processes under suitable measures. The first method is derived straightforwardly from the Libor market model. The second one uses a convexity adjustment technique under a linear swap model assumption. A numerical study demonstrates that both methods provide satisfactory approximations of spread option prices and can be used for calibration of a Libor market model to the CMS spread option market.
In this paper we develop several regression algorithms for solving general stochastic optimal control problems via Monte Carlo. This type of algorithms is particulary useful for problems with a high-dimensional state space and complex dependence structure of the underlying Markov process with respect to some control. The main idea behind the algorithms is to simulate a set of trajectories under some reference measure and to use the Bellman principle combined with fast methods for approximating conditional expectations and functional optimization. Theoretical properties of the presented algorithms are investigated and the convergence to the optimal solution is proved under mild assumptions. Finally, we present numerical results for the problem of pricing a high-dimensional Bermudan basket option under transaction costs in a financial market with a large investor.
We present recent developments in two-stage mixed-integer stochastic
programming with regard to application in power production planning.
In particular, we review structural properties, stability issues, scenario
reduction and decomposition algorithms for two-stage models. Furthermore,
we describe an application to stochastic thermal unit commitment.
In this paper, a model for (joint) dynamic chance constraints is proposed and applied to an optimization problem in water reservoir management. The model relies on discretization of the decision variables but keeps the probability distribution
continuous. Our approach relies on calculating probabilities of rectangles which is particularly useful in the presence of independent random variables but works for a moderate number of stages equally well in case of correlated variables. Numerical results are provided for two and three stages.
Structural adaptive smoothing provides a new concept of
edge-preserving non-parametric smoothing methods. In imaging it employs
qualitative assumption on the underlying homogeneity structure of the image.
The chapter describes the main principles of the approach and discusses
applications ranging from image denoising to the analysis of functional and
diffusion weighted Magnetic Resonance experiments.
The Real Multiple Dual
(2009)
In this paper we present a dual representation for the multiple stopping
problem, hence multiple exercise options. As such it is a natural generalization of the
method in Rogers (2002) and Haugh and Kogan (2004) for the standard stopping
problem for American options. We consider this representation as the real dual as it is
solely expressed in terms of an infimum over martingales rather than an infimum over
martingales and stopping times as in Meinshausen and Hambly (2004). For the multiple
dual representation we present three Monte Carlo simulation algorithms which require
only one degree of nesting.
This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column
generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures
scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures.
Wigner functions are functions on classical phase space, which are in one-to-one correspondence to square integrable functions on configuration space. For molecular quantum systems, classical transport of Wigner functions provides the basis of asymptotic approximation methods in the high energy regime. The article addresses the sampling of Wigner functions by Monte Carlo techniques. The approximation step is realized by an adaption of the Metropolis algorithm for real-valued functions with disconnected support. The quadrature, which computes values of the Wigner function, uses importance sampling with a Gaussian weight function. The numerical experiments combine the sampling with a surface hopping algorithm for non-adiabatic quantum dynamics. In agreement with theoretical considerations, the obtained results show an accuracy of two to four percent.
Whenever the invariant stationary density of metastable dynamical systems decomposes into almost invariant partial densities, its computation as eigenvector of some transition probability matrix is an ill-conditioned problem. In order to avoid this computational difficulty, we suggest to apply an aggregation/disaggregation method which only addresses wellconditioned sub-problems and thus results in a stable algorithm. In contrast to existing methods, the aggregation step is done via a sampling algorithm which covers only small patches of the sampling space. Finally, the theoretical analysis is illustrated by two biomolecular examples.
The complexity of molecular kinetics can be reduced significantly by a restriction to metastable conformations which are almost invariant sets of molecular dynamical systems. With the Robust Perron Cl uster Analysis PCCA+, developed by Weber and Deuflhard, we have a tool available which can be used to identify these conformations from a transition probability matrix. This method can also be applied to the corresponding transition rate matrix which provides important information concerning transition pathways of single molecules. In the present paper, we explain the relationship between these tw o concepts and the extraction of conformation kinetics from transition rates. Moreover, we show how transition rates can be approximated and conclude with numerical examples.
Fitting multidimensional data using gradient penalties and the sparse grid combination technique
(2009)
Sparse grids, combined with gradient penalties provide an attractive tool for regularised least squares fitting. It has earlier been found that the combination technique, which builds a sparse grid function using a linear combination of approximations on partial grids, is here not as effective as it is in the case of elliptic partial differential equations. We argue that this is due to the irregular and random data distribution, as well as the proportion of the number of data to the grid resolution. These effects are investigated both in theory and experiments. As part of this investigation we also show how overfitting arises when the mesh size goes to zero. We conclude with a study of modified ``optimal'' combination coefficients who prevent the amplification of the sampling noise present while using the original combination coefficients.
In this paper we study the shape and growth of structured pseudospectra
for small matrix perturbations of the form $A \leadsto
A_\Delta=A+B\Delta C$, $\Delta \in \DD$, $\|\Delta\|\leq \delta$.
It is shown that the properly scaled pseudospectra components converge
to non-trivial limit sets as $\delta$ tends to 0.
We discuss the relationship of these limit sets with $\mu$-values and
structured eigenvalue condition numbers for multiple eigenvalues.
We discuss the solution of linear second order differential-algebraic equations with variable coefficients.
Since index reduction and order reduction for higher order higher index differential-algebraic systems do not commute, appropriate index reduction methods for higher order DAEs are required.
We present an index reduction method based on derivative arrays that allows to determine
an equivalent second order system of lower index in a numerical computable way.
For such an equivalent second order system
an appropriate order reduction method allows to formulate a suitable first order DAE system of low index
that has the same solution components as the original second order system.
Optimality conditions for a class of optimal control problems with quasilinear elliptic equations
(2008)
A class of optimal control problems for quasilinear elliptic
equations is considered, where the coefficients of the elliptic
differential operator depend on the state function. First- and
second-order optimality conditions are discussed for an associated
control-constrained optimal control problem. In particular, the
Pontryagin maximum principle and second-order sufficient
optimality conditions are derived. One of the main difficulties is
the non-monotone character of the state equation.
New types of stationary solutions of a one-dimensional driven sixth-order Cahn-Hilliard type equation that arises as a model for epitaxially growing nano-structures such as quantum dots, are derived by an extension of the method of matched asymptotic expansions that retains exponentially small terms. This method yields analytical expressions for far-field behavior as well as the widths of the humps of these spatially non-monotone solutions in the limit of small driving force strength which is the deposition rate in case of epitaxial growth. These solutions extend the family of the
monotone kink and antikink solutions. The hump spacing is related to solutions of the Lambert $W$ function.
Using phase space analysis for the corresponding fifth-order dynamical
system, we use a numerical technique that enables the efficient and accurate tracking of the solution branches, where the asymptotic solutions are used as initial input.
Additionally, our approach is first demonstrated for the related but simpler driven fourth-order Cahn-Hilliard equation, also known as the convective Cahn-Hilliard equation.
In the well-known discrete modeling framework developed by R. Thomas, the structure of a biological regulatory network is captured in an interaction graph, which, together with a set of Boolean parameters, gives rise to a state transition graph describing all possible dynamical behaviors. For complex networks the analysis of the dynamics becomes more and more difficult, and efficient methods to carry out the analysis are needed. In this paper, we focus on identifying subnetworks of the system that govern the behavior of the system as a whole. We present methods to derive trajectories and attractors of the network from the dynamics suitable subnetworks display in isolation. In addition, we use these ideas to link the existence of certain structural motifs, namely circuits, in the interaction graph to the character and number of attractors in the state transition graph, generalizing and refining results presented in \cite{AB07}. Lastly, we show for a specific class of networks that all possible asymptotic behaviors of networks in that class can be derived from the dynamics of easily identifiable subnetworks.
We study Nash equilibria and the price of anarchy in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges
change over time. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; on the other hand, there is a rich literature on game theoretic aspects of flows over time in the traffic community.
In this paper, we present the first known results on the price of anarchy for flows over time. We also present algorithms for computing Nash flows over time. Those algorithms have to iteratively solve certain interesting and new static flow problems. Our results are based on a novel characterization of Nash equilibria for flows over time. The underlying flow over time model is a variant of the so-called deterministic queuing model that is very popular in road traffic simulation and related fields.
The paper deals with co-derivative formulae for normal cone mappings to smooth
inequality systems. Both the regular (Linear Independence Constraint Qualification satisfied)
and nonregular (Mangasarian-Fromovitz Constraint Qualification satisfied) cases are considered.
A major part of the results relies on general transformation formulae previously obtained by
Mordukhovich and Outrata. This allows one to derive exact formulae for general smooth, regular and polyhedral, possibly
nonregular systems. In the nonregular, nonpolyhedral case a generalized transformation formula by
Mordukhovich and Outrata applies, however, a major difficulty consists in
checking a calmness condition of a certain multivalued mapping. The paper provides a translation
of this condition in terms of much easier to verify constraint qualifications. The final section is
devoted to the situation where the calmness condition is violated. A series of examples
illustrates the use and comparison of the presented formulae.
The main focus of this paper is on an a-posteriori analysis for the method of proper orthogonal decomposition (POD) applied to optimal control problems governed by
parabolic and elliptic PDEs. Based on a perturbation method it is deduced how far the suboptimal
control, computed on the basis of the POD model, is from the (unknown)
exact one. Numerical examples illustrate the realization of the proposed approach for linear-quadratic problems governed by parabolic and elliptic partial differential equations.
Second-order sufficient optimality conditions are established for the optimal control
of semilinear elliptic and parabolic equations with pointwise constraints on the control and the state. In
contrast to former publications on this subject, the cone of critical directions is the smallest possible in the
sense that the second-order sufficient conditions are the closest to the associated necessary ones. The theory
is developed for elliptic distributed controls in domains up to dimension three. Moreover, problems of elliptic
boundary control and parabolic distributed control are discussed in spatial domains of dimension two and one,
respectively.
We present and analyze novel hierarchical a posteriori error estimates
for self-adjoint elliptic obstacle problems.
Our approach differs from straightforward, but non-reliable estimators~\cite{RHWHoppe_RKornhuber_1994a}
by an additional extra term accounting for the deviation
of the discrete free boundary in the localization step.
We prove efficiency and reliability
on a saturation assumption and a regularity condition on the underlying grid.
Heuristic arguments suggest
that the extra term is of higher order and preserves full locality.
Numerical computations confirm our theoretical findings.
A generalization of the method of Chu, Liu and Mehrmann
for the computation of the Hamiltonian real Schur form is presented.
The new method avoids some of the difficulties that may arise when
a Hamiltonian matrix has tightly clustered groups of eigenvalues.
A detailed analysis of the method is presented and several numerical examples demonstrate the superior behavior of the method.
To approximate convolutions which occur in evolution equations with memory terms, a variable-stepsize algorithm is presented for which advancing $N$ steps requires only $O(N\log N)$ operations and $O(\log N)$ active memory, in place of $O(N^2)$ operations and $O(N)$ memory for a direct implementation. A basic feature of the fast algorithm is the reduction, via contour integral representations, to differential equations which are solved numerically with adaptive step sizes. Rather than the kernel itself, its Laplace transform is used in the algorithm. The algorithm is illustrated on three examples: a blow-up example originating from a Schrödinger equation with concentrated nonlinearity, chemical reactions with inhibited diffusion, and viscoelasticity with a fractional order constitutive law.
A new approach to derive transparent boundary conditions (TBCs) for wave, Schrödinger, heat and drift-diffusion equations is presented. It relies on the pole condition and distinguishes between physical reasonable and unreasonable solutions by the location of the singularities of the spatial Laplace transform of the exterior solution. To obtain a numerical algorithm, a Möbius transform is applied to map the Laplace transform onto the unit disc. In the transformed coordinate the solution is expanded into a power series. Finally, equations for the coefficients of the power series are derived. These are coupled to the equation in the interior, and yield transparent boundary conditions.
Numerical results are presented in the last section, showing that the error introduced by the new approximate TBCs decays exponentially in the number of coefficients.
In this review article we discuss different techniques to solve numerically the
time-dependent Schrödinger equation on unbounded domains.
We present in detail the most recent approaches and describe briefly alternative ideas pointing out the relations between these works.
We conclude with several numerical examples from
different application areas to compare the presented techniques. We mainly focus on the one-dimensional problem but also touch upon the situation in two space dimensions and the cubic nonlinear case.
Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment
structure.
We investigate the detection of symmetries appearing in this approach.
We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear
time if the assignment structure is known.
We consider hybrid systems of differential-algebraic equations and present
a general framework for general nonlinear over- and underdetermined hybrid
systems that allows the
analysis of existence and uniqueness and the application of index reduction
methods for hybrid differential-algebraic systems.
A particular difficulty in the numerical simulation of hybrid systems is
(numerical) chattering, i.e., fast oscillations between modes of operations.
A regularization technique using sliding modes allows to regularize the
system behavior in the case of chattering.
Further, we show how chattering behavior during the numerical solution can
be prevented using sliding mode simulation. The advantage of the sliding mode
simulation is illustrated by numerical examples.
In this article, we analyse three related preconditioned steepest descent algorithms, which are partially popular in Hartree-Fock and Kohn-Sham theory as well as invariant subspace computations, from the viewpoint of minimization of the corresponding functionals, constrained by orthogonality conditions. We exploit the geometry of the of the admissible manifold, i.e. the invariance with respect to unitary transformations, to reformulate the problem on the Grassmann manifold as the admissible set. We then prove asymptotical linear convergence of the algorithms under the condition that the Hessian of the corresponding Lagrangian is elliptic on the tangent space of the Grassmann manifold at the minimizer.
Canonical forms for matrix triples $(A,G,\hat G)$, where
$A$ is arbitrary rectangular and $G$, $\hat G$ are either real symmetric
or skew symmetric, or complex Hermitian or skew Hermitian, are derived.
These forms generalize classical product Schur forms as well as
singular value decompositions.
An new proof for the complex case is given, where there is no need to
distinguish whether $G$ and $\hat G$ are Hermitian or skew Hermitian.
This proof is independent from the results in Bolschakov/Reichstein 1995, where
a similar canonical form has been obtained for the complex case,
and it allows generalization to the real case. Here,
the three cases, i.e., that
$G$ and $\hat G$ are both symmetric, both skew symmetric or one each,
are treated separately.
About 15 years ago, Goemans and Williamson formally introduced the primal-dual framework for approximation algorithms and applied it to a class of network design optimization problems. Since then literally hundreds of results appeared that extended, modified and applied the technique to a wide range of optimization problems.
In this paper we define a class of cost-sharing games arising from Goemans and Williamson's original network design problems. We then show how to derive a group-strategyproof (i.e., collusion resistant) mechanism for such a game, using an existing primal-dual algorithm for the underlying optimization problem as a black box. The budget-balance factor of this mechanism is proportional to the performance ratio of the primal-dual algorithm if the optimization problem satisfies an additional technical condition.
Most existing collusion-resistant cost-sharing mechanisms are obtained through skillful adaptation of existing primal-dual algorithms for the associated optimization problems. This paper shows that, at least for a large class of games arising from network design problems, no such adaptation is necessary.
The nonlinear Schrödinger equation based on the Taylor approximation of the material dispersion can become invalid for ultrashort and few-cycle optical pulses. Instead, we use a rational fit to the dispersion function such that the resonances are naturally accounted for. This approach allows us to derive a simple non-envelope model for short pulses propagating in one spatial dimension. This model is further investigated numerically and analytically.
We discuss first order optimality conditions for state constrained
optimal control problems. Our concern is the treatment of problems,
where the solution of the state equation is not known to be continuous,
as in the case of boundary control in three space dimensions or optimal
control with parabolic partial differential equations. We show existence of
measure valued Lagrangian multipliers, which have just enough additional
regularity to be applicable to all possibly discontinuous solutions of the
state equation.
An extended mathematical framework for barrier methods for state constrained optimal control compared to [Schiela, ZIB-Report 07-07] is considered. This allows to apply the results derived there to more general classes of optimal control problems, in particular to boundary control and finite dimensional control.
We study barrier methods for state constrained optimal control problems
with PDEs. In the focus of our analysis is the path of minimizers of the
barrier subproblems with the aim to provide a solid theoretical basis for function
space oriented path-following algorithms. We establish results on existence,
continuity, and convergence of this path. Moreover, we consider the structure of
barrier subdifferentials, which play the role of dual variables.
In a rather general setting of multivariate stochastic volatility market models we derive global iterative probabilistic schemes for computing the free boundary and its Greeks for a generic class of American derivative models using front-fixing methods. Establishment of convergence is closely linked to a proof of global regularity of the free boundary surface.
The paper focuses on multi-period aspects of risk functionals. It discusses properties,
provides dual representations and offers methods for constructing multiperiod
risk functionals. On the way, existence results and representations for conditional
risk mappings are derived. In particular, conditional, multi-period, and
nested versions of the average value-at-risk are given. Finally, the importance of
polyhedral multi-period risk functionals for their employment in practical dynamic
decision making and risk management is discussed.
Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination.
In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm.
Dynamic risk management in electricity portfolio optimization via polyhedral risk functionals
(2008)
We propose a methodology for combining risk management with optimal planning of power production and trading based on probabilistic knowledge about future uncertainties such as demands and spot prices. Typically, such a joint optimization of risk and (expected) revenue yields additional overall efficiency. Our approach is based on stochastic optimization (stochastic programming) with a risk functional as objective. The latter maps an uncertain cash flow to a real number. In particular, we employ so-called polyhedral risk functionals which, though being non-linear mappings, preserve linearity structures of optimization problems. Therefore, these are favorable to the numerical tractability of the optimization problems. The class of polyhedral risk functionals contains well-known risk functionals such as Average-Value-at-Risk and expected polyhedral utility. Moreover, it is also capable to model different dynamic risk mitigation strategies.
We present a new inexact nonsmooth Newton method for the solution
of convex minimization problems with piecewise smooth, pointwise
nonlinearities. The algorithm consists of a nonlinear smoothing
step on the fine level and a linear coarse correction.
Suitable postprocessing guarantees global convergence
even in the case of a single multigrid step for each linear subproblem.
Numerical examples show that the overall efficiency
is comparable to multigrid for similar linear problems.
In this review, we intend to clarify the underlying ideas and the relations
between various multigrid methods ranging from subset decomposition,
to projected subspace decomposition and truncated multigrid.
In addition, we present a novel globally convergent inexact active set method
which is closely related to truncated multigrid. The numerical properties
of algorithms are carefully assessed by means of a degenerate problem and
a problem with a complicated coincidence set.
The goal of this paper is a mathematical investigation of dilatometer experiments. These are used to detect the kinetics
of solid-solid phase transitions in steel upon cooling from the high temperature phase. Usually, the data are only used for measuring
the start and end temperature of the phase transition. In the case of several coexisting product phases, expensive microscopic
investigations have to be performed to obtain the resulting fractions of the different phases. In contrast, it is shown in this paper that in the case of at most two product phases the complete phase transition kinetics including the final phase fractions are uniquely determined by the dilatometer data. Numerical results confirm the theoretical result.
We consider an adaptive finite element method (AFEM) for obstacle problems associated with linear second order elliptic boundary value problems and prove a reduction in the energy norm of the discretization error which leads to $R$-linear convergence. This result is shown to hold up to a consistery error due to the extension of the discrete multipliers (point functionals) to $H^{-1}$ and a possible mismatch between the continuous and discrete coincidence and noncoincidence sets. The AFEM is based on a residual-type error estimator consisting of element and edge residuals. The a posteriori error analysis reveals that the significant difference to the unconstrained case lies in the fact that these residuals only have to be taken into account within the discrete noncoincidence set. The proof of the error reduction property uses the reliability and the discrete local efficiency of the estimator as well as a perturbed Galerkin orthogonality. Numerical results are given illustrating the performance of the AFEM.