In this paper, we present a new semidefinite programming hierarchy for covering problems in compact metric spaces.

In recent years, these kind of hierarchies were developed primarily for geometric packing and for energy minimization problems, and they frequently provide the best known bounds.

Starting from a semidefinite programming hierarchy for the dominating set problem in graph theory, we derive the new hierarchy for covering and show some of its basic properties: The hierarchy converges in finitely many steps, but the first level collapses to the volume bound when the compact metric space is homogeneous.

In the present article we propose a mixed-integer approximation of adjustable-robust optimization problems, that have both, continuous and discrete variables on the lowest level. As these trilevel problems are notoriously hard to solve, we restrict ourselves to weakly-connected instances. Our approach allows us to approximate, and in some cases exactly represent, the trilevel problem as a single-level mixed-integer problem. This allows us to leverage the computational efficiency of state-of-the-art mixed-integer programming solvers. We demonstrate the value of this approach by applying it to the optimization of power systems, particularly to the control of smart converters.

The presented work addresses two-stage stochastic programs (2SPs), a broadly applicable model to capture optimization problems subject to uncertain parameters with adjustable decision variables. In case the adjustable or second-stage variables contain discrete decisions, the corresponding 2SPs are known to be NP-complete. The standard approach of forming a single-stage deterministic equivalent problem can be computationally challenging even for small instances, as the number of variables and constraints scales with the number of scenarios. To avoid forming a potentially huge MILP problem, we build upon an approach of approximating the expected value of the second-stage problem by a neural network (NN) and encoding the resulting NN into the first-stage problem. The proposed algorithm alternates between optimizing the first-stage variables and retraining the NN. We demonstrate the value of our approach with the example of computing operating points in power systems by showing that the alternating approach provides improved first-stage decisions and a tighter approximation between the expected objective and its neural network approximation.

Finding point configurations, that yield the maximum polarization (Chebyshev constant) is gaining interest in the field of geometric optimization. In the present article, we study the problem of unconstrained maximum polarization on compact sets. In particular, we discuss necessary conditions for local optimality, such as that a locally optimal configuration is always contained in the convex hull of the respective darkest points. Building on this, we propose two sequences of mixed-integer linear programs in order to compute lower and upper bounds on the maximal polarization, where the lower bound is constructive. Moreover, we prove the convergence of these sequences towards the maximal polarization.

Compressed sensing is an image reconstruction technique to achieve high-quality results from limited amount of data. In order to achieve this, it utilizes prior knowledge about the samples that shall be reconstructed. Focusing on image reconstruction in nanotomography, this work proposes enhancements by including additional problem-specific knowledge. In more detail, we propose further classes of algebraic inequalities that are added to the compressed sensing model. The first consists in a valid upper bound on the pixel brightness. It only exploits general information about the projections and is thus applicable to a broad range of reconstruction problems. The second class is applicable whenever the sample material is of roughly homogeneous composition. The model favors a constant density and penalizes deviations from it. The resulting mathematical optimization models are algorithmically tractable and can be solved to global optimality by state-of-the-art available implementations of interior point methods. In order to evaluate the novel models, obtained results are compared to existing image reconstruction methods, tested on simulated and experimental data sets. The experimental data comprise one 360° electron tomography tilt series of a macroporous zeolite particle and one absorption contrast nano X-ray computed tomography (nano-CT) data set of a copper microlattice structure. The enriched models are optimized quickly and show improved reconstruction quality, outperforming the existing models. Promisingly, our approach yields superior reconstruction results, particularly when only a small number of tilt angles is available.

Linear complementarity problems (LCPs) are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many subareas of mathematics like game theory, optimization, and matrix theory. Despite their close relation to optimization, the protection of LCPs against uncertainties---especially in the sense of robust optimization---is still in its infancy. During the last years, robust LCPs have only been studied using the notions of strict and -robustness. Unfortunately, both concepts lead to the problem that the existence of robust solutions cannot be guaranteed. In this paper, we consider affinely adjustable robust LCPs. In the latter, a part of the LCP solution is allowed to adjust via a function that is affine in the uncertainty. We show that this notion of robustness allows us to establish strong characterizations of solutions for the cases of uncertain matrix and vector, separately, from which existence results can be derived. Our main results are valid for the case of an uncertain LCP vector. Here, we additionally provide sufficient conditions on the LCP matrix for the uniqueness of a solution. Moreover, based on characterizations of the affinely adjustable robust solutions, we derive a mixed-integer programming formulation that allows us to solve the corresponding robust counterpart. If, in addition, the certain LCP matrix is positive semidefinite, we prove polynomial-time solvability and uniqueness of robust solutions. If the LCP matrix is uncertain, characterizations of solutions are developed for every nominal matrix; i.e., these characterizations are, in particular, independent of the definiteness of the nominal matrix. Robust solutions are also shown to be unique for a positive definite LCP matrix, but both uniqueness and mixed-integer programming formulations still remain open problems if the nominal LCP matrix is not positive definite.

Pareto efficiency for robust linear programs was introduced by Iancu and Trichakis in [Manage Sci 60(1):130–147, 9]. We generalize their approach and theoretical results to robust optimization problems in Euclidean spaces with affine uncertainty. Additionally, we demonstrate the value of this approach in an exemplary manner in the area of robust semidefinite programming (SDP). In particular, we prove that computing a Pareto robustly optimal solution for a robust SDP is tractable and illustrate the benefit of such solutions at the example of the maximal eigenvalue problem. Furthermore, we modify the famous algorithm of Goemans and Williamson [Assoc Comput Mach 42(6):1115–1145, 8] in order to compute cuts for the robust max-cut problem that yield an improved approximation guarantee in non-worst-case scenarios.

This work studies equilibrium problems under uncertainty where firms maximize their profits in a robust way when selling their output. Robust optimization plays an increasingly important role when best guaranteed objective values are to be determined, independently of the specific distributional assumptions regarding uncertainty. In particular, solutions are to be determined that are feasible regardless of how the uncertainty manifests itself within some predefined uncertainty set. Our mathematical analysis adopts the robust optimization perspective in the context of equilibrium problems. First, we present structural insights for a single-stage, nonadjustable robust setting. We then go one step further and study the more complex two-stage or adjustable case where a part of the variables can adjust to the realization of the uncertainty. We compare equilibrium outcomes with the corresponding centralized robust optimization problem where the sum of all profits are maximized. As we find, the market equilibrium for the perfectly competitive firms differs from the solution of the robust central planner, which is in stark contrast to classical results regarding the efficiency of market equilibria with perfectly competitive firms. For the different scenarios considered, we furthermore are able to determine the resulting price of anarchy. In the case of non-adjustable robustness, for fixed demand in every time step the price of anarchy is bounded whereas it is unbounded if the buyers are modeled by elastic demand functions. For the two-stage adjustable setting, we show how to compute subsidies for the firms that lead to robust welfare optimal equilibria.

Knowledge-based determination of the best-possible experimental setups for nanoparticle design is highly challenging. Additionally, such processes are accompanied by noticeable uncertainties. Therefore, protection against those is needed. Robust optimization helps determining optimal processes. The latter guarantees quality requirements regardless of how uncertainties e.g., in raw materials, particle size distributions (PSD), heat and mass transport characteristics, and (growth) rates, manifest within predefined ranges. To approach this task, we exemplarily model a particle synthesis process with seeded growth by population balance equations and study different growth kinetics. We determine the mean residence time maximizing the product mass subject to a guaranteed yield. Additionally, we hedge against uncertain growth rates and derive an algorithmically tractable reformulation for the robustified problem. This reformulation can be applied if both the objective and the constraint functions are quasiconcave in the uncertainty which is a natural assumption in this context. We also show that the approach extends to higher-dimensional uncertainties if the uncertain parameters do not influence each other. We evaluate our approach for seeded growth synthesis of zinc oxide quantum dots and demonstrate computationally that a guaranteed yield is met for all growth rates within predefined regions. The protection against uncertainties only reduces the maximum amount of product that can be obtained by a negligible margin.

The present thesis is a commencement of a generalization of covering results in specific settings, such as the Euclidean space or the sphere, to arbitrary compact metric spaces. In particular we consider coverings of compact metric spaces $(X,d)$ by balls of radius $r$. We are interested in the minimum number of such balls needed to cover $X$, denoted by $\Ncal(X,r)$. For finite $X$ this problem coincides with an instance of the combinatorial \textsc{set cover} problem, which is $\mathrm{NP}$-complete. We illustrate approximation techniques based on the moment method of Lasserre for finite graphs and generalize these techniques to compact metric spaces $X$ to obtain upper and lower bounds for $\Ncal(X,r)$. \\ The upper bounds in this thesis follow from the application of a greedy algorithm on the space $X$. Its approximation quality is obtained by a generalization of the analysis of Chv\'atal's algorithm for the weighted case of \textsc{set cover}. We apply this greedy algorithm to the spherical case $X=S^n$ and retrieve the best non-asymptotic bound of B\"or\"oczky and Wintsche. Additionally, the algorithm can be used to determine coverings of Euclidean space with arbitrary measurable objects having non-empty interior. The quality of these coverings slightly improves a bound of Nasz\'odi. \\ For the lower bounds we develop a sequence of bounds $\Ncal^t(X,r)$ that converge after finitely (say $\alpha\in\N$) many steps: $$\Ncal^1(X,r)\leq \ldots \leq \Ncal^\alpha(X,r)=\Ncal(X,r).$$ The drawback of this sequence is that the bounds $\Ncal^t(X,r)$ are increasingly difficult to compute, since they are the objective values of infinite-dimensional conic programs whose number of constraints and dimension of underlying cones grow accordingly to $t$. We show that these programs satisfy strong duality and derive a finite dimensional semidefinite program to approximate $\Ncal^2(S^2,r)$ to arbitrary precision. Our results rely in part on the moment methods developed by de Laat and Vallentin for the packing problem on topological packing graphs. However, in the covering problem we have to deal with two types of constraints instead of one type as in packing problems and consequently additional work is required.

Die vorliegende Arbeit ist der Beginn einer Verallgemeinerung von Resultaten über spezifische Überdeckungen, wie etwa Überdeckungen des euklidischen Raumes oder Überdeckungen der Sphäre, zu einer Theorie auf kompakten metrischen Räumen. Insbesondere betrachtet man Überdeckungen eines kompakten metrischen Raumes $(X,d)$ durch Kugeln mit Radius $r$. Das Augenmerk liegt hierbei auf der minimalen Anzahl solcher Kugeln, welche benötigt wird um $X$ zu überdecken. Wir bezeichnen diese Anzahl mit $\Ncal(X,r)$. Für endliche Räume $X$ entspricht dieses Problem einer Instanz des kombinatorischen \textsc{set cover} Problems, welches NP-vollständig ist. Wir beschreiben Approximationstechniken, basierend auf der Momentenmethode von Lasserre für endliche Graphen und verallgemeinern diese Techniken auf kompakte metrische Räume um untere und obere Schranken zu erhalten. \\ Die oberen Schranken in dieser Arbeit folgen aus der Anwendung eines Greedy-Algorithmus auf den Raum $X$. Die Approximationsgüte des Algorithmus erhalten wir durch eine Verallgemeinerung der Analyse von Chv\'atals Algorithmus für gewichtete \textsc{set cover} Probleme. Wir wenden den genannten Greedy-Algorithmus auf den sphärischen Fall $X=S^n$ an und erhalten die beste, nicht asymptotische Schranke von Böröczky und Wintsche. Weiterhin kann der Algorithmus genutzt werden, um Überdeckungen des euklidischen Raumes durch beliebige messbare Objekte mit nicht leerem Inneren zu bestimmen. Die Approximationsgüte dieser Überdeckungen stellt eine leichte Verbesserung der Schranken von Nasz\'odi dar. \\ Um untere Schranken zu erhalten entwickeln wir eine Folge von Schranken $\Ncal^t(X,r)$, welche nach endlich vielen (bezeichnet mit $\alpha\in\N$) Schritten konvergiert: $$\Ncal^1(X,r)\leq \ldots \leq \Ncal^\alpha(X,r)=\Ncal(X,r).$$ Der Nachteil dieser Folge ist, dass die Schranken $\Ncal^t(X,r)$ mit wachsendem $t$ immer schwieriger zu berechnen sind, da sie die Zielfunktionswerte unendlichdimensionaler konischer Programme sind, deren Anzahl an Bedingungen und Dimension der Kegel mit $t$ wachsen. Wir zeigen, dass diese Programme die Bedingung der starken Dualität erfüllen und leiten ein endlichdimensionales semidefinites Programm ab, welches darauf abzielt $\Ncal^2(S^2,r)$ in beliebiger Präzision zu approximieren. Unsere Ergebnisse basieren teilweise auf der Momentenmethode von de Laat und Vallentin für das Packungsproblem auf topologischen Packungsgraphen. Jedoch müssen wir uns im Überdeckungsproblem um zwei Arten von Bedingungen kümmern anstatt nur einer Art wie im Packungsproblem. Dies benötigt zusätzlichen Aufwand.