Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-08T19:39:28Z No. of bitstreams: 1 Dissertação - Suellen Paulino Lima.pdf: 623720 bytes, checksum: 10d03fee1aa131fb068db1c244116b29 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-08T19:39:51Z (GMT) No. of bitstreams: 1 Dissertação - Suellen Paulino Lima.pdf: 623720 bytes, checksum: 10d03fee1aa131fb068db1c244116b29 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-08T19:40:06Z (GMT) No. of bitstreams: 1 Dissertação - Suellen Paulino Lima.pdf: 623720 bytes, checksum: 10d03fee1aa131fb068db1c244116b29 (MD5) / Made available in DSpace on 2016-06-08T19:40:06Z (GMT). No. of bitstreams: 1 Dissertação - Suellen Paulino Lima.pdf: 623720 bytes, checksum: 10d03fee1aa131fb068db1c244116b29 (MD5) Previous issue date: 2015-12-15 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This paper shows algorithms for problem solving Unrestricted. Initially it will address the Proximal Point Algorithm Inaccurate using classical algorithms for solving the problem of regularization of convex function, continuously differentiable and decisive the Hessian near zero. Then the Search Algorithm Nonlinear monotone that aims to improve the likelihood of find a global optimum, using traditional methods to decrease obtaining the step size, moreover, they can improve the speed of convergence in specific cases of monotonous scheme. At the end we will implementation of quadratic functions and analysis of results / Apresentaremos neste trabalho algoritmos para resolução de problemas irrestritos. Inicialmente será abordado o Algoritmo do Ponto Proximal Inexato com a utilização de algorítimos clássicos para resolução do problema de regularização da função convexa, continuamente diferenciável e com determinante da hessiana próximo de zero. Em seguida, o Algoritmo de Busca Linear não monótona que tem o objetivo de melhorar a probabilidade de encontrar um ótimo global, utilizando métodos de descida tradicionais para obter o tamanho do passo, além disso, eles podem melhorar a velocidade de convergência em casos específicos do esquema monótono. Ao final faremos a implementação de funções quadráticas e a análise dos resultados obtidos

Made available in DSpace on 2015-04-22T22:16:10Z (GMT). No. of bitstreams: 1 Dissertacao Jeanne Moreira.pdf: 447774 bytes, checksum: 635ca33ffaf3746929571ab0aabcfd32 (MD5) Previous issue date: 2008-12-29 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / In this work we use the gradient method to minimize, without restrictions, convex and pseudoconvex continuously differentiable functions. An important theme considered is the path length determination. We have that, when minimizing pseudoconvex functions, the linear search is exact. In this case, we present the first algorithm to obtain the path length, where will be included a quadratic regularization term, in the proximal point method sense. When dealing with the minimization of convex functions case, we have that the linear search is not exact. To obtain the path length, two algorithms are presented: the former needs that the gradient of the objective function satisfies a Lipschitz condition with a known constant L > 0. The latter is based on the work of Dennis-Schnabel (see [4]). The three process are based on the quasi-Fejér convergence principle. Although these descent methods need that the objective functions to be minimized have bounded level sets, in order to establish that the limit points are stationary, this approach guarantees the complete convergence of every sequence to a minimizer of the function without the hypothesis of bounded level sets. / Neste trabalho utilizamos o método do gradiente para minimizar, sem restrições, funções continuamente diferenciáveis pseudo-convexas e convexas. Um termo considerado importante é o cálculo do comprimento do passo. Na minimização de funções pseudo-convexas a busca linear é exata. Neste caso, apresentamos o primeiro algoritmo para o cálculo do comprimento do passo, onde é acrescentado um termo de regularização quadrático no sentido do método do ponto proximal. Posteriormente, na minimização de funções convexas, a busca linear é inexata. Para o cálculo do comprimento do passo apresentamos dois algoritmos: um necessita que o gradiente da função objetivo satisfaça uma condição de Lipschitz com constante L > 0 conhecida, e o outro é baseado no trabalho desenvolvido por Dennis-Schnabel (ver [4]). Os três processos baseiam-se na noção da quase-Fejér convergência. Embora os métodos de descida necessitem que a função objetivo a ser minimizada possua conjuntos de níveis limitados a fim de estabelecer que os pontos de acumulação sejam estacionários, nesta abordagem é garantida a convergência completa de toda sequência para um minimizador da função sem a hipótese de limitação do conjunto de nível.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-03-02T15:54:49Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação_Daniele A. F. Silva.pdf: 1378175 bytes, checksum: 8dfe0d31351466e795bb26e262eb8780 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-03-02T15:55:00Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação_Daniele A. F. Silva.pdf: 1378175 bytes, checksum: 8dfe0d31351466e795bb26e262eb8780 (MD5) / Made available in DSpace on 2018-03-02T15:55:00Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação_Daniele A. F. Silva.pdf: 1378175 bytes, checksum: 8dfe0d31351466e795bb26e262eb8780 (MD5) Previous issue date: 2016-11-04 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents a linear search algorithm for unconstrained optimization problems proposed by Gonglin Yuan, Sha Lu Wei and Zengxi [1], called here by Algorithm GSZ. This algorithm is designed from the perspective of inheriting the simplicity and low computational cost of the conjugate gradient method. n this context, a detailed proof of the global convergence analysis for functions not necessarily convex is presented. We also emphasize the achievement of the linear convergence rate for the case where the function is strongly Convex. / Neste trabalho apresentamos um algoritmo de busca linear para problemas de otimização irrestrita proposto por Gonglin Yuan, Sha Lu e Zengxi Wei [1], denominado aqui por Algoritmo GSZ. Este algoritimo é concebido sob a perspectiva de herdar a simplicidade e o baixo custo computacional do método do gradiente conjugado. Neste contexto, uma prova detalhada da análise de convergência global para funções não necessariamente convexas é apresentada. Ressaltamos ainda a obtenção da taxa de convergência linear para o caso em que a função é fortemente convexa.

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.

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.

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.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2015-05-21T19:19:51Z No. of bitstreams: 2 Tese - Reinier Díaz Millán - 2015.pdf: 3568052 bytes, checksum: b4c892f77911a368e1b8f629afb5e66e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2015-05-21T19:21:31Z (GMT) No. of bitstreams: 2 Tese - Reinier Díaz Millán - 2015.pdf: 3568052 bytes, checksum: b4c892f77911a368e1b8f629afb5e66e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-05-21T19:21:31Z (GMT). No. of bitstreams: 2 Tese - Reinier Díaz Millán - 2015.pdf: 3568052 bytes, checksum: b4c892f77911a368e1b8f629afb5e66e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-02-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Nesta tese apresentamos v arios algoritmos para resolver os problemas de Desigualdade Variacional e Inclus~ao. Para o problema de desigualdade variacional propomos, no Cap tulo 2 uma generaliza c~ao do algoritmo cl assico extragradiente, utilizando vetores normais n~ao nulos do conjunto vi avel. Em particular, dois algoritmos conceituais s~ao propostos e cada um deles cont^em tr^es variantes diferentes de proje c~ao que est~ao relacionadas com algoritmos extragradientes modi cados. Duas buscas diferentes s~ao propostas, uma sobre a borda do conjunto vi avel e a outra ao longo das dire c~oes vi aveis. Cada algoritmo conceitual tem uma estrat egia diferente de busca e tr^es formas de proje c~ao especiais, gerando tr^es sequ^encias com diferente e interessantes propriedades. E feito a an alise da converg^encia de ambos os algoritmos conceituais, pressupondo a exist^encia de solu c~oes, continuidade do operador e uma condi c~ao mais fraca do que pseudomonotonia. No Cap tulo 4, n os introduzimos um algoritmo direto de divis~ao para o problema variacional em espa cos de Hilbert. J a no Cap tulo 5, propomos um algoritmo de proje c~ao relaxada em Espa cos de Hilbert para a soma de m operadores mon otonos maximais ponto-conjunto, onde o conjunto vi avel do problema de desigualdade variacional e dado por uma fun c~ao n~ao suave e convexa. Neste caso, as proje c~oes ortogonais ao conjunto vi avel s~ao substitu das por proje c~oes em hiperplanos que separam a solu c~ao da itera c~ao atual. Cada itera c~ao do m etodo proposto consiste em proje c~oes simples de tipo subgradientes, que n~ao exige a solu c~ao de subproblemas n~ao triviais, utilizando apenas os operadores individuais, explorando assim a estrutura do problema. Para o problema de Inclus~ao, propomos variantes do m etodo de divis~ao de forward-backward para achar um zero da soma de dois operadores, a qual e a modi ca c~ao cl assica do forwardbackward proposta por Tseng. Um algoritmo conceitual e proposto para melhorar o apresentado por Tseng em alguns pontos. Nossa abordagem cont em, primeramente, uma busca linear tipo Armijo expl cita no esp rito dos m etodos tipo extragradientes para desigualdades variacionais. Durante o processo iterativo, a busca linear realiza apenas um c alculo do operador forward-backward em cada tentativa de achar o tamanho do passo. Isto proporciona uma consider avel vantagem computacional pois o operador forward-backward e computacionalmente caro. A segunda parte do esquema consiste em diferentes tipos de proje c~oes, gerando sequ^encias com caracter sticas diferentes. / In this thesis we present various algorithms to solve the Variational Inequality and Inclusion Problems. For the variational inequality problem we propose, in Chapter 2, a generalization of the classical extragradient algorithm by utilizing non-null normal vectors of the feasible set. In particular, two conceptual algorithms are proposed and each of them has three di erent projection variants which are related to modi ed extragradient algorithms. Two di erent linesearches, one on the boundary of the feasible set and the other one along the feasible direction, are proposed. Each conceptual algorithm has a di erent linesearch strategy and three special projection steps, generating sequences with di erent and interesting features. Convergence analysis of both conceptual algorithms are established, assuming existence of solutions, continuity and a weaker condition than pseudomonotonicity on the operator. In Chapter 4 we introduce a direct splitting method for solving the variational inequality problem for the sum of two maximal monotone operators in Hilbert space. In Chapter 5, for the same problem, a relaxed-projection splitting algorithm in Hilbert spaces for the sum of m nonsmooth maximal monotone operators is proposed, where the feasible set of the variational inequality problem is de ned by a nonlinear and nonsmooth continuous convex function inequality. In this case, the orthogonal projections onto the feasible set are replaced by projections onto separating hyperplanes. Furthermore, each iteration of the proposed method consists of simple subgradient-like steps, which does not demand the solution of a nontrivial subproblem, using only individual operators, which explores the structure of the problem. For the Inclusion Problem, in Chapter 3, we propose variants of forward-backward splitting method for nding a zero of the sum of two operators, which is a modi cation of the classical forward-backward method proposed by Tseng. The conceptual algorithm proposed here improves Tseng's method in many instances. Our approach contains rstly an explicit Armijo-type line search in the spirit of the extragradient-like methods for variational inequalities. During the iterative process, the line search performs only one calculation of the forward-backward operator in each tentative for nding the step size. This achieves a considerable computational saving when the forward-backward operator is computationally expensive. The second part of the scheme consists of special projection steps bringing several variants.