Institutes
Refine
Year of publication
Document Type
- Doctoral Thesis (91) (remove)
Has Fulltext
- yes (91)
Is part of the Bibliography
- no (91)
Keywords
- ALICE (3)
- CBM experiment (2)
- Cellular Automaton (2)
- Computer Vision (2)
- FPGA (2)
- Machine Learning (2)
- Tracking (2)
- ALICE experiment (1)
- Ageing (1)
- Agent (1)
Institute
- Informatik und Mathematik (91) (remove)
We live in age of data ubiquity. Even the most conservative estimates predict exponential growth in produced, transmitted and stored data. Big data is used to power business analytics as well as to foster scientific discoveries. In many cases, explosion of produced data exceeds capabilities of digital storage systems. Scientific high-performance computing environments cope with this problem by utilizing large, distributed, storage systems. These complex systems can only provide a high degree of reliability and durability by means of data redundancy. The most straight-forward way of doing that is by replicating the data over different physical devices. However, more elaborate approaches, such as erasure coding, can provide similar data protection while utilizing less storage. Recently, software-defined reliability methods began to replace traditional, hardware- based, solutions. Complicated failure modes of storage system components also warrant checksums to guaranty long-term data integrity. To cope with ever increasing data volumes, flexible and efficient software implementation of error correction codes is of great importance. This thesis introduces a method for realizing a flexible Reed-Solomon erasure code using the “Just-In-Time” compilation technique. By exploiting intrinsic arithmetic redundancy in the algorithm, and by relying on modern optimizing compilers, we obtain a throughput-efficient erasure code implementation. Additionally, exploitation of data parallelism is achieved effortlessly by instructing the compiler to produce SIMD code for desired execution platform. We show results of codes implemented using SSE and AVX2 SIMD instruction sets for x86, and NEON instruction set for ARM platforms. Next, we introduce a framework for efficient vectorized RAID-Z redundancy operations of ZFS file system. Traditional, table-based Galois field multiplication algorithms are replaced with custom SSE and AVX2 parallel methods, providing significantly faster and more efficient parity operations. The implementation of this framework was made publicly available as a part of ZFS on Linux project, since version 0.7. Finally, we propose a new erasure scheme for use with existing, high performance, parallel filesystems. Described reliability middleware (ECCFS) allows definition of flexible, file-based, reliability policies, adapting to customized user needs. By utilizing the block erasure code, the ECCFS achieves optimal storage, computation, and network resource utilization, while providing a high level of reliability. The distributed nature of the middleware allows greater scalability and more efficient utilization of storage and network resources, in order to improve availability of the system.
Antimicrobial resistance became a serious threat to the worldwide public health in this century. A better understanding of the mechanisms, by which bacteria infect host cells and how the host counteracts against the invading pathogens, is an important subject of current research. Intracellular bacteria of the Salmonella genus have been frequently used as a model system for bacterial infections. Salmonella are ingested by contaminated food or water and cause gastroenteritis and typhoid fever in animals and humans. Once inside the gastrointestinal tract, Salmonella can invade intestinal epithelial cells. The host cell can fight against intracellular pathogens by a process called xenophagy. For complex systems, such as processes involved in the bacterial infection of cells, computational systems biology provides approaches to describe mathematically how these intertwined mechanisms in the cell function. Computational systems biology allows the analysis of biological systems at different levels of abstraction. Functional dependencies as well as dynamic behavior can be studied. In this thesis, we used the Petri net formalism to gain a better insight into bacterial infections and host defense mechanisms and to predict cellular behavior that can be tested experimentally. We also focused on the development of new computational methods.
In this work, the first realization of a mathematical model of the xenophagic capturing of Salmonella enterica serovar Typhimurium in epithelial cells was developed. The mathematical model expressed in the Petri net formalism was constructed in an iterative way of modeling and analyses. For the model verification, we analyzed the Petri net, including a computational performance of knockout experiments named in silico knockouts, which was established in this work. The in silico knockouts of the proposed Petri net are consistent with the published experimental perturbation studies and, thus, ensures the biological credibility of the Petri net. In silico knockouts that have not been experimentally investigated yet provide hypotheses for future investigations of the pathway.
To study the dynamic behavior of an epithelial cell infected with Salmonella enterica serovar Typhimurium, a stochastic Petri net was constructed. In experimental research, a decision like "Which incubation time is needed to infect half of the epithelial cells with Salmonella?" is based on experience or practicability. A mathematical model can help to answer these questions and improve experimental design. The stochastic Petri net models the cell at different stages of the Salmonella infection. We parameterized the model by a set of experimental data derived from different literature sources. The kinetic parameters of the stochastic Petri net determine the time evolution of the bacterial infection of a cell. The model captures the stochastic variation and heterogeneity of the intracellular Salmonella population of a single cell over time. The stochastic Petri net is a valuable tool to examine the dynamics of Salmonella infections in epithelial cells and generate valuable information for experimental design.
In the last part of this thesis, a novel theoretical method was introduced to perform knockout experiments in silico. The new concept of in silico knockouts is based on the computation of signal flows at steady state and allows the determination of knockout behavior that is comparable to experimental perturbation behavior. In this context, we established the concept of Manatee invariants and demonstrated the suitability of their application for in silico knockouts by reflecting biological dependencies from the signal initiation to the response. As a proof of principle, we applied the proposed concept of in silico knockouts to the Petri net of the xenophagic recognition of Salmonella. To enable the application of in silico knockouts for the scientific community, we implemented the novel method in the software isiKnock. isiKnock allows the automatized performance and visualization of in silico knockouts in signaling pathways expressed in the Petri net formalism. In conclusion, the knockout analysis provides a valuable method to verify computational models of signaling pathways, to detect inconsistencies in the current knowledge of a pathway, and to predict unknown pathway behavior.
In summary, the main contributions of this thesis are the Petri net of the xenophagic capturing of Salmonella enterica serovar Typhimurium in epithelial cells to study the knockout behavior and the stochastic Petri net of an epithelial cell infected with Salmonella enterica serovar Typhimurium to analyze the infection dynamics. Moreover, we established a new method for in silico knockouts, including the concept of Manatee invariants and the software isiKnock. The results of these studies are useful to a better understanding of bacterial infections and provide valuable model analysis techniques for the field of computational systems biology.
The technology of advanced driver assistance systems (ADAS) has rapidly developed in the last few decades. The current level of assistance provided by the ADAS technology significantly makes driving much safer by using the developed driver protection systems such as automatic obstacle avoidance and automatic emergency braking. With the use of ADAS, driving not only becomes safer but also easier as ADAS can take over some routine tasks from the driver, e.g. by using ADAS features of automatic lane keeping and automatic parking. With the continuous advancement of the ADAS technology, fully autonomous cars are predicted to be a reality in the near future.
One of the most important tasks in autonomous driving is to accurately localize the egocar and continuously track its position. The module which performs this task, namely odometry, can be built using different kinds of sensors: camera, LIDAR, GPS, etc. This dissertation covers the topic of visual odometry using a camera. While stereo visual odometry frameworks are widely used and dominating the KITTI odometry benchmark (Geiger, Lenz and Urtasun 2012), the accuracy and performance of monocular visual odometry is much less explored.
In this dissertation, a new monocular visual odometry framework is proposed, namely Predictive Monocular Odometry (PMO). PMO employs the prediction-and-correction mechanism in different steps of its implementation. PMO falls into the category of sparse methods. It detects and chooses keypoints from images and tracks them on the subsequence frames. The relative pose between two consecutive frames is first pre-estimated using the pitch-yaw-roll estimation based on the far-field view (Barnada, Conrad, Bradler, Ochs and Mester 2015) and the statistical motion prediction based on the vehicle motion model (Bradler, Wiegand and Mester 2015). The correction and optimization of the relative pose estimates are carried out by minimizing the photometric error of the keypoints matches using the joint epipolar tracking method (Bradler, Ochs, Fanani and Mester 2017).
The monocular absolute scale is estimated by employing a new approach to ground plane estimation. The camera height over ground is assumed to be known. The scale is first estimated using the propagation-based scale estimation. Both of the sparse matching and the dense matching of the ground features between two consecutive frames are then employed to refine the scale estimates. Additionally, street masks from a convolutional neural network (CNN) are also utilized to reject non-ground objects in the region of interest.
PMO also has a method to detect independently moving objects (IMO). This is important for visual odometry frameworks because the localization of the ego-car should be estimated only based on static objects. The IMO candidate masks are provided by a CNN. The case of crossing IMOs is handled by checking the epipolar consistency. The parallel-moving IMOs, which are epipolar conformant, are identified by checking the depth consistency against the depth maps from CNN.
In order to evaluate the accuracy of PMO, a full simulation on the KITTI odometry dataset was performed. PMO achieved the best accuracy level among the published monocular frameworks when it was submitted to the KITTI odometry benchmark in July 2017. As of January 2018, it is still one of the leading monocular methods in the KITTI odometry benchmark.
It is important to note that PMO was developed without employing random sampling consensus (RANSAC) which arguably has been long considered as one of the irreplaceable components in a visual odometry framework. In this sense, PMO introduces a new style of visual odometry framework. PMO was also developed without a multi-frame bundle adjustment step. This reflects the high potential of PMO when such multi-frame optimization scheme is also taken into account.
In the first part of the thesis we investigate Lyapunov exponents for general flat vector bundles over Riemann surfaces and we describe properties of Lyapunov exponents on special loci of the moduli space of flat vector bundles. In the second part of the thesis we show how the knowledge of Lyapunov exponent over a sporadic Teichmüller curve can be used to compute the algebraic equation of the associated universal family of curves.
A lot of software systems today need to make real-time decisions to optimize an objective of interest. This could be maximizing the click-through rate of an ad displayed on a web page or profit for an online trading software. The performance of these systems is crucial for the parties involved. Although great progress has been made over the years in understanding such online systems and devising efficient algorithms, a fine-grained analysis and problem specific solutions are often missing. This dissertation focuses on two such specific problems: bandit learning and pricing in gross-substitutes markets.
Bandit learning problems are a prominent class of sequential learning problems with several real-world applications. The classical algorithms proposed for these problems, although optimal in a theoretical sense often tend to overlook model-specific proper- ties. With this as our motivation, we explore several sequential learning models and give efficient algorithms for them. Our approaches, inspired by several classical works, incorporate the model-specific properties to derive better performance bounds.
The second part of the thesis investigates an important class of price update strategies in static markets. Specifically, we investigate the effectiveness of these strategies in terms of the total revenue generated by the sellers and the convergence of the resulting dynamics to market equilibrium. We further extend this study to a class of dynamic markets. Interestingly, in contrast to most prior works on this topic, we demonstrate that these price update dynamics may be interpreted as resulting from revenue optimizing actions of the sellers. No such interpretation was known previously. As a part of this investigation, we also study some specialized forms of no-regret dynamics and prediction techniques for supply estimation. These approaches based on learning algorithms are shown to be particularly effective in dynamic markets.
Die vorliegende Arbeit beschäftigt sich mit dem Thema Stemmatologie, d.h. primär der Rekonstruktion der Kopiergeschichte handschriftlich fixierter Dokumente. Zentrales Objekt der Stemmatologie ist das Stemma, eine visuelle Darstellung der Kopiergeschichte, welche i.d.R. graphtheoretisch als Baum bzw. gerichteter azyklischer Graph vorliegt, wobei die Knoten Textzeugen (d.s. die Textvarianten) darstellen während die Kanten für einzelne Kopierprozesse stehen. Im Mittelpunkt des Wissenschaftszweiges steht die Frage des Autorenoriginals (falls ein einziges solches existiert haben sollte) und die Frage der Rekonstruktion seines Textes. Das Stemma selbst ist ein Mittel zu diesem Hauptzweck (Cameron 1987). Der durch für manuelle Kopierprozesse kennzeichnende Abweichungen zunehmend abgewandelte Originaltext ist meist nicht direkt überliefert. Ziel der Arbeit ist es, die semi-automatische Stemmatologie umfassend zu beschreiben und durch Tools und analytische Verfahren weiterzuentwickeln. Der erste Teil der Arbeit beschreibt die Geschichte der computer-assistierten Stemmatologie inkl. ihrer klassischen Vorläufer und mündet in der Vorstellung eines einfachen Tools zur dynamischen graphischen Darstellung von Stemmata. Ein Exkurs zum philologischen Leitphänomen Lectio difficilior erörtert dessen mögliche psycholinguistische Ursachen im schnelleren lexikalischen Zugriff auf hochfrequente Lexeme. Im zweiten Teil wird daraufhin die existenziellste aller stemmatologischen Debatten, initiiert durch Joseph Bédier, mit mathematischen Argumenten auf Basis eines von Paul Maas 1937 vorgeschlagenen stemmatischen Models beleuchtet. Des Weiteren simuliert der Autor in diesem Kapitel Stemmata, um den potenziellen Einfluss der Distribution an Kopierhäufigkeiten pro Manuskript abzuschätzen.
Im nächsten Teil stellt der Autor ein eigens erstelltes Korpus in persischer Sprache vor, welches ebenso wie 3 der bekannten artifiziellen Korpora (Parzival, Notre Besoin, Heinrichi) qualitativ untersucht wird. Schließlich wird mit der Multi Modal Distance eine Methode zur Stemmagenerierung angewandt, welche auf externen Daten psycholinguistisch determinierter Buchstabenverwechslungswahrscheinlichkeiten beruht. Im letzten Teil arbeitet der Autor mit minimalen Spannbäumen zur Stemmaerzeugung, wobei eine vergleichende Studie zu 4 Methoden der Distanzmatrixgenerierung mit 4 Methoden zur Stemmaerzeugung durchgeführt, evaluiert und diskutiert wird.
The thesis deals with the analysis and modeling of point processes emerging from different experiments in neuroscience. In particular, the description and detection of different types of variability changes in point processes is of interest.
A non-stationary rate or variance of life times is a well-known problem in the description of point processes like neuronal spike trains and can affect the results of further analyses requiring stationarity. Moreover, non-stationary parameters might also contain important information themselves. The goal of the first part of the thesis is the (further) development of a technique to detect both rate and variance changes that may occur in multiple time scales separately or simultaneously. A two-step procedure building on the multiple filter test (Messer et al., 2014) is used that first tests the null hypothesis of rate homogeneity allowing for an inhomogeneous variance and that estimates change points in the rate if the null hypothesis is rejected. In the second step, the null hypothesis of variance homogeneity is tested and variance change points are estimated. Rate change points are used as input. The main idea is the comparison of estimated variances in adjacent windows of different sizes sliding over the process. To determine the rejection threshold functionals of the Brownian motion are identified as limit processes under the null of variance homogeneity. The non-parametric procedure is not restricted to the case of at most one change point. It is shown in simulation studies that the corresponding test keeps the asymptotic significance level for a wide range of parameters and that the test power is remarkable. The practical applicability of the procedure is underlined by the analysis of neuronal spike trains.
Point processes resulting from experiments on bistable perception are analyzed in the second part of the thesis. Visual illusions allowing for than more possible perception lead to unpredictable changes of perception. In the thesis data from (Schmack et al., 2015) are used. A rotating sphere with switching perceived rotation direction was presented to the participants of the study. The stimulus was presented continuously and intermittently, i.e., with short periods of „blank display“ between the presentation periods. There are remarkable differences in the response patterns between the two types of presentation. During continuous presentation the distribution of dominance times, i.e., the intervals of constant perception, is a right-skewed and unimodal distribution with a mean of about five seconds. In contrast, during intermittent presentation one observes very long, stable dominance times of more than one minute interchanging with very short, unstable dominance times of less than five seconds, i.e., an increase of variability.
The main goal of the second part is to develop a model for the response patterns to bistable perception that builds a bridge between empirical data analysis and mechanistic modeling. Thus, the model should be able to describe both the response patterns to continuous presentation and to intermittent presentation. Moreover, the model should be fittable to typically short experimental data, and the model should allow for neuronal correlates. Current approaches often use detailed assumptions and large parameter sets, which complicate parameter estimation.
First, a Hidden Markov Model is applied. Second, to allow for neuronal correlates, a Hierarchical Brownian Model (HBM) is introduced, where perception is modeled by the competition of two neuronal populations. The activity difference between these two populations is described by a Brownian motion with drift fluctuating between two borders, where each first hitting time causes a perceptual change. To model the response patterns to intermittent presentation a second layer with competing neuronal populations (coding a stable and an unstable state) is assumed. Again, the data are described very well, and the hypothesis that the relative time in the stable state is identical in a group of patients with schizophrenia and a control group is rejected. To sum up, the HBM intends to link empirical data analysis and mechanistic modeling and provides interesting new hypotheses on potential neuronal mechanisms of cognitive phenomena.
Diese Arbeit beschäftigt sich mit inversen Problemen für partielle Differentialgleichungen. Moderne Lösungsverfahren solcher inversen Probleme müssen die zugehörige partielle Differentialgleichung (PDGL) oft sehr häufig lösen. Mit Hinblick auf die Rechenzeit solcher Verfahren stellt das häufige Lösen der PDGL den Hauptanteil der benötigten Rechenzeit dar. Daraus resultiert die Grundidee dieser Arbeit: es sollen Lösungsverfahren von inversen Problemen beschleunigt werden, indem die für die Vorwärtslösung benötigte Rechenzeit verringert wird. Genauer gesagt soll anstatt der Vorwärtslösung eine Approximation an diese, welche kostengünstig zu berechnen ist, verwendet werden. Für die Bestimmung einer kostengünstigen Annäherung an die Vorwärtslösung wird die Reduzierte Basis Methode, eine Modellreduktionstechnik, verwendet.
Das Ziel der klassischen Reduzierten Basis Methode ist es einen globalen Reduzierte Basis Raum (RB-Raum) zu konstruieren. Dabei handelt es sich um einen niedrigdimensionalen Teilraum des Lösungsraumes der PDGL, welcher für jeden Parameter aus dem Parameterraum eine gute Näherung der PDGL-Lösung liefert. Eine beispielhafte Methode zur Konstruktion eines solchen Raumes ist es, geschickt Parameter auszuwählen und die dazu gehörigen PDGL-Lösungen als Basisvektoren des RB-Raumes zu verwenden. Die orthogonale Projektion der PDGL auf diesen RB-Raum liefert die entsprechenden Reduzierte Basis Lösungen. Das Besondere in dieser Arbeit ist, dass die betrachteten PDGLn einen sehr hochdimensionalen und unbeschränkten Parameterraum besitzen, und es ist bekannt, dass dies für die Reduzierte Basis Methode eine immense Schwierigkeit darstellt.
In Kapitel 1 wird ein schlechtgestelltes inverses Modellproblem, die Rekonstruktion der Wärmeleitfähigkeit eines Gegenstandes aus der Messung der Temperatur desselben, eingeführt und das nichtlineare Landweber-Verfahren als iteratives Regularisierungsverfahren zur Lösung dieses inversen Problems vorgestellt. Die Grundlagen der Reduzierten Basis Methode werden dargelegt und es wird erläutert, warum die klassische Variante der Methode in diesem Kontext der Bildrekonstruktion versagt. Daraufhin wird der neuartig Ansatz, ein adaptiver Reduzierte Basis Ansatz, entwickelt. Die folgenden Schritte bilden die Grundlage dieses adaptiven Reduzierte Basis Ansatzes:
1. Sei ein RB-Raum gegeben, so projiziere den Lösungsalgorithmus des inversen Problems auf diesen RB-Raum.
2. Generiere mit Hilfe dieses projizierten Verfahrens neue Iterierte bis entweder eine Iterierte das inverse Problem löst oder bis der RB-Raum erweitert werden muss.
3. Im ersten Fall wird das Verfahren beendet, im zweiten Fall wird die zur aktuellen Iterierten gehörige Vorwärtslösung verwendet um den RB-Raum zu verbessern. Danach wird mit dem ersten Schritt fortgefahren.
Es wird also nach und nach ein lokal approximierender RB-Raum konstruiert, indem Parameter für neue Basisvektoren mittels einer projizierten Variante des Lösungsalgorithmus des inversen Problems gefunden werden. Das neuartige Reduzierte Basis Landweber-Verfahren ist das Hauptresultat von Kapitel 1, wobei das Verfahren ausführlich numerisch untersucht und mit dem ursprünglichen Landweber-Verfahren verglichen wird.
In Kapitel 2 dieser Arbeit soll der zuvor entwickelte adaptive Reduzierte Basis Ansatz auf ein komplexes und praxisrelevantes Problem angewandt werden. Insbesondere soll die dadurch entstehende neue Methode mit Hinblick auf Konvergenz theoretisch ausführlich untersucht werden. Daher widmet sich der zweite Teil dieser Arbeit dem Problem der Magnet Resonanz Elektrischen Impedanztomographie (MREIT).
Bei der MREIT handelt es sich um ein Bildgebungsverfahren, welches während der letzten drei Jahrzehnte entwickelt wurde. Dabei wird ein Gegenstand, an welchen Elektroden angeheftet sind, in einen Kernspintomographen gelegt und es ist das Ziel des Verfahrens die elektrische Leitfähigkeit des Gegenstandes zu bestimmen. Die dazu benötigten Daten werden folgendermaßen gewonnen: indem Strom an einer der Elektroden angelegt wird, wird ein Stromfluss erzeugt, welcher wiederum eine Änderung der Magnetflussdichte induziert. Diese kann mit Hilfe des Kernspintomographen gemessen werden, wodurch man einen vollen Satz innerer Daten zur Hand hat, sodass hoch aufgelöste Bilder der elektrischen Leitfähigkeit des Gegenstandes rekonstruiert werden können.
Als Lösungsalgorithmus für dieses praxisrelevante Problem wird der bereits bekannte Harmonische Bz Algorithmus vorgestellt. Das Problem und der Algorithmus werden mit Hinblick auf Konvergenz des Verfahrens untersucht und ein Konvergenzresultat, welches die bestehende Konvergenztheorie hin zu einem approximativen Harmonischen Bz Algorithmus erweitert, wird bewiesen. Dabei hängt das Resultat nicht davon ab welche Art von Approximation an die Vorwärtslösung der entsprechenden PDGL im approximativen Harmonischen Bz Algorithmus verwendet wird solange diese einer Regularitäts- und einer Qualitätsbedingung genügt. Damit folgt das zweite Hauptresultat dieser Arbeit: die numerische Konvergenz des Harmonischen Bz Algorithmus. Es soll dabei hervorgehoben werden, dass Konvergenzresultate im Bereich der inversen Probleme (sofern es sie gibt) meistens die Kenntnis der exakten Vorwärtslösung annehmen, sodass keine numerische Konvergenz des zugehörigen Verfahrens folgt (in einer numerischen Implementation wird stets eine Approximation an die Vorwärtslösung verwendet). Somit ist dieses Konvergenzresultat ein Schritt hin zur numerischen Konvergenz anderer Lösungsverfahren von inversen Problemen.
Da das theoretische Resultat von der Art der Approximation nicht abhängt, erhält man ebenfalls die Konvergenz des neuartigen Reduzierte Basis Harmonischen Bz Algorithmus, welcher die Kombination des in Kapitel 1 entwickelten adaptiven Reduzierte Basis Ansatzes und des Harmonischen Bz Algorithmus ist. In einer kurzen numerischen Untersuchung wird festgestellt, dass dieser Reduzierte Basis Harmonische Bz Algorithmus schneller als der Harmonische Bz Algorithmus ist, wobei die Qualität der Rekonstruktion gleichbleibend ist. Somit funktioniert der entwickelte adaptive Reduzierte Basis Ansatz auch angewandt auf dieses komplexe praxisrelevante inverse Problem der MREIT.
The results of this thesis lie in the area of convex algebraic geometry, which is the intersection of real algebraic geometry, convex geometry, and optimization.
We study sums of nonnegative circuit polynomials (SONC) and their related cone, both geometrically and in application to polynomial optimization. SONC polynomials are certain sparse polynomials having a special structure in terms of their Newton polytopes and supports, and serve as a certificate of nonnegativity for real polynomials, which is independent of sums of squares.
The first part of this thesis is dedicated to the convex geometric study of the SONC cone. As main results we show that the SONC cone is full-dimensional in the cone of nonnegative polynomials, we exactly determine the number of zeros of a nonnegative circuit polynomial, and we give a complete and explicit characterization of the number of zeros of SONC polynomials and forms. Moreover, we provide a first approach to the study of the exposed faces of the SONC cone and their dimensions.
In the second part of the thesis we use SONC polynomials to tackle constrained polynomial optimization problems (CPOPs).
As a first step, we derive a lower bound for the optimal value of CPOP based on SONC polynomials by using a single convex optimization program, which is a geometric program (GP) under certain assumptions. GPs are a special type of convex optimization problems and can be solved in polynomial time. We test the new method experimentally and provide examples comparing our new SONC/GP approach with Lasserre's relaxation, a common approach for tackling CPOPs, which approximates nonnegative polynomials via sums of squares and semidefinite programming (SDP). The new approach comes with the benefit that in practice GPs can be solved significantly faster than SDPs. Furthermore, increasing the degree of a given problem has almost no effect on the runtime of the new program, which is in sharp contrast to SDPs.
As a second step, we establish a hierarchy of efficiently computable lower bounds converging to the optimal value of CPOP based on SONC polynomials. For a given degree each bound is computable by a relative entropy program. This program is also a convex optimization program, which is more general than a geometric program, but still efficiently solvable via interior point methods.