A torsion free abelian group of finite rank is called almost completely decomposable if it has a completely decomposable subgroup of finite index. A p-local, p-reduced almost completely decomposable group of type (1,2) is briefly called a (1,2)-group. Almost completely decomposable groups can be represented by matrices over the ring Z/hZ, where h is the exponent of the regulator quotient. This particular choice of representation allows for a better investigation of the decomposability of the group. Arnold and Dugas showed in several of their works that (1,2)-groups with regulator quotient of exponent at least p^7 allow infinitely many isomorphism types of indecomposable groups. It is not known if the exponent 7 is minimal. In this dissertation, this problem is addressed. / Eine fast vollständig zerlegbare Gruppe ist eine torsionsfreie abelsche Gruppe endlichen Ranges,die eine vollständig zerlegbare Untergruppe von endlichem Index enthält. Fast vollständig zerlegbare Gruppen gestatten eine Darstellung durch Matrizen über dem Ring Z/hZ, wobei h der Exponent des Regulatorquotienten ist. Auf dieser Matrixdarstellung aufsetzend kann man das Zerlegungsverhalten von Gruppen untersuchen. Arnold und Dugas haben in mehreren Arbeiten gezeigt, dass es unendlich viele Isomorphietypen unzerlegbarer fast vollständig zerlegbarer Gruppen gibt,sobald der Exponent des Regulatorquotienten grösser gleich sieben ist. Allerdings ist unbekannt, ob sieben der kleinste Exponent mit dieser Eigenschaft ist. Wir untersuchen dieses Problem für p-lokale fast vollständig zerlegbare Gruppen vom Typ (1,2).

No abstract available

The success of diagnostic knowledge systems has been proved over the last decades. Nowadays, intelligent systems are embedded in machines within various domains or are used in interaction with a user for solving problems. However, although such systems have been applied very successfully the development of a knowledge system is still a critical issue. Similarly to projects dealing with customized software at a highly innovative level a precise specification often cannot be given in advance. Moreover, necessary requirements of the knowledge system can be defined not until the project has been started or are changing during the development phase. Many success factors depend on the feedback given by users, which can be provided if preliminary demonstrations of the system can be delivered as soon as possible, e.g., for interactive systems validation the duration of the system dialog. This thesis motivates that classical, document-centered approaches cannot be applied in such a setting. We cope with this problem by introducing an agile process model for developing diagnostic knowledge systems, mainly inspired by the ideas of the eXtreme Programming methodology known in software engineering. The main aim of the presented work is to simplify the engineering process for domain specialists formalizing the knowledge themselves. The engineering process is supported at a primary level by the introduction of knowledge containers, that define an organized view of knowledge contained in the system. Consequently, we provide structured procedures as a recommendation for filling these containers. The actual knowledge is acquired and formalized right from start, and the integration to runnable knowledge systems is done continuously in order to allow for an early and concrete feedback. In contrast to related prototyping approaches the validity and maintainability of the collected knowledge is ensured by appropriate test methods and restructuring techniques, respectively. Additionally, we propose learning methods to support the knowledge acquisition process sufficiently. The practical significance of the process model strongly depends on the available tools supporting the application of the process model. We present the system family d3web and especially the system d3web.KnowME as a highly integrated development environment for diagnostic knowledge systems. The process model and its activities, respectively, are evaluated in two real life applications: in a medical and in an environmental project the benefits of the agile development are clearly demonstrated. / Wissensbasierte Diagnosesysteme konnten in den letzten Jahrzehnten sehr erfolgreich eingesetzt werden. Intelligente Systeme sind heute in den verschiedensten Domainen zu finden, werden in komplexe Maschinen eingebettet oder interaktiv im Dialog mit dem Benutzer verwendet. Trotz aller Erfolge ist die Entwicklung eines Wissenssystems immer noch eine komplexe Aufgabe. Dies ist darin begründet, dass ähnlich zu der Erstellung von Individual-Software mit einem hohen innovativen Grad eine präzise Spezifikation zu Anfand des Projekt häufig nicht gegeben werden kann. Vielmehr können notwendige Faktoren, welche den Erfolg des Systems maßgeblich bestimmen, nicht vor der Entwicklung identifiziert werden oder sind Änderungen während der Entwicklungsphase unterworfen. Viele Einflussfaktoren können hierbei nur in Rückkopplung mit dem Benutzer abgewogen werden, welches durch vorläufige Versionen des Systems in frühen Stadien ermöglicht werden kann, z.B. bei interaktiven Systemen durch eine Validierung des Dialoges durch den Benutzer. Diese Arbeit stellt heraus, dass klassische, dokument-zentrierte Ansätze in einem solchen Umfeld nicht anwendbar sind, und schlägt ein agiles Vorgehensmodell zur Entwicklung von wissensbasierten Diagnosesystemen als Lösung vor. Das agile Vorgehensmodell wurde wesentlich durch Ideen des im Software Engineering bekannten eXtreme Programming beeinflusst. Als wichtigstes Ziel dieser Arbeit wird die Vereinfachung des Entwicklungsprozesses für den Fachexperten verfolgt, der im Idealfall das benötigte Wissen selbst formalisiert. Dabei wird der Entwicklungsprozess auf einer übergeordneten Ebene durch die Einführung von Wissenscontainern unterstützt, welche eine organisierte Übersicht auf das im System enthaltene Wissen bieten. Weiterhin werden strukturierte Vorgehensweisen für das Füllen der jeweiligen Container empfohlen. Das tatsächliche Wissen wird von Beginn des Projekts an erfasst und formalisiert; eine kontinuierliche Integration von neuen Wissensinhalten in ein lauffähiges System sorgt für eine frühe und konkrete Rückkopplung mit dem Benutzer. Im Gegensatz zu den verwandten Prototyping Ansätzen wird die Validität und Wartbarkeit des erfassten Wissens durch geeignete Test- und Restrukturierungsmethoden sichergestellt. Zusätzlich werden angepasste Lernmethoden diskutiert, welche den Wissensakquisitionsprozess in vielen Bereichen ergänzen können. Die praktische Bedeutung des Vorgehensmodells ist stark mit der Verfügbarkeit von Werkzeugen verknüpft, welche den Fachexperten bei der Entwicklung direkt unterstützen können. Es wird daher die Systemfamilie d3web und im Speziellen die integrierte Entwicklungsumgebung d3web.KnowME vorgestellt. Das Vorgehensmodell und seine Aktivitäten werden in zwei Praxis-Anwendungen, einem medizinischen und einem geo-ökologischen Projekt, evaluiert.

Mathematische Programme mit Gleichgewichtsrestriktionen (oder Komplementaritätsbedingungen), kurz MPECs, sind als äußerst schwere Optimierungsprobleme bekannt. Lokale Minima oder geeignete stationäre Punkte zu finden, ist ein nichttriviales Problem. Diese Arbeit beschreibt, wie man dennoch die spezielle Struktur von MPECs ausnutzen kann und mittels eines Branch-and-Bound-Verfahrens ein globales Minimum von Linearen Programmen mit Gleichgewichtsrestriktionen, kurz LPECs, bekommt. Des Weiteren wird dieser Branch-and-Bound-Algorithmus innerhalb eines Filter-SQPEC-Verfahrens genutzt, um allgemeine MPECs zu lösen. Für das Filter-SQPEC Verfahren wird ein globaler Konvergenzsatz bewiesen. Außerdem werden für beide Verfahren numerische Resultate angegeben. / Mathematical programs with equilibrium (or complementarity) constraints, MPECs for short, are known to be very difficult optimization problems. Finding local minima or suitable stationary points is a highly nontrivial task. On the other hand, taking into account the special structure of MPECs, this thesis describes a branch-and-bound-type algorithm for the computation of a global minimum of linear programs with equilibrium constraints, LPECs for short. Furthermore this branch-and-bound-type algorithm is used within a filter-SQPEC algorithm to solve the general MPEC. For the filter-SQPEC algorithm, a global convergence theorem is proven. Numerical results are presented for both methods.

In dieser Arbeit werden Algorithmen zur Lösung von linearen semidefiniten Programmen beschrieben. Unter einer geeigneten Regularitätsvoraussetzung ist ein semidefinites Programm äquivalent zu seinen Optimalitätsbedingungen. Die Optimalitätsbedingungen bzw. die Zentralen-Pfad-Bedingungen überführen wir zunächst durch matrixwertige NCP-Funktionen in ein nichtlineares Gleichungssystem. Dieses nichtlineare und teilweise nicht differenzierbare Gleichungssystem lösen wir dann mit einem Newton-ähnlichen Verfahren. Durch die Umformulierung in ein nichtlineares Gleichungssystem muss während der Iteration nicht mehr explizit die positive (Semi-)Definitheit der beteiligten Matrizen beachtet werden. Weiter wird gezeigt, dass dieser Ansatz im Gegensatz zu Inneren-Punkte-Methoden sofort symmetrische Suchrichtungen erzeugt. Um globale Konvergenz zu erhalten, werden verschiedene Globalisierungsstrategien (Schrittweitenbestimmung, Trust-Region-Ansatz) untersucht. Für das betrachtete Prädiktor-Korrektor-Verfahren und das Trust-Region-Verfahren wird lokal superlineare Konvergenz unter strikter Komplementarität und Nichtdegeneriertheit gezeigt. Die theoretische Untersuchung eines nichtglatten Newton-Verfahrens liefert ein lokal quadratisches Konvergenzverhalten ohne strikte Komplementarität, wenn die Nichtdegeneriertheitsvoraussetzung geeignet modifiziert wird. / In this thesis we consider algorithms to compute a solution of linear semidefinite programs. Under a suitable regularity condition a semidefinite program is equivalent to its optimality conditions. These optimality conditions, or central-path-conditions, are reformulated as a nonlinear system of equations via matrix-valued NCP-functions. This nonlinear and partly nonsmooth system of equations is solved with a Newton-type method. Because of the reformulation as a nonlinear system of equations, we do not need the iterates to be positive (semi-)definite. Moreover, this reformulation automatically computes symmetric search directions, in contrast to interior point methods. To obtain global convergence, different globalizations (line search, trust-region) are considered. For the predictor-corrector method and the trust-region-method global and local superlinear convergence is shown under strikt complementarity and nondegeneracy. The theoretical investigation of a nonsmooth version of Newton's methods yields locally quadratic convergence without strict complementarity if the nondegeneracy conditon is modified in a suitable way.

An exhaustive discussion of constraint qualifications (CQ) and stationarity concepts for mathematical programs with equilibrium constraints (MPEC) is presented. It is demonstrated that all but the weakest CQ, Guignard CQ, are too strong for a discussion of MPECs. Therefore, MPEC variants of all the standard CQs are introduced and investigated. A strongly stationary point (which is simply a KKT-point) is seen to be a necessary first order optimality condition only under the strongest CQs, MPEC-LICQ, MPEC-SMFCQ and Guignard CQ. Therefore a whole set of KKT-type conditions is investigated. A simple approach is given to acquire A-stationarity to be a necessary first order condition under MPEC-Guiganrd CQ. Finally, a whole chapter is devoted to investigating M-stationary, among the strongest stationarity concepts, second only to strong stationarity. It is shown to be a necessary first order condition under MPEC-Guignard CQ, the weakest known CQ for MPECs.

The investigation of multivariate generalized Pareto distributions (GPDs) in the framework of extreme value theory has begun only lately. Recent results show that they can, as in the univariate case, be used in Peaks over Threshold approaches. In this manuscript we investigate the definition of GPDs from Section 5.1 of Falk et al. (2004), which does not differ in the area of interest from those of other authors. We first show some theoretical properties and introduce important examples of GPDs. For the further investigation of these distributions simulation methods are an important part. We describe several methods of simulating GPDs, beginning with an efficient method for the logistic GPD. This algorithm is based on the Shi transformation, which was introduced by Shi (1995) and was used in Stephenson (2003) for the simulation of multivariate extreme value distributions of logistic type. We also present nonparametric and parametric estimation methods in GPD models. We estimate the angular density nonparametrically in arbitrary dimension, where the bivariate case turns out to be a special case. The asymptotic normality of the corresponding estimators is shown. Also in the parametric estimations, which are mainly based on maximum likelihood methods, the asymptotic normality of the estimators is shown under certain regularity conditions. Finally the methods are applied to a real hydrological data set containing water discharges of the rivers Altmühl and Danube in southern Bavaria. / Die Untersuchung der multivariaten verallgemeinerten Pareto-Verteilungen (GPDs) im Rahmen der Extremwerttheorie hat erst kürzlich begonnen. Neueste Ergebnisse zeigen, dass diese wie im univariaten Fall bei Peaks over Threshold-Ansätzen angewendet werden können. In dieser Arbeit verwenden wir die Definition einer GPD aus Abschnitt 5.1 von Falk et al. (2004), die sich im interessierenden Bereich nicht von der anderer Autoren unterscheidet. Wir zeigen zuerst einige theoretische Eigenschaften und stellen wichtige Beispiele von GPDs vor. Zur weiteren Untersuchung dieser Verteilungen sind Simulationen unerläßlich. Wir stellen mehrere Methoden zur Simulation von GPDs vor, beginnend mit einer effizienten Methode für die logistische GPD. Der entsprechende Algorithmus basiert auf der Shi-Transformation, die von Shi (1995) eingeführt und von Stephenson (2003) verwendet wurde, um logistische multivariate Extremwertverteilungen zu simulieren. Wir führen auch nicht-parametrische und parametrische Schätzverfahren in GPD-Modellen ein. Wir schätzen die Angular Density in beliebiger Dimension, wobei sich der bivariate Fall als ein besonderer herausstellt. Die asymptotische Normalität der entsprechenden Schätzer wird gezeigt. Ebenso zeigen wir für die parametrischen Schätzungen, die hauptsächlich Maximum-Likelihood-Methoden verwenden, die asymptotische Normalität unter geeigneten Regularitätsbedingungen Zum Schluß werden die Methoden auf einen realen hydrologischen Datensatz, bestehend aus Abflussraten der Flüsse Altmühl und Donau in Südbayern, angewendet.

This thesis is concerned with numerical methods for solving nonlinear and mixed complementarity problems. Such problems arise from a variety of applications such as equilibria models of economics, contact and structural mechanics problems, obstacle problems, discrete-time optimal control problems etc. In this thesis we present a new formulation of nonlinear and mixed complementarity problems based on the Fischer-Burmeister function approach. Unlike traditional reformulations, our approach leads to an over-determined system of nonlinear equations. This has the advantage that certain drawbacks of the Fischer-Burmeister approach are avoided. Among other favorable properties of the new formulation, the natural merit function turns out to be differentiable. To solve the arising over-determined system we use a nonsmooth damped Levenberg-Marquardt-type method and investigate its convergence properties. Under mild assumptions, it can be shown that the global and local fast convergence results are similar to some of the better equation-based method. Moreover, the new method turns out to be significantly more robust than the corresponding equation-based method. For the case of large complementarity problems, however, the performance of this method suffers from the need for solving the arising linear least squares problem exactly at each iteration. Therefore, we suggest a modified version which allows inexact solutions of the least squares problems by using an appropriate iterative solver. Under certain assumptions, the favorable convergence properties of the original method are preserved. As an alternative method for mixed complementarity problems, we consider a box constrained least squares formulation along with a projected Levenberg-Marquardt-type method. To globalize this method, trust region strategies are proposed. Several ingredients are used to improve this approach: affine scaling matrices and multi-dimensional filter techniques. Global convergence results as well as local superlinear/quadratic convergence are shown under appropriate assumptions. Combining the advantages of the new methods, a new software for solving mixed complementarity problems is presented. / Diese Dissertation behandelt numerische Verfahren zur Lösung nichtlinearer und gemischer Komplementaritätsprobleme. Solche Probleme ergeben sich aus einer Vielzahl von Anwendungen wie z.B. ökonomische Gleichgewichtmodelle, Kontakt- und Strukturprobleme der Mechanik, Hindernisprobleme, Probleme der optimalen Steuerung usw.. Als erstes wird eine neue Umformulierung der nichtlinearen und gemischen Komplementaritätsproblemen vorgestellt, die auf der Fischer-Burmeister Funktion basiert. Im Gegensatz zu bekannten Umformulierungen führt unsere zu einem überbestimmten nichtlinearen Gleichungssystem. Dadurch werden bestimmte Nachteile der Fischer-Burmeister Umformulierung vermieden. Eine vorteilhafte Eigenschaft der neuen Formulierung ist die Differenzierbarkeit der Straffunktion. Um das resultierende überbestimmte Gleichungsystem zu lösen benutzen wir eine nichtglattes gedämpftes Levenberg-Marquardt Verfahren und untersuchen dessen Konvergenzeigenschaften. Unter milden Annahmen kann gezeigt werden, dass die globalen und lokalen schnellen Konvergenzresultate der etwas besseren Methoden erhalten bleiben. Außerdem scheint die neue Methode deutlich robuster zu sein als andere Methoden die ebenfalls auf einer Umformulierung der Komplementaritätsprobleme als Gleichungsystem beruhen. Im Falle grosser Komplementaritätsprobleme leidet die Leistung dieser Methode jedoch, da in jedem Iterationsschritt die exakte Lösung eines grossdimensionalem linearem Ausgleichsproblem anfällt. Folglich schlagen wir eine geänderte Version vor, die inexakte Lösungen dieser Ausgleichsprobleme zulässt, durch Verwendung eines iterativen Lösers. Unter bestimmten Annahmen bleiben die vorteilhaften Konvergenzeigenschaften der ursprünglichen Methode erhalten. Als alternative Methode für gemischte Komplementaritätprobleme betrachten wir eine Box-restringierte Umformulierung zusammen mit einem projizierten Levenberg-Marquardt Verfahren. Zu Globalisierungszwecken wird eine Trust-Region Strategie vorgeschlagen. Skalierungmatrizen und mehrdimensionale Filtertechniken werden benutzt, um das Verfahren zu verbessern. Globale Konvergenz, sowie lokal superlineare/quadratische Konvergenz kann unter adäquaten Voraussetzungen gezeigt werden. Schließlich wird eine Software zur Lösung der gemischten Komplementaritätsprobleme, welche die Vorteile der neuen Methoden kombiniert.

The dissertation thesis studies the complexity of membership problems. Generally, membership problems consider the question whether a given object belongs to a set. Object and set are part of the input. The thesis studies the complexity of membership problems for two special kinds of sets. The first problem class asks whether a given natural number belongs to a set of natural numbers. The set of natural numbers is defined via finite recurrent systems: sets are built by iterative application of operations, like union, intersection, complementation and arithmetical operations, to already defined sets. This general problem implies further problems by restricting the set of used operations. The thesis contains completeness results for well-known complexity classes as well as undecidability results for these problems. The second problem class asks whether a given graph is a minimal triangulation of another graph. A graph is a triangulation of another graph, if it is a chordal spanning supergraph of the second graph. If no proper supergraph of the first graph is a triangulation of the second graph, the first graph is a minimal triangulation of the second graph. The complexity of the membership problem for minimal triangulations of several graph classes is investigated. Restricted variants are solved by linear-time algorithms. These algorithms rely on appropriate characterisations of minimal triangulations. / Die Dissertation beschäftigt sich mit der Komplexität von Enthaltenseinproblemen. Allgemein gesprochen, interessieren sich Enthaltenseinprobleme für die Frage, ob ein gegebenes Objekt zu einer Menge gehört. Sowohl Objekt als auch Menge sind Teil der Eingabe. Die Arbeit untersucht die Komplexität dieser Fragestellung für zwei konkrete Mengenklassen. Zum ersten soll entschieden werden, ob eine natürliche Zahl zu einer Menge natürlicher Zahlen gehört. Entscheidend für die Komplexität dieses Problems ist die Darstellung der Menge natürlicher Zahlen. Es werden rekurrente Systeme verwendet, die Mengen natürlicher Zahlen durch iterierte Anwendung einfacher Operationen, wie die drei Mengenoperationen Vereinigung, Durchschnitt, Komplementbildung und arithmetische Operationen, auf bereits konstruierte Mengen definieren. Beschränkt man die Menge verwendeter Operationen, ergibt sich eine Vielzahl von Problemen, deren Komplexitäten bestimmt werden. Es werden Vollständigkeitsresultate für bekannte Komplexitätsklassen wie auch Unentscheidbarkeit gezeigt. Zum zweiten soll entschieden werden, ob ein Graph eine minimale Triangulation eines anderen Graphen ist. Ein Graph ist Triangulation eines anderen Graphen, wenn er ein chordaler aufspannender Obergraph des zweiten Graphen ist. Ist kein echter Obergraph des ersten Graphen eine Triangulation des zweiten Graphen, so ist der erste Graph eine minimale Triangulation des zweiten Graphen. Ein Graph kann mehrere minimale Triangulationen besitzen. Untersucht wird die Komplexität des Enthaltenseinproblems für minimale Triangulationen für verschiedene Graphenklassen, und es werden Linearzeitalgorithmen zur Lösung einer eingeschränkten Variante des jeweiligen Problems angegeben. Die Algorithmen basieren alle auf geeigneten Charakterisierungen minimaler Triangulationen.

In this thesis affine-scaling-methods for two different types of mathematical problems are considered. The first type of problems are nonlinear optimization problems subject to bound constraints. A class of new affine-scaling Newton-type methods is introduced. The methods are shown to be locally quadratically convergent without assuming strict complementarity of the solution. The new methods differ from previous ones mainly in the choice of the scaling matrix. The second type of problems are semismooth system of equations with bound constraints. A new affine-scaling trust-region method for these problems is developed. The method is shown to have strong global and local convergence properties under suitable assumptions. Numerical results are presented for a number of problems arising from different areas. / In dieser Arbeit werden affine Skalierungsverfahren fuer zwei verschiedene mathematische Problemstellungen untersucht. Der erste Problemtyp sind nichtlineare Optimierungsaufgaben mit Box-Restriktionen. Hierfuer wird eine neue Klasse von affinen Skalierungsverfahren eingefuehrt. Fuer diese Verfahren kann lokale quadratische Konvergenz ohne eine strikte Komplementaritaetsannahme bewiesen werde. Die neuen Methoden unterscheiden sich von den bisherigen durch die Wahl der Skalierungsmatrix. Probleme vom zweiten Typ sind semismoothe nichtlineare Gleichungssysteme mit Box-Restriktionen. Ein neues affine Skalierungs Trust-Region-Verfahren fuer diese Probleme wird vorgestellt. Das Verfahren besitzt starke globale und lokale Konvergenzeigenschaften unter ueblichen Voraussetzungen. Fuer eine Vielzahl von Problemstellungen werden numerische Ergebnisse beschrieben.