Relaxações tratáveis para problemas de otimização cúbicos restritos à esfera

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.