TY - JOUR

T1 - Polynomial optimization and a Jacobi-Davidson type method for commuting matrices

AU - Bleylevens, I.W.M.

AU - Hochstenbach, M.E.

AU - Peeters, R.L.M.

PY - 2013

Y1 - 2013

N2 - In this paper we introduce a new Jacobi–Davidson type eigenvalue solver for a set of commuting matrices, called JDCOMM, used for the global optimization of so-called Minkowski-norm dominated polynomials in several variables. The Stetter–Möller matrix method yields such a set of real non-symmetric commuting matrices since it reformulates the optimization problem as an eigenvalue problem. A drawback of this approach is that the matrix most relevant for computing the global optimum of the polynomial under investigation is usually large and only moderately sparse. However, the other matrices are generally much sparser and have the same eigenvectors because of the commutativity. This fact is used to design the JDCOMM method for this problem: the most relevant matrix is used only in the outer loop and the sparser matrices are exploited in the solution of the correction equation in the inner loop to greatly improve the efficiency of the method. Some numerical examples demonstrate that the method proposed in this paper is more efficient than approaches that work on the main matrix (standard Jacobi–Davidson and implicitly restarted Arnoldi), as well as conventional solvers for computing the global optimum, i.e., SOSTOOLS, GloptiPoly, and PHCpack.
Keywords: Multivariate polynomial optimization; Global optimization; Solving systems of polynomial equations; Stetter–Möller matrix method; Commuting matrices; Jacobi–Davidson; Correction equation; Arnoldi method

AB - In this paper we introduce a new Jacobi–Davidson type eigenvalue solver for a set of commuting matrices, called JDCOMM, used for the global optimization of so-called Minkowski-norm dominated polynomials in several variables. The Stetter–Möller matrix method yields such a set of real non-symmetric commuting matrices since it reformulates the optimization problem as an eigenvalue problem. A drawback of this approach is that the matrix most relevant for computing the global optimum of the polynomial under investigation is usually large and only moderately sparse. However, the other matrices are generally much sparser and have the same eigenvectors because of the commutativity. This fact is used to design the JDCOMM method for this problem: the most relevant matrix is used only in the outer loop and the sparser matrices are exploited in the solution of the correction equation in the inner loop to greatly improve the efficiency of the method. Some numerical examples demonstrate that the method proposed in this paper is more efficient than approaches that work on the main matrix (standard Jacobi–Davidson and implicitly restarted Arnoldi), as well as conventional solvers for computing the global optimum, i.e., SOSTOOLS, GloptiPoly, and PHCpack.
Keywords: Multivariate polynomial optimization; Global optimization; Solving systems of polynomial equations; Stetter–Möller matrix method; Commuting matrices; Jacobi–Davidson; Correction equation; Arnoldi method

U2 - 10.1016/j.amc.2013.08.015

DO - 10.1016/j.amc.2013.08.015

M3 - Article

SN - 0096-3003

VL - 224

SP - 564

EP - 580

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

ER -