On the Complexity of Using Handelman Relaxation for Solving Polynomial Optimization Problems

This paper investigates the computational complexity involved when using Handelman relaxation method for solving multivariable polynomial optimization problems. In particular, the relationship between the degree of the Handelman representation of nonnegative polynomial function over convex polytopic set and the number of decision variables required to prove its existence through linear programming method is characterized. A simulation result to help illustrate the computational complexity and rate of convergence of Handelman relaxation method for solving multivariable polynomial optimization problem is also presented.