Método Subgradiente Condicional com Sequência Ergódica / Conditional subgradient method with sequence Ergodic

AUTOR(ES)

Jose Carlos Rubianes Silva

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

18/02/2011

RESUMO

Nesta dissertação consideramos um problema de otimização convexo e estudamos variações do método subgradiente aplicado ao problema dual obtido via uma função Lagrangiana. Estudamos o método subgradiente condicional desenvolvido por Larsson et al, o qual é uma simples variação do método subgradiente usual. A principal diferença é que os subgradientes são condicionados a um conjunto restrição, mais especificamente, o comportamento da função fora do conjunto restrição não é levado em conta. Uma motivação para estudar tais métodos consiste principalmente na sua simplicidade, em especial, estes métodos são bastante usados em problemas de grande porte. O método subgradiente, quando aplicado a um problema dual, é relativamente eficaz para obter boas aproximações de soluções duais e do valor ótimo, no entanto, não possue a mesma eficiência para obter soluções primais. Analisamos uma estratégia para obter boas aproximações de soluções primais via método subgradiente condicional, com pouco custo computacional adicional. Esta estratégia consiste em construir uma sequência ergódica das soluções obtidas durante a resolução dos subproblemas Lagrangianos. Mostraremos que os pontos limites desta sequência ergódica são soluções primais. Consideramos diferentes regras para o tamanho do passo, em particular, seguindo as idéias de Nedic e Ozdaglar, apresentamos estimativas da sequência ergódica com o conjunto de soluções primais e/ou o conjunto viável quando usamos a regra de passos constantes.

ASSUNTO(S)

programação convexa métodos subgradientes subgradiente condicinal relaxação lagrangiana dualidade lagrangiana e convergência ergódica matematica aplicada convex programming subgradient methods conditional subgradient lagrangean relaxation lagrangean duality and ergodic convergence

Documentos Relacionados

• Método Subgradiente Condicional com Sequência Ergódica
• TESTS WITH CONDITIONAL FREQUENTISTS ERRORS AND TESTS WITH INTERPRETATION BAYESIAN AND CONDITIONAL FREQUENTISTS.
• Some results about ergodic optimization for noncompact spaces
• Reusing values in a dynamic conditional execution architecture
• Audiologic triage in neonates with Robin sequence