Gotowa bibliografia na temat „Newton algorithms”

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (p. 99-101).<br>Most of today's communication networks are large-scale and comprise of agents with local information and heterogeneous preferences, making centralized control and coordination impractical. This motivated much interest in developing and studying distributed algorithms for network resource allocation problems, such as Internet routing, data collection and processing in sensor networks, and cross-layer communication network design. Existing works on network resource allocation problems rely on using dual decomposition and first-order (gradient or subgradient) methods, which involve simple computations and can be implemented in a distributed manner, yet suffer from slow rate of convergence. Second-order methods are faster, but their direct implementation requires computation intensive matrix inversion operations, which couple information across the network, hence cannot be implemented in a decentralized way. This thesis develops and analyzes Newton-type (second-order) distributed methods for network resource allocation problems. In particular, we focus on two general formulations: Network Utility Maximization (NUM), and network flow cost minimization problems. For NUM problems, we develop a distributed Newton-type fast converging algorithm using the properties of self-concordant utility functions. Our algorithm utilizes novel matrix splitting techniques, which enable both primal and dual Newton steps to be computed using iterative schemes in a decentralized manner with limited information exchange. Moreover, the step-size used in our method can be obtained via an iterative consensus-based averaging scheme. We show that even when the Newton direction and the step-size in our method are computed within some error (due to finite truncation of the iterative schemes), the resulting objective function value still converges superlinearly to an explicitly characterized error neighborhood. Simulation results demonstrate significant convergence rate improvement of our algorithm relative to the existing subgradient methods based on dual decomposition. The second part of the thesis presents a distributed approach based on a Newtontype method for solving network flow cost minimization problems. The key component of our method is to represent the dual Newton direction as the limit of an iterative procedure involving the graph Laplacian, which can be implemented based only on local information. Using standard Lipschitz conditions, we provide analysis for the convergence properties of our algorithm and show that the method converges superlinearly to an explicitly characterized error neighborhood, even when the iterative schemes used for computing the Newton direction and the stepsize are truncated. We also present some simulation results to illustrate the significant performance gains of this method over the subgradient methods currently used.<br>by Ermin Wei.<br>S.M.

Orientador: Maria Aparecida Diniz Ehrhardt<br>Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica<br>Made available in DSpace on 2018-08-16T22:41:08Z (GMT). No. of bitstreams: 1 Sassi_Carlos_M.pdf: 2431422 bytes, checksum: 7e2d7456777a9a43cc62a5524d3fca93 (MD5) Previous issue date: 2010<br>Resumo: Iniciamos este trabalho com o estudo de equações não lineares, transcendentais de uma única variável, com o objetivo principal de abordar sistemas de equações não lineares, analisar os métodos, algoritmos e realizar testes computacionais, embasados na plataforma MatLab "The Language of Technical computer - R2008a - version 7.6.0.324_. Os algoritmos tratados se referem ao método de Newton, métodos Quase-Newton, método Secante e aplicações, com enfoque na H-equação de Chandrasekhar. Estudamos aspectos de convergência de cada um destes métodos que puderam ser analisados na prática, a partir dos experimentos numéricos realizados<br>Abstract: This work begins with the study of nonlinear and transcendental equations, with only one variable, which has the main purpose to study systems of nonlinear equations, methods and algoritms, in order to accomplish computational tests using MatLab Codes "The Language of Technical computer - R2008a - version 7.6.0.324". These algoritms were concerned to Newton's method, Quasi-Newton method, Secant method, and the main application was the Chandrasekhar H-Equation. Convergence studies for these methods were analysed with the applied numerical methods<br>Mestrado<br>Matematica<br>Mestre em Matemática

Orientador: Roberto Andreani<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica<br>Made available in DSpace on 2018-08-04T05:03:19Z (GMT). No. of bitstreams: 1 Gaujoux_RenaudGilles_M.pdf: 1743739 bytes, checksum: a3548a59bc983f4398cb0136c62c1d6a (MD5) Previous issue date: 2005<br>Resumo: Esta dissertação trata da aplicação de um método de tipo Newton generalizado aos sistemas KKT. Graças às funções chamadas de NCP, o sistema KKT pode ser reformulado como uma equação do tipo H(z) = O, onde H é uma função semi-suave. Nos preliminares teóricos apresentamos os conceitos importantes para a análise desse tipo de sistema quando a função involvida não é diferenciável. Trata-se de subdiferencial, semi-suavidade, semi-derivada. Então, usando um ponto de vista global, descrevemos de uma vez só as diferentes generalizações do método de Newton, apresentando as condições suficientes de convergência local. Uma versão globalizada do método é também detalhada. Com o fim de aplicar o algoritmo à reformulação semi-suave do sistema KKT, estudamos as propriedades da função H, primeiro independentemente da função NCP usada. Então analisamos o caso de três funções NCP particulares: a função do Mínimo, a função de Fischer-Burmeister, a função de Fischer-Burmeister Penalizada. Apresentamos os resultados de testes numéricos que comparam o desempenho do algoritmo quando usa as diferentes funções NCP acima<br>Abstract: This work deals with the use of generalized Newton type method to solve KKT systems. By the mean of so called NCP functions, any KKT system can be writen as an equation of type H(z) = O, where H is a semismooth function. In a teorical preliminaries part, we present some key notions for the analysis of such a type of system, whose the involved function is not differentiable. It deals with subdifferential, semismoothness, semiderivative. Then, tackling the problem with a very general point of view, we make a unified description of different generalizations of N ewton method, giving sufficient local convergence conditions. More over, we detail a possible globalization of such methods. In order to use this global algorithm to solve semismooth form of KKT systems, we study some of the H function's properties, first without specifying any underlying NCP function, and then in the case of three known NCP functions: the minimum function, the Fischer-Burmeister function and the penalized Fischer-Burmeister function. Finally, we give the results of numerical tests, which compare the algorithm's performance for each of these three NCP functions<br>Mestrado<br>Matematica Aplicada<br>Mestre em Matemática Aplicada