We propose two multigrid approaches for the global optimization of polynomial op- timization problems. In our first contribution we consider problems that arise from the discretization of infinite dimensional optimization problems, such as PDE optimiza- tion problems, boundary value problems and some global optimization applications. In many of these applications, the level of discretization can be used to obtain a hierarchy of optimization models that captures the underlying infinite dimensional problem at different degrees of fidelity. This approach, inspired by multigrid methods, has been successfully used for decades to solve large systems of linear equations. However, it has not been adapted to SDP relaxations of polynomial optimization problems. The main difficulty is that the geometric information between grids is lost when the original problem is approximated via an SDP relaxation. Despite the loss of geometric infor- mation, we show how a multigrid approach can be applied by developing prolongation operators to relate the primal and dual variables of the SDP relaxation between lower and higher levels in the hierarchy of discretizations. We develop sufficient conditions for the operators to be useful in applications. Our conditions are easy to verify in prac- tice, and we discuss how they can be used to reduce the complexity of infeasible interior
iv
point methods. Following the same reasoning, the second approach does not assume any particular structure of the underlying polynomial problem, but instead considers the hierarchy of sparse SDP relaxations that can be obtained for any unconstrained polynomial optimizations problem with structured sparsity. Prolongation operators are defined for this type of hierarchy, and theoretical results that show their usefulness are proved. Our preliminary results highlight two promising advantages of following a multigrid approach in contrast with a pure interior point method: the percentage of problems that can be solved to a high accuracy is much higher, and the time necessary to find a solution can be reduced significantly, especially for large scale problems.