The hypervolume subset selection problem consists of finding a subset, with a given cardinality, of a nondominated set of points that maximizes the hypervolume indicator. This problem arises in selection procedures of population-based heuristics for multiobjective optimization, and for which practically efficient algorithms are strongly required. In this article, we provide two new formulations for the two-dimensional variant of this problem.
The first is an integer programming formulation that can be solved by solving its linear relaxation. The second formulation is a \(k\)-link shortest path formulation on a special digraph with Monge property that can be solved by dynamic programming in \(\mathcal{O}(n^2)\) time complexity. This improves upon the existing result of \(O(n^3)\) in Bader.
Edgeworth expansions have been introduced as a generalization of the central limit theorem and allow to investigate the convergence properties of sums of i.i.d. random variables. We consider triangular arrays of lattice random vectors and obtain a valid Edgeworth expansion for this case. The presented results can be used, for example, to study the convergence behavior of lattice models.
We propose a model for acid-mediated tumor invasion involving two different scales: the microscopic one, for the dynamics of intracellular protons and their exchange with their extracellular counterparts, and the macroscopic scale of interactions between tumor cell and normal cell populations, along with the evolution of extracellular protons. We also account for the tactic behavior of cancer cells, the latter being assumed to biase their motion according to a gradient of extracellular protons (following [2,31] we call this pH taxis). A time dependent (and also time delayed) carrying capacity for the tumor cells in response to the effects of acidity is considered as well. The global well posedness of the resulting multiscale model is proved with a regularization and fixed point argument. Numerical simulations are performed in order to illustrate the behavior of the model.
This thesis is devoted to the computational aspects of intersection theory and enumerative geometry. The first results are a Sage package Schubert3 and a Singular library schubert.lib which both provide the key functionality necessary for computations in intersection theory and enumerative geometry. In particular, we describe an alternative method for computations in Schubert calculus via equivariant intersection theory. More concretely, we propose an explicit formula for computing the degree of Fano schemes of linear subspaces on hypersurfaces. As a special case, we also obtain an explicit formula for computing the number of linear subspaces on a general hypersurface when this number is finite. This leads to a much better performance than classical Schubert calculus.
Another result of this thesis is related to the computation of Gromov-Witten invariants. The most powerful method for computing Gromov-Witten invariants is the localization of moduli spaces of stable maps. This method was introduced by Kontsevich in 1995. It allows us to compute Gromov-Witten invariants via Bott's formula. As an insightful application, we computed the numbers of rational curves on general complete intersection Calabi-Yau threefolds in projective spaces up to degree six. The results are all in agreement with predictions made from mirror symmetry.
In 2006 Jeffrey Achter proved that the distribution of divisor class groups of degree 0 of function fields with a fixed genus and the distribution of eigenspaces in symplectic similitude groups are closely related to each other. Gunter Malle proposed that there should be a similar correspondence between the distribution of class groups of number fields and the distribution of eigenspaces in ceratin matrix groups. Motivated by these results and suggestions we study the distribution of eigenspaces corresponding to the eigenvalue one in some special subgroups of the general linear group over factor rings of rings of integers of number fields and derive some conjectural statements about the distribution of \(p\)-parts of class groups of number fields over a base field \(K_{0}\). Where our main interest lies in the case that \(K_{0}\) contains the \(p\)th roots of unity, because in this situation the \(p\)-parts of class groups seem to behave in an other way like predicted by the popular conjectures of Henri Cohen and Jacques Martinet. In 2010 based on computational data Malle has succeeded in formulating a conjecture in the spirit of Cohen and Martinet for this case. Here using our investigations about the distribution in matrixgroups we generalize the conjecture of Malle to a more abstract level and establish a theoretical backup for these statements.
In this paper we analyze the vibrations of nonlinear structures by means of the novel approach of isogeometric finite elements. The fundamental idea of isogeometric finite elements is to apply the same functions, namely B-Splines and NURBS (Non-Uniform Rational B-Splines), for describing the geometry and for representing the numerical solution. In case of linear vibrational analysis, this approach has already been shown to possess substantial advantages over classical finite elements, and we extend it here to a nonlinear framework based on the harmonic balance principle.
As application, the straight nonlinear Euler-Bernoulli beam is used, and overall, it is demonstrated that isogeometric finite elements with B-Splines in combination with the harmonic balance method are a powerful means for the analysis of nonlinear structural vibrations. In particular, the smoother k-method provides higher accuracy than the p-method for isogeometric nonlinear vibration analysis.
Non-smooth contact dynamics provides an increasingly popular simulation framework for granular material. In contrast to classical discrete element methods, this approach is stable for arbitrary time steps and produces visually acceptable results in very short computing time. Yet when it comes to the prediction of draft forces, non-smooth contact dynamics is typically not accurate enough. We therefore propose to combine the method class with an interior point algorithm for higher accuracy. Our specific algorithm is based on so-called Jordan algebras and exploits the relation to symmetric cones in order to tackle the conical constraints that are intrinsic to frictional contact problems. In every interior point iteration a linear system has to be solved. We analyze how the interior point method behaves when it is combined with Krylov subspace solvers and incomplete factorizations. We show that efficient preconditioners and efficient linear solvers are essential for the method to be applicable to large-scale problems. Using BiCGstab as a linear solver and incomplete Cholesky factorizations, we substantially improve the accuracy in comparison to the projected Gauss-Jacobi solver.
A large class of estimators including maximum likelihood, least squares and M-estimators are based on estimating functions. In sequential change point detection related monitoring functions can be used to monitor new incoming observations based on an initial estimator, which is computationally efficient because possible numeric optimization is restricted to the initial estimation. In this work, we give general regularity conditions under which we derive the asymptotic null behavior of the corresponding tests in addition to their behavior under alternatives, where conditions become particularly simple for sufficiently smooth estimating and monitoring functions. These regularity conditions unify and even extend a large amount of existing procedures in the literature, while they also allow us to derive monitoring schemes in time series that have not yet been considered in the literature including non-linear autoregressive time series and certain count time series such as binary or Poisson autoregressive models. We do not assume that the estimating and monitoring function are equal or even of the same dimension, allowing for example to combine a non-robust but more precise initial estimator with a robust monitoring scheme. Some simulations and data examples illustrate the usefulness of the described procedures.
In this article we present a method to extend high order finite volume schemes
to networks of hyperbolic conservation laws with algebraic coupling conditions. This method is based on an ADER approach in time to solve the
generalized Riemann problem at the junction. Additionally to the high order accuracy, this approach maintains an exact conservation of quantities if
stated by the coupling conditions. Several numerical examples confirm the
benefits of a high order coupling procedure for high order accuracy and stable
shock capturing.
This thesis is divided into two parts. Both cope with multi-class image segmentation and utilize
non-smooth optimization algorithms.
The topic of the first part, namely unsupervised segmentation, is the application of clustering
to image pixels. Therefore, we start with an introduction of the biconvex center-based clustering
algorithms c-means and fuzzy c-means, where c denotes the number of classes. We show that
fuzzy c-means can be seen as an approximation of c-means in terms of power means.
Since noise is omnipresent in our image data, these simple clustering models are not suitable
for its segmentation. To this end, we introduce a general and finite dimensional segmentation
model that consists of a data term stemming from the aforementioned clustering models plus a
continuous regularization term. We tackle this optimization model via an alternating minimiza-
tion approach called regularized c-centers (RcC). Thereby, we fix the centers and optimize the
segment membership of the pixels and vice versa. In this general setting, we prove convergence
in the sense of set-valued algorithms using Zangwill’s Theory [172].
Further, we present a segmentation model with a total variation regularizer. While updating
the cluster centers is straightforward for fixed segment memberships of the pixels, updating the
segment membership can be solved iteratively via non-smooth, convex optimization. Thereby,
we do not iterate a convex optimization algorithm until convergence. Instead, we stop as soon as
we have a certain amount of decrease in the objective functional to increase the efficiency. This
algorithm is a particular implementation of RcC providing also the corresponding convergence
theory. Moreover, we show the good performance of our method in various examples such as
simulated 2d images of brain tissue and 3d volumes of two materials, namely a multi-filament
composite superconductor and a carbon fiber reinforced silicon carbide ceramics. Thereby, we
exploit the property of the latter material that two components have no common boundary in
our adapted model.
The second part of the thesis is concerned with supervised segmentation. We leave the area
of center based models and investigate convex approaches related to graph p-Laplacians and
reproducing kernel Hilbert spaces (RKHSs). We study the effect of different weights used to
construct the graph. In practical experiments we show on the one hand image types that
are better segmented by the p-Laplacian model and on the other hand images that are better
segmented by the RKHS-based approach. This is due to the fact that the p-Laplacian approach
provides smoother results, while the RKHS approach provides often more accurate and detailed
segmentations. Finally, we propose a novel combination of both approaches to benefit from the
advantages of both models and study the performance on challenging medical image data.
Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms
(2014)
