Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/14068
Tipo: Tese
Título: Relaxações tratáveis para problemas de otimização cúbicos restritos à esfera
Título(s) alternativo(s): Tractable relaxations for cubic optimization problems subject to a norm constraint
Autor(es)/Inventor(es): Chumbes, Orlando Sarmiento
Orientador: Fampa, Marcia Helena Costa
Resumo: Neste trabalho, estamos interessados em desenvolver técnicas de relaxação para problemas de otimização cúbicos restritos à esfera. Cabe ressaltar que estes problemas são NP-difíceis em contraste com suas versões quadráticas. Apesar da não convexidade o problema quadrático restrito à esfera, conhecido na literatura como subproblema de região de confiança, pode ser resolvido eficientemente já que o problema dual associado é côncavo com gap de dualidade nulo. Na literatura, diversas técnicas de relaxação têm sido estudadas para problemas polinomiais, baseadas em desigualdades RLT e via Programação Semidefinida, obtendo-se bons resultados em programação quadrática e recentemente estendida para programação com polinômios de maior grau. Nesta tese, apresentamos duas técnicas para encontrar limites inferiores para os problemas cúbicos restritos à esfera. A primeira técnica desenvolvida lineariza tanto a função objetivo quanto a função que define a restrição (funções cúbica e quadrática respectivamente), esta técnica é uma adaptação das metodologias propostas na literatura para programas de otimização polinomial. A segunda técnica desenvolvida utiliza quatro diferentes abordagens de decomposição para a função objetivo dos problemas cúbicos. Diferentemente da técnica de linearização, desenvolvemos abordagens que decompõem a função objetivo sem modificar a região viável, com a intenção de obter melhores limites. Resultados computacionais são apresentados nos quais mostramos a eficiência das abordagens propostas.
Resumo: In this work, we are interested in developing relaxation techniques for cubic optimization problems subject to a norm constraint. It should be noted that these problems are NP-hard in constrast to their quadratic variants. In spite of the non-convexity the latter quadratic problem, which is the well-known trust region subproblem, can be solved efficiently since it has a concave dual problem with no duality gap. In the literature, several relaxation techniques have been studied to polynomials problems, based on RLT inequalities and via Semidefinite Programming, obtaining good results in quadratic programming, and recently extended for programs with higher degree polynomials. In this thesis, we present two techniques to find lower bounds for the cubic optimization problems subject to a norm constraint. The first technique linearizes both objective and constraint functions (cubic and quadratic functions respectively), this technique is an adaptation of approaches proposed in the literature for polynomial optimization programs. The second technique uses four different decomposition approaches for the objective functions of the cubic optimization problems. Unlike the first technique, these approaches that decompose objective function without modifying the feasible region, with the intention of obtaining better lower bounds. Computational results are presented in which we show the efficiency of the proposed approaches.
Palavras-chave: Programação global com polinômios
Problema de otimização cúbico
Desigualdades de reformulação e linearização (RLT)
Novas abordagens de relaxação
Método de decomposição Lagrangeana
Assunto CNPq: CNPQ::ENGENHARIAS
Programa: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Unidade produtora: Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Editora: Universidade Federal do Rio de Janeiro
Data de publicação: Jun-2019
País de publicação: Brasil
Idioma da publicação: por
Tipo de acesso: Acesso Aberto
Aparece nas coleções:Engenharia de Sistemas e Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
OrlandoSarmientoChumbes.pdf579.21 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.