Tractable relaxations for cubic optimization problems subject to a norm constraint

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.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