Projeção de um Ponto sobre um Hiperplano do Rn+: Complexidade Numérica e Implementação

Autores

1911
Claudio Prata Santiago
488,44
1912
Nelson Maculan Filho
(Orientador)
488,44

Informações:

Publicações do PESC

Título
Projeção de um Ponto sobre um Hiperplano do Rn+: Complexidade Numérica e Implementação
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
18/12/2000
Resumo
PESC: Resumo de Dissertação de Mestrado Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)

Projeção de um Ponto sobre um Hiperplano do Rn+: Complexidade Numérica e Implementação

Cláudio Prata Santiago

Dezembro/2000
Orientador: Nelson Maculan Filho  

 
Programa: Engenharia de Sistemas e Computação

      Apresentamos um algoritmo de complexidade O(n) para projeção de um vetor na interseção de um hiperplano e uma caixa no Rn. Resolver este problema de forma eficiente é de fundamental importância para alguns métodos de otimização, nos quais se resolve a projeção como subproblema, como, por exemplo, na solução o problema dual lagrangeano em programação inteira utilizando técnicas de subgradiente. Analisamos a extensão dessa abordagem para o caso de duas restrições e uma caixa, o que torna o problema bem mais complexo. Para esse novo problema, apresentamos um algoritmo O(n2logn) e sua aplicação a alguns métodos e-subgradientes. Mostramos também a aplicação dos algoritmos de projeção com canalização de variáveis de uma e duas restrições a problema de programação quadrática mais gerais.

Abstract
PESC: Master's Degree Abstract Abstract of Thesis presented at COPPE/UFRJ as a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.)

Projection of a Vector on a Hyperplane and Rn+: Numerical Complexity and Implementation

Cláudio Prata Santiago

Dezembro/2000
Advisor:Nelson Maculan Filho  
Department: Systems Engineering and Computer Science

      We present an O(n) time algorithm for the projection of a vector on the intersection of a hyperplane and a box in Rn. To solve this projection problem efficiently is very important for some optimization methods, in which the projection is solved as a subproblem, as in the solution of the dual Lagrangean problem in integer programming using subgradient techniques. We also analyse the extension of this approach to the case of two restrictions and a box, what makes the problem much more complex. For this new problem, we present an O(n2logn) algorithm and its application to some e-subgradient methods. We also show the application of the algorithms for projecting on one or two restrictions and a box to more general quadratic problems.

Arquivo
Topo