Efficiency improvement in an nD-systems approach to polynomial optimization

The problem of finding the global minimum of a so-called Minkowski-norm dominated polynomial can be approached by the matrix method of Stetter-Moller, which reformulates it as a large eigenvalue problem. A drawback of this approach is that the matrix involved is usually very large. However, all that is needed for modern iterative eigenproblem solvers (such as methods based on Arnoldi and Jacobi-Davidson techniques) is a routine which computes the action of the matrix on a given vector. The huge number of required iterations is the main reason why the action of the matrix on a vector has to be computed efficiently. This paper focuses on this aspect of the optimization technique. To avoid building the large matrix one can associate the system of first order conditions with an nD-system of difference equations, by interpreting the variables in the polynomial equations as shift operators working on a multidimensional time series. Then one way to compute the action of the matrix on a vector efficiently, is by setting up a corresponding shortest path problem and to apply an algorithm like Dijkstra's or Floyd's algorithm, to solve it. In the case of 2D-systems the shortest path problem can be solved analytically. For nD-systems the situation is more complicated but a number of partial results are available. For large n the shortest path problem has a high computational complexity, and therefore some heuristic procedures are developed to arrive cheaply at suboptimal paths with acceptable performance. The approach and techniques presented in this paper are demonstrated by means of a worked example involving a dominated polynomial of 4 variables and total degree 8.
Key words: global polynomial optimization, Grƒobner basis, Stetter-Moller matrix method, nD-systems, large eigenvalue problems