Métodos do tipo Lagrangiano Aumentado são muito utilizados para minimização de funções sujeitas a restrições gerais. Nestes métodos, podemos separar o conjunto de restrições em dois grupos: restrições fáceis e restrições difíceis. Dizemos que uma restrição é fácil se existe um algoritmo disponível e eficiente para resolver problemas restritos a este tipo de restrição. Caso contrário, dizemos que a restrição é difícil. Métodos do tipo Lagrangiano aumentado resolvem, a cada iteração, problemas sujeitos às restrições fáceis, penalizando as restrições difíceis. Problemas de minimização com restrições lineares aparecem com freqüência, muitas vezes como resultados da aproximação de problemas com restrições gerais. Este tipo de problema surge também como subproblema de métodos do tipo Lagrangiano aumentado. Assim, uma implementação eficiente para resolver problemas com restrições lineares é relevante para a implementação eficiente de métodos para resolução de problemas de programação não-linear. Neste trabalho, começamos considerando fáceis as restrições de caixa. Introduzimos BETRA-ESPARSO, uma versão de BETRA para problemas de grande porte. BETRA é um método de restrições ativas que utiliza regiões de confiança para minimização em cada face e gradiente espectral projetado para sair das faces. Utilizamos BETRA (denso ou esparso) na resolução dos subproblemas que surgem a cada iteração de ALGENCAN (um método de lagrangiano aumentado). Para decidir qual algoritmo utilizar para resolver cada subproblema, desenvolvemos regras que escolhem um método para resolver o subproblema de acordo com suas características. Em seguida, introduzimos dois algoritmos de restrições ativas desenvolvidos para resolver problemas com restrições lineares (BETRALIN e GENLIN). Estes algoritmos utilizam, a cada iteração, o método do Gradiente Espectral Projetado Parcial quando decidem mudar o conjunto de restrições ativas. O método do gradiente Espectral Projetado Parcial foi desenvolvido especialmente para este propósito. Neste método, as projeções são computadas apenas em um subconjunto das restrições, com o intuito de torná-las mais eficientes. Por fim, tendo introduzido um método para minimização com restrições lineares, consideramos como fáceis as restrições lineares. Incorporamos BETRALIN e GENLIN ao arcabouço de Lagrangianos aumentados e verificamos experimentalmente a eficiência e eficácia destes métodos que trabalham explicitamente com restrições lineares e penalizam as demais. / Augmented Lagrangian methods are widely used to solve general nonlinear programming problems. In these methods, one can split the set of constraints in two groups: the set of easy and hard constraints. A constraint is called easy if there is an efficient method available to solve problems subject to that kind of constraint. Otherwise, the constraints are called hard. Augmented Lagrangian methods solve, at each iteration, problems subject to the set of easy constraints while penalizing the set of hard constraints. Linearly constrained problems appear frequently, sometimes as a result of a linear approximation of a problem, sometimes as an augmented Lagrangian subproblem. Therefore, an efficient method to solve linearly constrained problems is important for the implementation of efficient methods to solve nonlinear programming problems. In this thesis, we begin by considering box constraints as the set of easy constraints. We introduce a version of BETRA to solve large scale problems. BETRA is an active-set method that uses a trust-region strategy to work within the faces and spectral projected gradient to leave the faces. To solve each iteration\'s subproblem of ALGENCAN (an augmented Lagrangian method) we use either the dense or the sparse version of BETRA. We develope rules to decide which box-constrained inner solver should be used at each augmented Lagrangian iteration that considers the main characteristics of the problem to be solved. Then, we introduce two active-set methods to solve linearly constrained problems (BETRALIN and GENLIN). These methods use Partial Spectral Projected Gradient method to change the active set of constraints. The Partial Spectral Projected Gradient method was developed specially for this purpose. It computes projections onto a subset of the linear constraints, aiming to make the projections more efficient. At last, having introduced a linearly-constrained solver, we consider the set of linear constraints as the set of easy constraints. We use BETRALIN and GENLIN in the framework of augmented Lagrangian methods and verify, using numerical experiments, the efficiency and robustness of those methods that work with linear constraints and penalize the nonlinear constraints.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-01092008-114422 |
| Date | 24 July 2008 |
| Creators | Marina Andretta |
| Contributors | Ernesto Julian Goldberg Birgin, Carlos Humes Junior, Nelson Maculan Filho, José Mario Martinez Perez, Marcos Raydan |
| Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0115 seconds