65-XX NUMERICAL ANALYSIS
Refine
Year of publication
Document Type
- ZIB-Report (35)
- Master's Thesis (5)
- Doctoral Thesis (2)
- Software (2)
Is part of the Bibliography
- no (44)
Keywords
- finite element method (5)
- optimal control (4)
- reduced basis method (4)
- rigorous optical modeling (3)
- Algebraic multigrid (2)
- Automatic Differentiation (2)
- Lipschitz Continuity (2)
- Monte Carlo (2)
- Nonsmooth (2)
- PDE (2)
Institute
- Numerical Mathematics (23)
- Computational Medicine (7)
- Mathematical Optimization (6)
- Modeling and Simulation of Complex Processes (6)
- Visual and Data-centric Computing (6)
- Computational Nano Optics (5)
- Visual Data Analysis (5)
- Computational Systems Biology (4)
- Energy Network Optimization (3)
- Mathematical Optimization Methods (3)
Convergence Properties of Newton's Method for Globally Optimal Free Flight Trajectory Optimization
(2023)
The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition.
This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set.
This thesis examines how taking into account surface to surface radiation
impacts the cooling process in general. We formulate the non local bound-
ary condition after introducing the general setting for the cooling model. In
section 3, the mathematical description of the radiative heat transfer is dis-
cussed. We cover the implementation of the radiative matrix in section 4,
which is followed by a brief explanation of the radiative matrix’s structure
and several techniques to dealing with the accompanying challenges.
We investigate the importance of radiative heat transport by applying the
given approach to a two-dimensional geometry and computing the ensuing
cooling curves. We compare the findings of our computation to those ac-
quired from experiment conducted and find that they are extremely similar.
There is a considerable difference (of about 35%) in the time of cooling of the
surface where there is a possibility of influence of radiation from the second
surface to that of the surface with no influence at all. Although it is possible
to infer that heat convection plays a role in the total result, this has yet to be
proved. However, one can clearly see the significance of the surface to surface
radiative heat transfer on these parts confirming the research question posed
at the begining. The effect of the surface to surface radiative heat transfer
has an influence on the resulting cooling time and should be considered in
the model.
UG is a generic framework to parallelize branch-and-bound based solvers (e.g., MIP, MINLP, ExactIP) in a distributed or shared memory computing environment. It exploits the powerful performance of state-of-the-art "base solvers", such as SCIP, CPLEX, etc. without the need for base solver parallelization.
UG framework, ParaSCIP(ug[SCIP,MPI]) and FiberSCIP (ug[SCIP,Pthreads]) are available as a beta version.
v1.0.0: new documentation and cmake, generalization of ug framework, implementation of selfsplitrampup for fiber- and parascip, better memory and time limit handling.
Sampling rare events in metastable dynamical systems is often a computationally expensive task and one needs to resort to enhanced sampling methods such as importance sampling. Since we can formulate the problem of finding optimal importance sampling controls as a stochastic optimization problem, this then brings additional numerical challenges and the convergence of corresponding algorithms might as well suffer from metastabilty. In this article we address this issue by combining systematic control approaches with the heuristic adaptive metadynamics method. Crucially, we approximate the importance sampling control by a neural network, which makes the algorithm in principle feasible for high dimensional applications. We can numerically demonstrate in relevant metastable problems that our algorithm is more effective than previous attempts and that only the combination of the two approaches leads to a satisfying convergence and therefore to an efficient sampling in certain metastable settings.
In many applications, geodesic hierarchical models are adequate for the study of temporal observations. We employ such a model derived for manifold-valued data to Kendall's shape space. In particular, instead of the Sasaki metric, we adapt a functional-based metric, which increases the computational efficiency and does not require the implementation of the curvature tensor. We propose the corresponding variational time discretization of geodesics and employ the approach for longitudinal analysis of 2D rat skulls shapes as well as 3D shapes derived from an imaging study on osteoarthritis. Particularly, we perform hypothesis test and estimate the mean trends.
UG is a generic framework to parallelize branch-and-bound based solvers (e.g., MIP, MINLP, ExactIP) in a distributed or shared memory computing environment. It exploits the powerful performance of state-of-the-art "base solvers", such as SCIP, CPLEX, etc. without the need for base solver parallelization.
UG framework, ParaSCIP(ug[SCIP,MPI]) and FiberSCIP (ug[SCIP,Pthreads]) are available as a beta version. For MIP solving, ParaSCIP and FiberSCIP are well debugged and should be stable. For MINLP solving, they are relatively stable, but not as thoroughly debugged. This release version should handle branch-and-cut approaches where subproblems are defined by variable bounds and also by constrains for ug[SCIP,*] ParaSCIP and FiberSCIP). Therefore, problem classes other than MIP or MINLP can be handled, but they have not been tested yet.
v0.9.1: Update orbitope cip files.
In this thesis, adaptive algorithms in optimization under PDE constraints have been inves-
tigated. In its application, the aim of optimization is to increase the longevity of implants,
namely the hip joint implant, and in doing so to minimize stress shielding and simultaneously minimize the influence of locally high stresses, that, above a threshold value, are malign to the bone structure. Under the constraint of the equilibrium of forces, describing an elastodynamic setup, coupled with a contact inequality condition, a computationally expensive problem formulation is given.
The first step to make the solution of the given problem possible and efficient was to change over to the spatial equilibrium equation, thus rendering an elastostatic setup. Subsequently the intrinsically dynamic motions – trajectories in the load domain – were converted to the static setup. Thus, the trajectories are marginalized to the load domain and characterized with probability distributions. Therefore the solving of the PDE constraint, the contact problem, is simplified.
Yet in the whole optimization process, the solving of the PDE, the spatial equilibrium equation together with the contact condition has the most expensive contribution still and hence needed further reduction. This was achieved by application of Kriging interpolation to the load responses of the integrated distribution of stress difference and the maximum stresses. The interpolation of the two response surfaces only needs comparatively few PDE solves to set up the models. Moreover, the Kriging models can be adaptively extended by sequentially adding sample-response pairs. For this the Kriging inherent variance is used to estimate ideal new sample locations with maximum variance values. In doing so, the overall interpolation variance and therefore the interpolation error is reduced.
For the integration of the integrated stress differences and penalty values on the relative high dimensional load domain Monte Carlo integration was implemented, averting the curse of dimension. Here, the motion’s probability distribution combined with patient specific data of motion frequencies is taken advantage of, making obsolete the use of the otherwise necessary importance sampling.
Throughout the optimization, the FE-discretization error and the subsequently attached errors entering the solution process via PDE discretization and approximative
solving of the PDE, Kriging interpolation and Monte Carlo integration need to decrease. While the FE-discretization error and the solution of the elastostatic contact problem were assumed precise enough, numerics showed, that the interpolation and integration errors can be controlled by adaptive refinement of the respective methods. For this purpose comparable error quantities for the particular algorithms were introduced and effectively put to use.
For the implant position’s optimization, the derivative of the objective function was derived using the implicit function theorem. As the FE-discretization changes with implant position modifications big enough, a special line search had to be used to deal with the discontinuities in the objective function.
The interplay and performance of the subalgorithms was demonstrated numerically on a reduced 2D setup of a hip joint with and without the implant. Consequently the load domain and the control variable were also limited to the 2D case.
The SCIP Optimization Suite provides a collection of software packages for
mathematical optimization centered around the constraint integer programming frame-
work SCIP. This paper discusses enhancements and extensions contained in version 7.0
of the SCIP Optimization Suite. The new version features the parallel presolving library
PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op-
timization problems and can be used stand-alone or integrated into SCIP via a presolver
plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im-
provements in the Benders’ decomposition solver of SCIP, user-defined decomposition
structures can be read, which are used by the automated Benders’ decomposition solver
and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation
that is used to predict the completion of the overall solving process and potentially
trigger restarts. Moreover, substantial performance improvements of the MIP core were
achieved by new developments in presolving, primal heuristics, branching rules, conflict
analysis, and symmetry handling. Last, not least, the report presents updates to other
components and extensions of the SCIP Optimization Suite, in particular, the LP solver
SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.
This master thesis investigates the use and behaviour of a mixed finite element formulation for the simulation of garments.
The garment is modelled as an isotropic shell and is related to its mid-surface by energetic degeneration. Based on this, an energy functional is constructed, which contains the deformation and the mid-surface vector as degree of freedom. It is then shown why this problem does not correspond to a saddle point problem, but to a non-convex energy minimization.
The implementation of the energy minimization takes place with the ZIB-internal FE framework Kaskade7.4, whereby a geometric linear and different geometric non-linear problems are examined, whereby for a selected, non-linear example a comparison is made with an existing implementation on basis of Morley elements.
The further evaluations include the analysis of the quantitative and qualitative results, the used solution method, the behaviour of the system energy as well as the used CPU time.
The determination of time of death is one of the central tasks in forensic medicine. A standard method of time of death estimation elies on matching temperature measurements of the corpse with a post-mortem cooling model. In addition to widely used empirical post-mortem models, modelling based on a precise mathematical simulation of the cooling process have been gaining popularity.
The simulation based cooling models and the resulting time of death estimates dependon a large variety of parameters. These include hermal properties for different body tissue types, environmental conditions such as temperature and air flow, and the presence of clothing and coverings. In this thesis we focus on a specific arameter - the contact between corpse and underground - and investigate its influence on the time of death estimation. Resulting we aim to answer the question whether it is necessary to consider contact mechanics in the underlying mathematical cooling model.
Quantitative PA tomography of high resolution 3-D images: experimental validation in tissue phantoms
(2019)
Quantitative photoacoustic tomography aims recover the spatial distribution of absolute chromophore concentrations and their ratios from deep tissue, high-resolution images. In this study, a model-based inversion scheme based on a Monte-Carlo light transport model is experimentally validated on 3-D multispectral images of a tissue phantom acquired using an all-optical scanner with a planar detection geometry. A calibrated absorber allowed scaling of the measured data during the inversion, while an acoustic correction method was employed to compensate the effects of limited view detection. Chromophore- and fluence-dependent step sizes and Adam optimization were implemented to achieve rapid convergence. High resolution 3-D maps of absolute concentrations and their ratios were recovered with high accuracy. Potential applications of this method include quantitative functional and molecular photoacoustic tomography of deep tissue in preclinical and clinical studies.
In many applications, geodesic hierarchical models are adequate for the study of temporal observations. We employ such a model derived for manifold-valued data to Kendall's shape space. In particular, instead of the Sasaki metric, we adapt a functional-based metric, which increases the computational efficiency and does not require the implementation of the curvature tensor. We propose the corresponding variational time discretization of geodesics and apply the approach for the estimation of group trends and statistical testing of 3D shapes derived from an open access longitudinal imaging study on osteoarthritis.
Quantitative photoacoustic tomography aims to recover maps of the local concentrations of tissue chromophores from multispectral images. While model-based inversion schemes are promising approaches, major challenges to their practical implementation include the unknown fluence distribution and the scale of the inverse problem. This paper describes an inversion scheme based on a radiance Monte Carlo model and an adjoint-assisted gradient optimization that incorporates fluence-dependent step sizes and adaptive moment estimation. The inversion is shown to recover absolute chromophore concentrations, blood oxygen saturation and the Grüneisen parameter from in silico 3D phantom images for different radiance approximations. The scattering coefficient was assumed to be homogeneous and known a priori.
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders’ decomposition in a generic framework. GCG’s detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added
to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders’ framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.
In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side F:IR^n -> IR^n.
When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a non-differentiability of F. In such a situation the investigated generalized trapezoidal rule achieves a higher convergence order than the classical method. While the asymptotic behavior of the generalized method was investigated in a previous work, in the present article we develop the algorithmic structure for efficient implementation strategies
and estimate the actual computational cost of the latter.
Moreover, energy preservation of the generalized trapezoidal rule is proved for Hamiltonian systems with piecewise linear right hand side.
We consider the use of randomised forward models and log-likelihoods within the Bayesian approach to inverse problems. Such random approximations to the exact forward model or log-likelihood arise naturally when a computationally expensive model is approximated using a cheaper stochastic surrogate, as in Gaussian process emulation (kriging), or in the field of probabilistic numerical methods. We show that the Hellinger distance between the exact and approximate Bayesian posteriors is bounded by moments of the difference between the true and approximate log-likelihoods. Example applications of these stability results are given for randomised misfit models in large data applications and the probabilistic solution of ordinary differential equations.
This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.
In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side \(F:R^n \to R^n\) based on a generalization of algorithmic differentiation. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a nondifferentiability of \(F\). The advantage of the proposed generalized trapezoidal rule is threefold: Firstly, we can achieve a higher convergence order than with the classical method. Moreover, the method is energy preserving for piecewise linear Hamiltonian systems. Finally, in analogy to the classical case we derive a third order interpolation polynomial for the numerical trajectory. In the smooth case the generalized rule reduces to the classical one. Hence, it is a proper extension of the classical theory. An error estimator is given and numerical results are presented.
An automatic adaptive importance sampling algorithm for molecular dynamics in reaction coordinates
(2017)
In this article we propose an adaptive importance sampling scheme for dynamical quantities of high dimensional complex systems which are metastable. The main idea of this article is to combine a method coming from Molecular Dynamics Simulation, Metadynamics, with a theorem from stochastic analysis, Girsanov's theorem. The proposed algorithm has two advantages compared to a standard estimator of dynamic quantities: firstly, it is possible to produce estimators with a lower variance and, secondly, we can speed up the sampling. One of the main problems for building importance sampling schemes for metastable systems is to find the metastable region in order to manipulate the potential accordingly. Our method circumvents this problem by using an assimilated version of the Metadynamics algorithm and thus creates a non-equilibrium dynamics which is used to sample the equilibrium quantities.