In this paper we consider polynomial conic optimization problems, where the feasible set is defined by constraints in the form of given polynomial vectors belonging to given nonempty closed convex cones, and we assume that all the feasible solutions are nonnegative. This family of problems captures in particular polynomial optimization problems, polynomial semidefinite polynomial optimization problems and polynomial second order cone optimization problems. We propose a general hierarchy of linear conic optimization relaxations inspired by an extension of Pólya's Positivstellensatz for homogeneous polynomials being positive over a basic semialgebraic cone contained in the nonnegative orthant. Under some classical assumptions these relaxations converge monotonically to the optimal value of the original problem. The members of this hierarchy provide strong bounds for the optimum value, especially for polynomial semidefinite problems and polynomial second order cone optimization problems, where these bounds are comparable or even outperform the existing bounds based on sum-of-squares. Adding a redundant polynomial positive semidefinite constraint to the original problem improves the bounds drastically. We provide an extensive list of numerical examples which clearly indicate the advantages and disadvantages of our hierarchy.
Citation
Dickinson, P.J.C. & Povh, J. Comput Optim Appl (2019). https://doi.org/10.1007/s10589-019-00066-0
Article
View A new approximation hierarchy for polynomial conic optimization