Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/14068
Type: Tese
Title: Relaxações tratáveis para problemas de otimização cúbicos restritos à esfera
Other Titles: Tractable relaxations for cubic optimization problems subject to a norm constraint
Author(s)/Inventor(s): Chumbes, Orlando Sarmiento
Advisor: Fampa, Marcia Helena Costa
Abstract: 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.
Abstract: 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.
Keywords: 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
Subject CNPq: CNPQ::ENGENHARIAS
Program: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Production unit: Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Publisher: Universidade Federal do Rio de Janeiro
Issue Date: Jun-2019
Publisher country: Brasil
Language: por
Right access: Acesso Aberto
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
OrlandoSarmientoChumbes.pdf579,21 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.