There are many iterative techniques to find a root or zero of a given function. For any iterative technique, it is often of interest to know which initial seeds lead to which roots. When the iterative technique used is Newton’s Method, this is known as Cayley’s Problem. In this thesis, I investigate two extensions of Cayley’s Problem. In particular, I study generalizations of Newton’s Method, in both C and R2, and the associated fractal structures that arise from using more sophisticated numerical approximation techniques.

Some well-studied infinite-state stochastic models give rise to systems of nonlinear equations. These systems of equations have solutions that are probabilities, generally probabilities of termination in the model. We are interested in finding efficient, preferably polynomial time, algorithms for calculating probabilities associated with these models. The chief tool we use to solve systems of polynomial equations will be Newton’s method as suggested by [EY09]. The main contribution of this thesis is to the analysis of this and related algorithms. We give polynomial-time algorithms for calculating probabilities for broad classes of models for which none were known before. Stochastic models that give rise to such systems of equations include such classic and heavily-studied models as Multi-type Branching Processes, Stochastic Context- Free Grammars(SCFGs) and Quasi Birth-Death Processes. We also consider models that give rise to infinite-state Markov Decision Processes (MDPs) by giving algorithms for approximating optimal probabilities and finding policies that give probabilities close to the optimal probability, in several classes of infinite-state MDPs. Our algorithms for analysing infinite-state MDPs rely on a non-trivial generalization of Newton’s method that works for the max/min polynomial systems that arise as Bellman optimality equations in these models. For SCFGs, which are used in statistical natural language processing, in addition to approximating termination probabilities, we analyse algorithms for approximating the probability that a grammar produces a given string, or produces a string in a given regular language. In most cases, we show that we can calculate an approximation to the relevant probability in time polynomial in the size of the model and the number of bits of desired precision. We also consider more general systems of monotone polynomial equations. For such systems we cannot give a polynomial-time algorithm, which pre-existing hardness results render unlikely, but we can still give an algorithm with a complexity upper bound which is exponential only in some parameters that are likely to be bounded for the monotone polynomial equations that arise for many interesting stochastic models.

We introduce basic ideas of a nonsmooth Newton’s method and its application in solving semidefinite optimization (SDO) problems. In particular, the method can be used to solve both linear and nonlinear semidefinite complementarity problems. We also survey recent theoretical results in matrix functions and stability of SDO that are stemed from the research on the matrix form of the nonsmooth Newton’s method. / Singapore-MIT Alliance (SMA)

The micro-electromechanical systems (MEMS) industry has grown incredibly fast over the past few years, due to the irresistible character and properties of MEMS. MEMS devices have been widely used in various fields such as aerospace, microelectronics, and the automobile industry. Increasing prominence is given to the development and research of MEMS; this is largely driven by the market requirements. Multi-physics coupled fields are often present in MEMS. This makes the modelling and analysis o such devices difficult and sometimes costly. The coupling between electrostatic and mechanical fields in MEMS is one of the most common and fundamental phenomena in MEMS; it is this configuration that is studied in this thesis. The following issues are addressed: 1. Due to the complexity in the structural geometry, as well as the difficulty to analyze the behaviour in the presence of coupled fields, simple analytical solutions are normally not available for MEMS. The finite element method (FEM) is therefore used to model electrostaticmechanical coupled MEMS. In this thesis, this avenue is followed. 2. In order to capture the configuration of the system accurately, with relatively little computational effort, a geometric non-linear mixed assumed stress element is developed and used in the FE analyses. It is shown that the developed geometrically non-linear mixed assumed stress element can produce an accuracy level comparable to that of the Q8 element, while the number of the degrees of freedom is that of the Q4 element. 3. Selected algorithms for solving highly non-linear coupled systems are evaluated. It is concluded that the simple, accurate and quadratic convergent Newton-Raphson algorithm remains best. To reduce the single most frustrating disadvantage of the Newton method, namely the computational cost of constructing the gradients, analytical gradients are evaluated and implemented. It is shown the CPU time is significantly reduced when the analytical gradients are used. 4. Finally, a practical engineering MEMS problem is studied. The developed geometric nonlinear mixed element is used to model the structural part of a fixed-fixed beam that experiences large axial stress due to an applied electrostatic force. The Newton method with analytical gradients is used to solve this geometrically nonlinear coupled MEMS problem. / Dissertation (MEng (Mechanical))--University of Pretoria, 2007. / Mechanical and Aeronautical Engineering / unrestricted

We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points a₁,..., am ∈ Rn. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it particularly amenable to solution by interior-point methods, and it has been the subject of much theoretical complexity analysis. Here we focus on computation. We present a combined interior-point and active-set method for solving this problem. Our computational results demonstrate that our method solves very large problem instances (m = 30,000 and n = 30) to a high degree of accuracy in under 30 seconds on a personal computer. / Singapore-MIT Alliance (SMA)

In dieser Arbeit präsentieren wir eine neue Art von Newton-Verfahren mit Liniensuche, basierend auf Interpolation im Bildbereich nach Wedin et al. [LW84]. Von dem resultierenden stabilisierten Newton-Algorithmus wird theoretisch und praktisch gezeigt, dass er effizient ist im Falle von nichtsingulären Lösungen. Darüber hinaus wird beobachtet, dass er eine superlineare Rate von Konvergenz bei einfachen Singularitäten erhält. Hingegen ist vom Newton-Verfahren ohne Liniensuche bekannt, dass es nur linear von fast allen Punkten in der Nähe einer singulären Lösung konvergiert. In Hinsicht auf Anwendungen auf Komplementaritätsprobleme betrachten wir auch Systeme, deren Jacobimatrix nicht differenzierbar sondern nur semismooth ist. Auch hier erreicht unser stabilisiertes und beschleunigtes Newton- Verfahren Superlinearität bei einfachen Singularitäten. / In this thesis we present a new type of line-search for Newton’s method, based on range space interpolation as suggested by Wedin et al. [LW84]. The resulting stabilized Newton algorithm is theoretically and practically shown to be efficient in the case of nonsingular roots. Moreover it is observed that it maintains a superlinear rate of convergence at simple singularities. Whereas Newton’s method without line-search is known to converge only linearly from almost all points near the singular root. In view of applications to complementarity problems we also consider systems, whose Jacobian is not differentiable but only semismooth. Again, our stabilized and accelerated Newton’s method achieves superlinearity at simple singularities.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-11T10:37:14Z No. of bitstreams: 1 leandroalmeidavasconcelos.pdf: 2921811 bytes, checksum: acf68048e9da96cbcc9355d4ebc70813 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-26T11:53:39Z (GMT) No. of bitstreams: 1 leandroalmeidavasconcelos.pdf: 2921811 bytes, checksum: acf68048e9da96cbcc9355d4ebc70813 (MD5) / Made available in DSpace on 2016-02-26T11:53:39Z (GMT). No. of bitstreams: 1 leandroalmeidavasconcelos.pdf: 2921811 bytes, checksum: acf68048e9da96cbcc9355d4ebc70813 (MD5) Previous issue date: 2014-10-23 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A tecnologia HVDC (High Voltage Direct Current) possui características que a tornam especialmente atrativa para determinadas aplicações em transmissão de energia elétrica. Além disso, pode-se verificar a partir do estudo de utilização desse tipo de tecnologia no mundo que existe uma tendência e perspectiva de utilização crescente nos Sistemas Elétricos de Potência. Desta forma, torna-se cada vez mais importante dispor de técnicas que possibilitem a inclusão dos modelos destes equipamentos em programas de análise de redes de forma eficiente, principalmente no fluxo de potência, com a finalidade de permitir a correta modelagem da rede como um todo nos estudos de planejamento da expansão e operação. A transmissão em corrente contínua vem se tornando amplamente reconhecida no que tange as suas vantagens no transporte de grandes blocos de energia a grandes distâncias, no transporte de potência entre parques eólicos offshore para terra, na interconexão de sistemas com frequências não compatíveis, em travessias subaquáticas, dentre outras questões que a tornam técnica e economicamente viável em algumas situações. Nesse contexto, este trabalho tem por principal objetivo desenvolver e implementar uma metodologia genérica para a representação de Sistemas de Transmissão HVDC Multiterminais no problema de fluxo de potência. Neste sentido, tal metodologia é baseada na solução simultânea de um sistema de equações não lineares composto pelas representações em regime permanente das redes C.C. e C.A., utilizando-se o método de Newton-Raphson para sua solução. A partir deste contexto, são apresentadas as equações que representam a resposta de regime permanente dos conversores, da rede C.C. e das estratégias de controle aplicáveis a esses sistemas. Além disso, são apresentadas as principais configurações existentes de conversores HVDC, suas características e como é feita sua modelagem em regime permanente e no problema de Fluxo de Potência. A metodologia proposta é validada através do estudo de sistemas tutoriais e sistemas teste encontrados como referência na literatura especializada. Os resultados apresentados demonstram que a metodologia proposta é capaz de representar de forma satisfatória os modelos de sistemas HVDC Multiterminais nos estudos de regime permanente em Sistemas Elétricos de Potência. / High Voltage Direct Current (HVDC) technology has characteristics that make it especially attractive for certain transmission applications. Furthermore, it is possible to notice that there is a trend and prospect of increased use of this technology in Electric Power Systems around the world. In this context, it has been increasingly important to have techniques that efficiently include these equipment models in network analysis programs, especially in power flow, in order to allow a correct modeling of the network in studies of expansion planning and operation. The direct current transmission is becoming widely recognized by their advantages in transporting large blocks of power over long distances, to transport power from offshore wind farms to land, in asynchronous interconnection of systems, in underwater crossings, and other issues that make it technically and economically feasible in some situations. In this context, this thesis has the objective to develop and implement a generic methodology for the representation of HVDC Multi-Terminal Systems in the power flow problem. In this sense, this methodology is based on the simultaneous solution of a system of nonlinear equations that represent, in steady state studies, the DC and AC networks, using the Newton-Raphson method to solve the problem. Equations that represent the steady state response of the converters, the DC network and control strategies are presented. In addition, it will be presented the main settings of HVDC converters, their characteristics and how their modelling are set forth in the Power Flow problem. The proposed methodology is validated by studying tutorial and test systems found in the literature. The results show that the proposed methodology is able to represent satisfactorily models of HVDC Multi-Terminal Systems in studies of steady state in Electric Power Systems.

Die kontinuierliche Weiterentwicklung und Verbesserung technischer Prozesse erfolgt heute auf der Basis stochastischer und deterministischer Optimierungsstrategien in Kombination mit der numerischen Simulation dieser Abläufe. Da die FE-Simulation von Umformvorgängen in der Regel sehr zeitintensiv ist, bietet sich für die Optimierung solcher Prozesse der Einsatz deterministischer Methoden an, da hier weniger Optimierungsschritte und somit auch weniger FE-Simulationen notwendig sind. Eine wichtige Anforderung an solche Optimierungsverfahren ist globale Konvergenz zu lokalen Minima, da die optimalen Parametersätze nicht immer näherungsweise bekannt sind. Die zwei wichtigsten Strategien zum Ausdehnen des beschränkten Konvergenzradius der natürlichen Optimierungsverfahren (newtonschrittbasierte Verfahren und Gradientenverfahren) sind die Line-Search-Strategie und die Trust-Region-Strategie. Die Grundlagen der Line-Search-Strategie werden aufgearbeitet und die wichtigsten Teilalgorithmen implementiert. Danach wird dieses Verfahren auf eine effiziente Kombination der Teilalgorithmen und Verfahrensparameter hin untersucht. Im Anschluss wird die Leistung eines Optimierungsverfahrens mit Line-Search-Strategie verglichen mit der eines ebenfalls implementierten Optimierungsverfahrens mit skalierter Trust-Region-Strategie. Die Tests werden nach Einfügen der implementierten Verfahren in das Programm SPC-Opt anhand der Lösung eines Quadratmittelproblems aus der Materialparameteridentifikation sowie der Formoptimierung eines Umformwerkzeugs vorgenommen.

Die kontinuierliche Weiterentwicklung und Verbesserung technischer Prozesse erfolgt heute auf der Basis stochastischer und deterministischer Optimierungsstrategien in Kombination mit der numerischen Simulation dieser Abläufe. Da die FE-Simulation von Umformvorgängen in der Regel sehr zeitintensiv ist, bietet sich für die Optimierung solcher Prozesse der Einsatz deterministischer Methoden an, da hier weniger Optimierungsschritte und somit auch weniger FE-Simulationen notwendig sind. Eine wichtige Anforderung an solche Optimierungsverfahren ist globale Konvergenz zu lokalen Minima, da die optimalen Parametersätze nicht immer näherungsweise bekannt sind. Die zwei wichtigsten Strategien zum Ausdehnen des beschränkten Konvergenzradius der natürlichen Optimierungsverfahren (newtonschrittbasierte Verfahren und Gradientenverfahren) sind die Line-Search-Strategie und die Trust-Region-Strategie. Die Grundlagen der Line-Search-Strategie werden aufgearbeitet und die wichtigsten Teilalgorithmen implementiert. Danach wird dieses Verfahren auf eine effiziente Kombination der Teilalgorithmen und Verfahrensparameter hin untersucht. Im Anschluss wird die Leistung eines Optimierungsverfahrens mit Line-Search-Strategie verglichen mit der eines ebenfalls implementierten Optimierungsverfahrens mit skalierter Trust-Region-Strategie. Die Tests werden nach Einfügen der implementierten Verfahren in das Programm SPC-Opt anhand der Lösung eines Quadratmittelproblems aus der Materialparameteridentifikation sowie der Formoptimierung eines Umformwerkzeugs vorgenommen.:1 Einleitung 7 2 Verfahren zur unrestringierten Optimierung 9 2.1 Vorbemerkungen 9 2.2 Der Schrittvektor sk 10 2.3 Natürliche Schrittweite und Konvergenz der Verfahren 11 2.4 Richtung des steilsten Abstiegs 12 2.5 Newtonschrittbasierte Verfahren 13 2.5.1 Newton-Verfahren 15 2.5.2 Quasi-Newton-Verfahren der Broyden-Klasse 15 2.5.3 Der BFGS-Auffrisch-Algorithmus 18 2.5.4 Die SR1-Auffrisch-Formel 19 2.5.5 Die DFP-Auffrisch-Formel 20 2.5.6 Gauß-Newton-Verfahren 20 2.6 Erzwingen der Bedingung der positiven Definitheit von Gk 21 3 Übersicht über die Verfahren zum Stabilisieren der natürlichen Schrittweiten 24 3.1 Das Prinzip der Line-Search-Verfahren 24 3.2 Das Prinzip der Trust-Region-Verfahren 26 3.3 Vergleich der Trust-Region- und der Line-Search-Strategien 27 4 Line-Search-Strategien 30 4.1 Vorbemerkungen 30 4.2 Ein prinzipieller Line-Search-Algorithmus 33 5 Die Akzeptanzkriterien für die Line-Search-Strategien 36 5.1 Die exakte Schrittweite 37 5.2 Das Armijo-Kriterium, ein Abstiegskriterium 39 5.2.1 Das klassische Armijo-Kriterium 39 5.2.2 Armijo-Kriterium mit unterer Schranke fflo > 0 40 5.3 Die Goldstein-Kriterien 42 5.4 Die Wolfe-Kriterien 44 5.4.1 Die einfachen Wolfe-Kriterien 44 5.4.2 Die starken Wolfe-Kriterien 46 5.5 Näherungsweiser Line-Search basierend auf Armijo, ff-Methode 47 6 Ermittlung der nächsten Testschrittweite ffj+1 49 6.1 Die Startschrittweite ffj=1 51 6.2 Verfahren mit konstanten Faktoren 52 6.3 Verfahren mit konstanten Summanden 53 6.4 Verfahren mit quadratischen Polynomen 54 6.5 Verfahren mit kubischen Polynomen 56 6.6 Sektionssuche mit goldenem Schnitt 58 7 Absicherung und Abbruchbedingungen des Line-Search-Verfahrens 60 7.1 Die drei Konvergenzpunkte eines Line-Search-Verfahrens 60 7.1.1 Lokales Minimum in f 60 7.1.2 Algorithmus konvergiert gegen −1 61 7.1.3 Der Winkel zwischen sk und −rfk wird 90° 61 7.2 Weitere Absicherungen 62 7.2.1 Abstiegsrichtung 62 7.2.2 Der gradientenbezogene Schrittvektor 62 7.2.3 Zulässige Schrittweiten in der Extrapolationsphase 63 7.2.4 Intervalle bei der Interpolation 63 7.2.5 Maximale Durchlaufzahlen 63 8 Implementierung 65 8.1 Grundlegende Struktur der Implementierung 65 8.2 Anwendungsgebiete 67 8.2.1 Identifikation der Materialparameter der isotropen Verfestigung und der HILLschen Fließbedingung 67 8.2.2 Optimierung der Form eines Umformwerkzeugs 70 8.3 Test des Programms anhand der Identifikation der Parameter der isotropen Verfestigung und der HILLschen Fließbedingung 71 8.3.1 Einfluss der Funktionsumgebung 71 8.3.2 Test der Line-Search-Verfahrensparameter 74 8.3.3 Einfluss der Startwerte und der Qualität der Ableitungsermittlung 77 8.3.4 Test der Quasi-Newton-Strategien 77 8.3.5 Test der Trust-Region-Skalierung 79 8.3.6 Vergleich der Trust-Region- und der Line-Search-Strategie 80 8.3.7 Tests mit den HILLschen Anisotropieparametern und drei Vorwärtsrechnungen 81 9 Zusammenfassung und Ausblick 83 9.1 Zusammenfassung 83 9.2 Ausblick 84 Liste häufig verwendeter Formelzeichen 85 Literaturverzeichnis 88 A Zusätzliches zur Implementierung 90 A.1 Parametervorschläge für die Line-Search-Verfahren 90 A.2 Fehlercode-Liste 92 A.3 Programmablaufpläne 94 A.3.1 Ablauf in main.cpp 94 A.3.2 Ablauf in OneOptLoop 95 A.3.3 Ablauf während des Trust-Region-Verfahrens 96 A.3.4 Ablauf während des Line-Search-Verfahrens 97 A.4 Steuerung der Optimierungsoptionen über OptInputData.dat 98 A.4.1 Übergeordnete Algorithmen 98 A.4.1.1 Quasi-Newton-Verfahren 98 A.4.1.2 Absichern der positiven Definitheit von Gk 99 A.4.1.3 Auswahl des Optimierungsverfahrens, Auswahl der Schrittweitensteuerung 100 A.4.1.4 Abbruchbedingungen für die Lösungsfindung 100 A.4.1.5 Wahl des Startvektors x0 101 A.4.2 Die Trust-Region-Algorithmen 102 A.4.2.1 Wahl des Anfangsradius 0 des Vertrauensbereichs 102 A.4.2.2 Wahl des Skalierungsverfahrens 102 A.4.2.3 Wahl des Startwertes l=0 für die Regularisierungsparameteriteration 103 A.4.2.4 Regularisierungsparameteriteration 103 A.4.2.5 Wahl des Verfahrens zum Auffrischen des Radius des Vertrauensbereichs 103 A.4.2.6 Bedingungen für einen akzeptablen Schritt 104 A.4.2.7 Absicherungen des Trust-Region-Verfahrens 104 A.4.3 Die Line-Search-Algorithmen 105 A.4.3.1 Die Akzeptanzkriterien 105 A.4.3.2 Die Verfahren zur Extrapolation 105 A.4.3.3 Die Verfahren zur Interpolation 106 A.4.3.4 Verfahren zur Wahl von ffj=2 106 A.4.3.5 Absicherung des Line-Search-Verfahrens 106 B Testrechnungen 107 B.1 Ausgewählte Versuchsreihen 107 B.2 Bilder der Funktionsumgebung der Materialparameteridentifikation 109 B.3 Beschreibung der digitalen Anlagen 112 Eidesstattliche Erklärung und Aufgabenstellung 113

In this thesis I hope to provide a clear and concise introduction to Feigenbaum scaling accessible to undergraduate students. This is accompanied by a description of how to obtain numerical results by various means. A more intricate approach drawing from renormalization theory as well as a short consideration of some of the topological properties will also be presented. I was furthermore trying to put great emphasis on diagrams throughout the text to make the contents more comprehensible and intuitive.