A Variation on a Random Coordinate Minimization Method for Constrained Polynomial Optimization

Abstract

In this paper we propose an algorithm for solving constrained polynomial minimization problems. The algorithm is a variation on the random coordinate descent, in which transverse steps are sometimes taken. Differently from other methods, the proposed technique is guaranteed to converge in probability to the global solution of the minimization problem, even when the objective polynomial is nonconvex. The technique appears to be promising for tackling nonlinear control problems in which the standard Sum-of-Squares methods may fail due to the problem size. The theoretical results are corroborated by numerical tests that validate the efficiency of the method.