Neste trabalho, propomos um método de pontos interiores para minimização com restrições lineares de grande porte. Este método explora a linearidade das restrições, partindo de um ponto viável e preservando a viabilidade dos iterandos. Apresentamos os principais resultados de convergência global, além de uma descrição rica em detalhes de uma implementação prática de todos os passos do método. Para atestar a implementação do método, exibimos uma ampla experimentação numérica, e uma análise comparativa com métodos bem difundidos na comunidade de otimização contínua. / In this work, we propose an interior-point method for large-scale linearly constrained optimization. This method explores the linearity of the constraints, starting from a feasible point and preserving the feasibility of the iterates. We present the main global convergence results, together with a rich description of the implementation details of all the steps of the method. To validate the implementation of the method, we present a wide set of numerical experiments and a comparative analysis with well known softwares of the continuous optimization community.

A new neural network approach for performing matrix computations is presented. The idea of this approach is to construct a feed-forward neural network (FNN) and then train it by matching a desired set of patterns. The solution of the problem is the converged weight of the FNN. Accordingly, unlike the conventional FNN research that concentrates on external properties (mappings) of the networks, this study concentrates on the internal properties (weights) of the network. The present network is linear and its weights are usually strongly constrained; hence, complicated overlapped network needs to be construct. It should be noticed, however, that the present approach depends highly on the training algorithm of the FNN. Unfortunately, the available training methods; such as, the original Back-propagation (BP) algorithm, encounter many deficiencies when applied to matrix algebra problems; e. g., slow convergence due to improper choice of learning rates (LR). Thus, this study will focus on the development of new efficient and accurate FNN training methods. One improvement suggested to alleviate the problem of LR choice is the use of a line search with steepest descent method; namely, bracketing with golden section method. This provides an optimal LR as training progresses. Another improvement proposed in this study is the use of conjugate gradient (CG) methods to speed up the training process of the neural network. The computational feasibility of these methods is assessed on two matrix problems; namely, the LU-decomposition of both band and square ill-conditioned unsymmetric matrices and the inversion of square ill-conditioned unsymmetric matrices. In this study, two performance indexes have been considered; namely, learning speed and convergence accuracy. Extensive computer simulations have been carried out using the following training methods: steepest descent with line search (SDLS) method, conventional back propagation (BP) algorithm, and conjugate gradient (CG) methods; specifically, Fletcher Reeves conjugate gradient (CGFR) method and Polak Ribiere conjugate gradient (CGPR) method. The performance comparisons between these minimization methods have demonstrated that the CG training methods give better convergence accuracy and are by far the superior with respect to learning time; they offer speed-ups of anything between 3 and 4 over SDLS depending on the severity of the error goal chosen and the size of the problem. Furthermore, when using Powell's restart criteria with the CG methods, the problem of wrong convergence directions usually encountered in pure CG learning methods is alleviated. In general, CG methods with restarts have shown the best performance among all other methods in training the FNN for LU-decomposition and matrix inversion. Consequently, it is concluded that CG methods are good candidates for training FNN of matrix computations, in particular, Polak-Ribidre conjugate gradient method with Powell's restart criteria.

Orientadores: Márcia Aparecida Gomes Ruggiero, Sandra Augusta Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-21T10:21:10Z (GMT). No. of bitstreams: 1 Begiato_RodolfoGotardi_D.pdf: 3815627 bytes, checksum: 59584610cfd737a94e68dc5bf3735e25 (MD5) Previous issue date: 2012 / Resumo: O objetivo desta tese é tratar da resolução de sistemas não lineares de grande porte, em que as funções são continuamente diferenciáveis, por meio de uma abordagem híbrida que utiliza um método iterativo com duas fases. A primeira fase consiste de versões sem derivadas do método do ponto fixo empregando parâmetros espectrais para determinar o tamanho do passo da direção residual. A segunda fase é constituída pelo método de Newton inexato em uma abordagem matrix-free, em que é acoplado o método GMRES para resolver o sistema linear que determina a nova direção de busca. O método híbrido combina ordenadamente as duas fases de forma que a segunda é acionada somente em caso de falha na primeira e, em ambas, uma condição de decréscimo não-monótono deve ser verificada para aceitação de novos pontos. Desenvolvemos ainda um segundo método, em que uma terceira fase de busca direta é acionada em situações em que o excesso de buscas lineares faz com que o tamanho de passo na direção do método de Newton inexato torne-se demasiadamente pequeno. São estabelecidos os resultados de convergência dos métodos propostos. O desempenho computacional é avaliado em uma série de testes numéricos com problemas tradicionalmente encontrados na literatura. Tanto a análise teórica quanto a numérica evidenciam a viabilidade das abordagens apresentadas neste trabalho / Abstract: This thesis handles large-scale nonlinear systems for which all the involved functions are continuously differentiable. They are solved by means of a hybrid approach based on an iterative method with two phases. The first phase is defined by derivative-free versions of a fixed-point method that employs spectral parameters to define the steplength along the residual direction. The second phase consists of a matrix-free inexact Newton method that employs the GMRES to solve the linear system that computes the search direction. The proposed hybrid method neatly combines the two phases in such a way that the second is called only in case the first one fails. To accept new points in both phases, a nonmonotone decrease condition upon a merit function has to be verified. A second method is developed as well, with a third phase based on direct search, that should act whenever too many line searches have excessively decreased the steplenght along the inexact- Newton direction. Convergence results for the proposed methods are established. The computational performance is assessed in a set of numerical experiments with problems from the literature. Both the theoretical and the experimental analysis corroborate the feasibility of the proposed strategies / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Neste trabalho, propomos um método de pontos interiores para minimização com restrições lineares de grande porte. Este método explora a linearidade das restrições, partindo de um ponto viável e preservando a viabilidade dos iterandos. Apresentamos os principais resultados de convergência global, além de uma descrição rica em detalhes de uma implementação prática de todos os passos do método. Para atestar a implementação do método, exibimos uma ampla experimentação numérica, e uma análise comparativa com métodos bem difundidos na comunidade de otimização contínua. / In this work, we propose an interior-point method for large-scale linearly constrained optimization. This method explores the linearity of the constraints, starting from a feasible point and preserving the feasibility of the iterates. We present the main global convergence results, together with a rich description of the implementation details of all the steps of the method. To validate the implementation of the method, we present a wide set of numerical experiments and a comparative analysis with well known softwares of the continuous optimization community.

O método do Gradiente Espectral, introduzido por Barzilai e Borwein e analisado por Raydan, para minimização irrestrita, é um método simples cujo desempenho é comparável ao de métodos tradicionais como, por exemplo, gradientes conjugados. Desde a introdução do método, assim como da sua extensão para minimização em conjuntos convexos, foram introduzidas várias combinações de passos espectrais diferentes, assim como de buscas lineares não monótonas diferentes. Dos resultados numéricos apresentados em vários trabalhos não é possível inferir se existem diferenças significativas no desempenho dos diversos métodos. Além disso, também não fica clara a relevância das buscas não monótonas como uma ferramenta em si próprias ou se, na verdade, elas são úteis apenas para permitir que o método seja o mais parecido possível com o método original de Barzilai e Borwein. O objetivo deste trabalho é comparar os diversos métodos recentemente introduzidos como combinações de diferentes buscas lineares não monótonas e diferentes passos espectrais para encontrar a melhor combinação e, a partir daí, aferir o desempenho numérico do método. / The Spectral Gradient method, introduced by Barzilai and Borwein and analized by Raydan for unconstrained minimization, is a simple method whose performance is comparable to traditional methods, such as conjugate gradients. Since the introduction of method, as well as its extension to minimization of convex sets, there were introduced various combinations of different spectral steplengths, as well as different nonmonotone line searches. By the numerical results presented in many studies it is not possible to infer whether there are siginificant differences in the performance of various methods. It also is not sure the relevance of the nonmonotone line searches as a tool in themselves or whether, in fact, they are usefull only to allow the method to be as similar as possible with the original method of Barzilai e Borwein. The objective of this study is to compare the different methods recently introduced as different combinations of nonmonotone linear searches and different spectral steplengths to find the best combination and from there, evaluating the numerical performance of the method.

Dans cette thèse, nous nous intéressons au problème de recherche incrémentale de motifs dans des séquences fortement similaires (On-line Pattern Matching on Highly Similar Sequences), issues de technologies de séquençage à haut débit (SHD). Ces séquences ne diffèrent que par de très petites quantités de variations et présentent un niveau de similarité très élevé. Il y a donc un fort besoin d'algorithmes efficaces pour effectuer la recherche rapide de motifs dans de tels ensembles de séquences spécifiques. Nous développons de nouveaux algorithmes pour traiter ce problème. Cette thèse est répartie en cinq parties. Dans la première partie, nous présentons un état de l'art sur les algorithmes les plus connus du problème de recherche de motifs et les index associés. Puis, dans les trois parties suivantes, nous développons trois algorithmes directement dédiés à la recherche incrémentale de motifs dans un ensemble de séquences fortement similaires. Enfin, dans la cinquième partie, nous effectuons une étude expérimentale sur ces algorithmes. Cette étude a montré que nos algorithmes sont efficaces en pratique en terme de temps de calcul / In this thesis, we are interested in the problem of on-line pattern matching in highly similar sequences, On-line Pattern Matching on Highly Similar Sequences, outcoming from Next Generation Sequencing technologies (NGS). These sequences only differ by a very small amount. There is thus a strong need for efficient algorithms for performing fast pattern matching in such specific sets of sequences. We develop new algorithms to process this problem. This thesis is partitioned into five parts. In the first part, we present a state of the art on the most popular algorithms of finding problem and the related indexes. Then, in the three following parts, we develop three algorithms directly dedicated to the on-line search for patterns in a set of highly similar sequences. Finally, in the fifth part, we conduct an experimental study on these algorithms. This study shows that our algorithms are efficient in practice in terms of computation time.

This paper studies Newton's method for solving the algebraic Riccati equation combined with an exact line search. Based on these considerations we present a Newton{like method for solving algebraic Riccati equations. This method can improve the sometimes erratic convergence behavior of Newton's method.

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 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.