510 Mathematik
Refine
Year of publication
Document Type
- Doctoral Thesis (85)
- Habilitation (2)
- Article (1)
Has Fulltext
- yes (88)
Keywords
- Optimierung (14)
- Approximationstheorie (7)
- Approximation (6)
- Funktionalanalysis (6)
- Funktionentheorie (6)
- Partielle Differentialgleichung (6)
- Universalität (6)
- Shape Optimization (5)
- universal functions (5)
- Analysis (4)
Institute
- Mathematik (65)
- Fachbereich 4 (20)
We consider irreversible investment problems where an agent decides if and when to
invest in a project which generates a perpetual flow of profits after paying some investment
cost. The agent observes the profits which follow a geometric Brownian motion
with possibly time-dependent drift. Moreover, she discounts future profits as well as the
investment cost. In the classical model introduced by Dixit and Pindyck (1994, Chapter
6, Section 1), the drift is constant and known to the agent. Even though this assumption
is convenient for their analysis, it is generally unrealistic. In this thesis, we consider three
variants of the classical model which turn out to be two-dimensional optimal stopping
problems: Unknown drift, a jump of the drift at a fixed time, and a jump of the drift at
an exponentially distributed time.
For all variants, the optimal investment decision only depends on the current profits
and the current state of the respective additional feature, which is either the current
updated belief on the true state of the drift, the remaining time until the drift jumps,
or the current state of the drift. Precisely, we characterize the optimal stopping time
by a continuous and monotonic boundary function mapping the state of the additional
feature on the minimal stopping trigger for the profit process. To achieve these results
and to derive the boundary function, we employ the following two approaches:
For unknown drift and a jump of the drift at a fixed time, we compute the boundary function
numerically by a nonlinear integral equation. This approach requires establishing
several properties of the boundary function and the value function such as monotonicity
and continuity. Since the agent’s payoff not only depends on the current state of the
profit process but also on the state of the additional feature, many standard arguments
to derive these properties are not applicable. Instead, our proofs build on a method to
connect the value functions for different initial profit levels and initial states of the additional feature. Based on this, we show that the value function solves the associated free
boundary problem. Next, we derive a nonlinear integral equation whose unique solution
is the boundary function. Utilizing this, we compute the boundary function numerically
via a fixed-point iteration in combination with a Monte-Carlo method.
For a jump of the drift at an exponentially distributed time and in a special case for
unknown drift, we determine the boundary function by a nonlinear equation which, for
the latter variant, even yields an analytical expression. We reduce both problems to
a family of parameterized one-dimensional optimal stopping problems whose optimal thresholds characterize the boundary function. For each sub-problem, we solve the
associated free boundary problem and verify that its solution corresponds to the value
function. This way, we establish a nonlinear equation for the threshold.
Additionally, we numerically analyze the influence of parameter variation on the optimal
investment behavior for every variant. Particularly, we analyze the value of information
in the case of unknown drift and, for the same expected jump time, compare the models
whose drift jumps at a fixed or an exponentially distributed time.
The maximization of submodular functions under various kinds of constraints is a central component of many combinatorial optimization problems, since submodular functions naturally cover the property of diminishing returns. This dissertation comprises four scientific articles in which we consider three different combinatorial optimization problems involving the maximization of submodular functions under knapsack or cardinality constraints.
The first article considers the maximization of a submodular function defined on a weighted set of items under a knapsack constraint with unknown capacity. Assume that items are packed sequentially into the knapsack, and that an oracle reveals whether an item being attempted for packing fits into the currently packed knapsack. If an item fits, it is packed irrevocably; otherwise, either packing stops immediately (packing without discarding), or the item is removed, and packing continues (packing with discarding).
Our main result concerns non-adaptive packing without discarding, under the assumption that the unknown knapsack capacity is greater than or equal to the weight of the heaviest item. Specifically, we present the first polynomial-time algorithm for computing a universal policy that, for any unknown capacity, performs at least as well as the classical greedy algorithm, studied by Wolsey (1982), for the same known capacity.
In the second article, we study a game-theoretic variant of maximizing a submodular function under a cardinality constraint. In this variant, an initial solution to the classical problem is determined first. Subsequently, a predetermined number of elements of the ground set, possibly containing elements of the initial solution, are deleted. If any deleted elements were part of the initial solution, they are replaced by a set of at most equal cardinality. The objective is to maximize the value of the ultimate solution, with the deletion being maximally disadvantageous to it. We analyze several special cases of this problem and present polynomial-time algorithms for computing optimal or approximately optimal ultimate solutions. For the general case, we present a polynomial-time algorithm whose approximation guarantee depends on the curvature of the submodular objective function.
The last two articles of this dissertation address the classic problem of maximizing a submodular function under a knapsack constraint. The first of these articles focuses on exact solvers: We present a branch-and-bound algorithm along with several acceleration techniques. We compare it against two solvers by Sakaue and Ishihata (2018), which currently achieve the strongest performance reported in the literature, as well as a branch-and-cut algorithm implemented using Gurobi that solves a binary linear reformulation of the submodular knapsack problem, demonstrating that our methods are highly successful.
The last article considers variants of the classical greedy algorithm for submodular maximization under a knapsack constraint studied by Wolsey (1982). While the classical algorithm assumes access to an exact incremental oracle in every iteration, we generalize the known approximation results for this algorithm to the presence of only an $\alpha$-approximate oracle that returns in every iteration an item whose relative marginal gain approximates the maximum relative marginal gain by at least $\frac{1}{\alpha}$, with $\alpha \geq 1$ fixed. We also present an approximation result for a variant of the classical greedy algorithm that uses an approximate oracle only in the first iteration and an exact oracle thereafter.
Three-Point Difference Schemes of High Order of Accuracy for Solving the Sturm-Liouville Problem
(2025)
The dissertation is devoted to the construction and justification of three-point difference schemes of high order of accuracy for solving the Sturm-Liouville problem. A new algorithmic realization of the exact three-point difference scheme on a non-uniform grid has been developed. We show that to compute the coefficients of the exact scheme in an arbitrary grid node, it is necessary to solve two auxiliary Cauchy problems for the system of three linear ordinary differential equations of the first order. The coefficient stability of the exact three-point difference scheme is proved. If the Cauchy problems are solved numerically using any one-step method, we obtain the truncated three-point difference scheme. The accuracy estimate of three-point difference schemes was obtained and the algorithm for finding their solution was developed.
We also developed a new algorithmic realization of the exact three-point difference scheme for the Sturm-Liouville problem with singularities at the ends of the interval. As in the case of the classical Sturm-Liouville problem, to find the coefficients of the exact three-point difference scheme, it is necessary to solve two auxiliary Cauchy problems for each grid node. The coefficient stability of the exact three-point difference scheme is proved. Since the Cauchy problems for the first and last grid nodes are singular, the Taylor series method has been developed to solve them. The accuracy estimate of truncated three-point difference schemes was obtained. To solve the difference scheme, the Newton's iterative method is used.
Numerical experiments are presented which confirm the efficiency of the proposed approach.
The goal of this work is to compare operators that are defined on probably varying Hilbert spaces. Distance concepts for operators as well as convergence concepts for such operators are explained and examined. For distance concepts we present three main notions. All have in common that they use space-linking operators that connect the spaces. At first, we look at unitary maps and compare the unitary orbits of the operators. Then, we consider isometric embeddings, which is based on a concept of Joachim Weidmann. Then we look at contractions but with more norm equations in comparison. The latter idea is based on a concept of Olaf Post called quasi-unitary equivalence. Our main result is that the unitary and isometric distances are equal provided the operators are both self-adjoint and have 0 in their essential spectra. In the third chapter, we focus specifically on the investigation of these distance terms for compact operators or operators in p-Schatten classes. In this case, the interpretation of the spectra as null sequences allows further distance investigation. Chapter four deals mainly with convergence terms of operators on varying Hilbert spaces. The analyses in this work deal exclusively with concepts of norm resolvent convergence. The main conclusion of the chapter is that the generalisation for norm resolvent convergence of Joachim Weidmann and the generalisation of Olaf Post, called quasi-unitary equivalence, are equivalent to each other. In addition, we specify error bounds and deal with the convergence speed of both concepts. Two important implications of these convergence notions are that the approximation is spectrally exact, i.e., the spectra converge suitably, and that the convergence is transferred to the functional calculus of the bounded functions vanishing at infinity.
Although universality has fascinated over the last decades, there are still numerous open questions in this field that require further investigation. In this work, we will mainly focus on classes of functions whose Fourier series are universal in the sense that they allow us to approximate uniformly any continuous function defined on a suitable subset of the unit circle.
The structure of this thesis is as follows. In the first chapter, we will initially introduce the most important notation which is needed for our following discussion. Subsequently, after recalling the notion of universality in a general context, we will revisit significant results concerning universality of Taylor series. The focus here is particularly on universality with respect to uniform convergence and convergence in measure. By a result of Menshov, we will transition to universality of Fourier series which is the central object of study in this work.
In the second chapter, we recall spaces of holomorphic functions which are characterized by the growth of their coefficients. In this context, we will derive a relationship to functions on the unit circle via an application of the Fourier transform.
In the second part of the chapter, our attention is devoted to the $\mathcal{D}_{\textup{harm}}^p$ spaces which can be viewed as the set of harmonic functions contained in the $W^{1,p}(\D)$ Sobolev spaces. In this context, we will also recall the Bergman projection. Thanks to the intensive study of the latter in relation to Sobolev spaces, we can derive a decomposition of $\mathcal{D}_{\textup{harm}}^p$ spaces which may be seen as analogous to the Riesz projection for $L^p$ spaces. Owing to this result, we are able to provide a link between $\mathcal{D}_{\textup{harm}}^p$ spaces and spaces of holomorphic functions on $\mathbb{C}_\infty \setminus \s$ which turns out to be a crucial step in determining the dual of $\mathcal{D}_{\textup{harm}}^p$ spaces.
The last section of this chapter deals with the Cauchy dual which has a close connection to the Fantappié transform. As an application, we will determine the Cauchy dual of the spaces $D_\alpha$ and $D_{\textup{harm}}^p$, two results that will prove to be very helpful later on. Finally, we will provide a useful criterion that establishes a connection between the density of a set in the direct sum $X \oplus Y$ and the Cauchy dual of the intersection of the respective spaces.
The subsequent chapter will delve into the theory of capacities and, consequently, potential theory which will prove to be essential in formulating our universality results. In addition to introducing further necessary terminologies, we will define capacities in the first section following [16], however in the frame of separable metric spaces, and revisit the most important results about them.
Simultaneously, we make preparations that allow us to define the $\mathrm{Li}_\alpha$-capacity which will turn out to be equivalent to the classical Riesz $\alpha$-capacity. The $\mathrm{Li}_\alpha$-capacity proves to be more adapted to the $D_\alpha$ spaces. It becomes apparent in the course of our discussion that the $\mathrm{Li}_\alpha$-capacity is essential to prove uniqueness results for the class $D_\alpha$. This leads to the centerpiece of this chapter which forms the energy formula for the $\mathrm{Li}_\alpha$-capacity on the unit circle. More precisely, this identity establishes a connection between the energy of a measure and its corresponding Fourier coefficients. We will briefly deal with the complement-equivalence of capacities before we revisit the concept of Bessel and Riesz capacities, this time, however, in a much more general context, where we will mainly rely on [1]. Since we defined capacities on separable metric spaces in the first section, we can draw a connection between Bessel capacities and $\mathrm{Li}_\alpha$-capacities. To conclude this chapter, we would like to take a closer look at the geometric meaning of capacities. Here, we will point out a connection between the Hausdorff dimension and the polarity of a set, and transfer it to the $\mathrm{Li}_\alpha$-capacity. Another aspect will be the comparison of Bessel capacities across different dimensions, in which the theory of Wolff potentials crystallizes as a crucial auxiliary tool.
In the fourth chapter of this thesis, we will turn our focus to the theory of sets of uniqueness, a subject within the broader field of harmonic analysis. This theory has a close relationship with sets of universality, a connection that will be further elucidated in the upcoming chapter.
The initial section of this chapter will be dedicated to the notion of sets of uniqueness that is specifically adapted to our current context. Building on this concept, we will recall some of the fundamental results of this theory.
In the subsequent section, we will primarily rely on techniques from previous chapters to determine the closed sets of uniqueness for the class $\mathcal{D}_{\alpha}$. The proofs we will discuss are largely influenced by [16, p.\ 178] and [9, pp.\ 82].
One more time, it will become evident that the introduction of the $\mathrm{Li}_\alpha$-capacity in the third chapter and the closely associated energy formula on the unit circle, were the pivotal factors that enabled us to carry out these proofs.
In the final chapter of our discourse, we will present our results on universality. To begin, we will recall a version of the universality criterion which traces back to the work of Grosse-Erdmann (see [26]). Coupled with an outcome from the second chapter, we will prove a result that allows us to obtain the universality of a class using the technique of simultaneous approximation. This tool will play a key role in the proof of our universality results which will follow hereafter.
Our attention will first be directed toward the class $D_\alpha$ with $\alpha$ in the interval $(0,1]$. Here, we summarize that universality with respect to uniform convergence occurs on closed and $\alpha$-polar sets $E \subset \s$. Thanks to results of Carleson and further considerations, which particularly rely on the favorable behavior of the $\mathrm{Li}_\alpha$-kernel, we also find that this result is sharp. In particular, it may be seen as a generalization of the universality result for the harmonic Dirichlet space.
Following this, we will investigate the same class, however, this time for $\alpha \in [-1,0)$. In this case, it turns out that universality with respect to uniform convergence occurs on closed and $(-\alpha)$-complement-polar sets $E \subset \s$. In particular, these sets of universality can have positive arc measure. In the final section, we will focus on the class $D_{\textup{harm}}^p$. Here, we manage to prove that universality occurs on closed and $(1,p)$-polar sets $E \subset \s$. Through results of Twomey [68] combined with an observation by Girela and Pélaez [23], as well as the decomposition of $D_{\textup{harm}}^p$, we can deduce that the closed sets of universality with respect to uniform convergence of the class $D_{\textup{harm}}^p$ are characterized by $(1,p)$-polarity. We conclude our work with an application of the latter result to the class $D^p$. We will show that the closed sets of divergence for the class $D^p$ are given by the $(1,p)$-polar sets.
Mixed-Integer Optimization Techniques for Robust Bilevel Problems with Here-and-Now Followers
(2025)
In bilevel optimization, some of the variables of an optimization problem have to be an optimal solution to another nested optimization problem. This specific structure renders bilevel optimization a powerful tool for modeling hierarchical decision-making processes, which arise in various real-world applications such as in critical infrastructure defense, transportation, or energy. Due to their nested structure, however, bilevel problems are also inherently hard to solve—both in theory and in practice. Further challenges arise if, e.g., bilevel problems under uncertainty are considered.
In this dissertation, we address different types of uncertainties in bilevel optimization using techniques from robust optimization. We study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we tackle using the notion of Gamma-robustness. We present two exact branch-and-cut approaches to solve these Gamma-robust bilevel problems, along with cuts tailored to the important class of monotone interdiction problems. Given the overall hardness of the considered problems, we additionally propose heuristic approaches for mixed-integer, linear, and Gamma-robust bilevel problems. The latter rely on solving a linear number of deterministic bilevel problems so that no problem-specific tailoring is required. We assess the performance of both the exact and the heuristic approaches through extensive computational studies.
In addition, we study the problem of determining optimal tolls in a traffic network in which the network users hedge against uncertain travel costs in a robust way. The overall toll-setting problem can be seen as a single-leader multi-follower problem with multiple robustified followers. We model this setting as a mathematical problem with equilibrium constraints, for which we present a mixed-integer, nonlinear, and nonconvex reformulation that can be tackled using state-of-the-art general-purpose solvers. We further illustrate the impact of considering robustified followers on the toll-setting policies through a case study.
Finally, we highlight that the sources of uncertainty in bilevel optimization are much richer compared to single-level optimization. To this end, we study two aspects related to so-called decision uncertainty. First, we propose a strictly robust approach in which the follower hedges against erroneous observations of the leader's decision. Second, we consider an exemplary bilevel problem with a continuous but nonconvex lower level in which algorithmic necessities prevent the follower from making a globally optimal decision in an exact sense. The example illustrates that even very small deviations in the follower's decision may lead to arbitrarily large discrepancies between exact and computationally obtained bilevel solutions.
Partial differential equations are not always suited to model all physical phenomena, especially, if long-range interactions are involved or if the actual solution might not satisfy the regularity requirements associated with the partial differential equation. One remedy to this problem are nonlocal operators, which typically consist of integrals that incorporate interactions between two separated points in space and the corresponding solutions to nonlocal equations have to satisfy less regularity conditions.
In PDE-constrained shape optimization the goal is to minimize or maximize an objective functional that is dependent on the shape of a certain domain and on the solution to a partial differential equation, which is usually also influenced by the shape of this domain. Moreover, parameters associated with the nonlocal model are oftentimes domain dependent and thus it is a natural next step to now consider shape optimization problems that are governed by nonlocal equations.
Therefore, an interface identification problem constrained by nonlocal equations is thoroughly investigated in this thesis. Here, we focus on rigorously developing the first and second shape derivative of the associated reduced functional. In addition, we study first- and second-order shape optimization algorithms in multiple numerical experiments.
Moreover, we also propose Schwarz methods for nonlocal Dirichlet problems as well as regularized nonlocal Neumann problems. Particularly, we investigate the convergence of the multiplicative Schwarz approach and we conduct a number of numerical experiments, which illustrate various aspects of the Schwarz method applied to nonlocal equations.
Since applying the finite element method to solve nonlocal problems numerically can be quite costly, Local-to-Nonlocal couplings emerged, which combine the accuracy of nonlocal models on one part of the domain with the fast computation of partial differential equations on the remaining area. Therefore, we also examine the interface identification problem governed by an energy-based Local-to-Nonlocal coupling, which can be numerically computed by making use of the Schwarz method. Here, we again present a formula for the shape derivative of the associated reduced functional and investigate a gradient based shape optimization method.
Optimal Error Bounds in Normal and Edgeworth Approximation of Symmetric Binomial and Related Laws
(2024)
This thesis explores local and global normal and Edgeworth approximations for symmetric
binomial distributions. Further, it examines the normal approximation of convolution powers
of continuous and discrete uniform distributions.
We obtain the optimal constant in the local central limit theorem for symmetric binomial
distributions and its analogs in higher-order Edgeworth approximation. Further, we offer a
novel proof for the known optimal constant in the global central limit theorem for symmetric
binomial distributions using Fourier inversion. We also consider the effect of simple continuity
correction in the global central limit theorem for symmetric binomial distributions. Here, and in
higher-order Edgeworth approximation, we found optimal constants and asymptotically sharp
bounds on the approximation error. Furthermore, we prove asymptotically sharp bounds on the
error in the local case of a relative normal approximation to symmetric binomial distributions.
Additionally, we provide asymptotically sharp bounds on the approximation error in the local
central limit theorem for convolution powers of continuous and discrete uniform distributions.
Our methods include Fourier inversion formulae, explicit inequalities, and Edgeworth expansions, some of which may be of independent interest.
Differential equations yield solutions that necessarily contain a certain amount of regularity and are based on local interactions. There are various natural phenomena that are not well described by local models. An important class of models that describe long-range interactions are the so-called nonlocal models, which are the subject of this work.
The nonlocal operators considered here are integral operators with a finite range of interaction and the resulting models can be applied to anomalous diffusion, mechanics and multiscale problems.
While the range of applications is vast, the applicability of nonlocal models can face problems such as the high computational and algorithmic complexity of fundamental tasks. One of them is the assembly of finite element discretizations of truncated, nonlocal operators.
The first contribution of this thesis is therefore an openly accessible, documented Python code which allows to compute finite element approximations for nonlocal convection-diffusion problems with truncated interaction horizon.
Another difficulty in the solution of nonlocal problems is that the discrete systems may be ill-conditioned which complicates the application of iterative solvers. Thus, the second contribution of this work is the construction and study of a domain decomposition type solver that is inspired by substructuring methods for differential equations. The numerical results are based on the abstract framework of nonlocal subdivisions which is introduced here and which can serve as a guideline for general nonlocal domain decomposition methods.
The publication of statistical databases is subject to legal regulations, e.g. national statistical offices are only allowed to publish data if the data cannot be attributed to individuals. Achieving this privacy standard requires anonymizing the data prior to publication. However, data anonymization inevitably leads to a loss of information, which should be kept minimal. In this thesis, we analyze the anonymization method SAFE used in the German census in 2011 and we propose a novel integer programming-based anonymization method for nominal data.
In the first part of this thesis, we prove that a fundamental variant of the underlying SAFE optimization problem is NP-hard. This justifies the use of heuristic approaches for large data sets. In the second part, we propose a new anonymization method belonging to microaggregation methods, specifically designed for nominal data. This microaggregation method replaces rows in a microdata set with representative values to achieve k-anonymity, ensuring each data row is identical to at least k − 1 other rows. In addition to the overall dissimilarities of the data rows, the method accounts for errors in resulting frequency tables, which are of high interest for nominal data in practice. The method employs a typical two-step structure: initially partitioning the data set into clusters and subsequently replacing all cluster elements with representative values to achieve k-anonymity. For the partitioning step, we propose a column generation scheme followed by a heuristic to obtain an integer solution, which is based on the dual information. For the aggregation step, we present a mixed-integer problem formulation to find cluster representatives. To this end, we take errors in a subset of frequency tables into account. Furthermore, we show a reformulation of the problem to a minimum edge-weighted maximal clique problem in a multipartite graph, which allows for a different perspective on the problem. Moreover, we formulate a mixed-integer program, which combines the partitioning and the aggregation step and aims to minimize the sum of chi-squared errors in frequency tables.
Finally, an experimental study comparing the methods covered or developed in this work shows particularly strong results for the proposed method with respect to relative criteria, while SAFE shows its strength with respect to the maximum absolute error in frequency tables. We conclude that the inclusion of integer programming in the context of data anonymization is a promising direction to reduce the inevitable information loss inherent in anonymization, particularly for nominal data.