Usando a Trajetória Central para Calcular o Centro Analítico de um Politopo Após a Adição de um Plano de Corte Profundo
Autores
|
1695 |
287,156
|
|
|
1696 |
287,156
|
Informações:
Publicações do PESC
Título
Usando a Trajetória Central para Calcular o Centro Analítico de um Politopo Após a Adição de um Plano de Corte Profundo
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
23/4/1998
Resumo
Neste trabalho desenvolvemos um algoritmo para resolver o problema de adicionar um corte profundo a um politopo, baseado na obtenção do centro analítico do politopo. Este problema é o passo central em métodos de plano de corte para resolver problemas de otimização convexa. Quando cortes muito profundos são considerados, a grande dificuldade é a recuperação da viabilidade para iniciar um algoritmo de centralização.
A nossa estratégia para vencer tal dificuldade é partir de um centro analítico aproximado do antigo politopo, que é conhecido, e seguir a trajetória central de um problema de programação linear auxiliar até obter um centro analítico aproximado do novo politopo.
Abstract
In this work we develope an algorithm to solve the problema of adding a very deep cut to a polytope based on obtaining the analytic center of the polytope. This problem is the central step in cutting plane methods for solving convex optimization problems. When very deep cuts are considered the major difficulty is to retrieve feasibility to initialize a centralization algorithm. Our strategy to overcome such difficulty is to start from an approximate analytic center of the old polytope that is known and then to follow the central path of an auxiliary linear programming until obtaining an approximate analytic center of the new polytope.
Arquivo