• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
10.11606/T.45.2008.tde-01092008-114422
Documento
Autor
Nombre completo
Marina Andretta
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2008
Director
Tribunal
Birgin, Ernesto Julian Goldberg (Presidente)
Humes Junior, Carlos
Maculan Filho, Nelson
Martinez Perez, José Mario
Raydan, Marcos
Título en portugués
Tópicos em otimização com restrições lineares
Palabras clave en portugués
gradiente espectral projetado
métodos de Lagrangiano aumentado
métodos de restrições ativas
minimização com restrições lineares
programação não-linear.
Resumen en portugués
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.
Título en inglés
Topics on linearly-constrained optimization
Palabras clave en inglés
active-set methods
augmented Lagrangian methods
linearly-constrained methods
nonlinear programming.
spectral projected gradient
Resumen en inglés
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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
andretta.pdf (1.27 Mbytes)
Fecha de Publicación
2008-11-17
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2020. Todos los derechos reservados.