Numerical And Symbolic Hybrid Method In Polynomial Optimization

The multivariate polynomial optimization is an important problem in the globaloptimization. It has applications in many areas of science and engineering, such ascontrol theory and signal processing. Numerical algorithm and symbolic algorithm arethe fundamental approaches for this problem.Symbolic algorithm deals with mathematical symbols and algebra objects withouterror. However, this kind of method often leads to heavy duty of computation when thescale of the problem is large. Numerical algorithm, on the other hand, can solve largerproblem in general. It also faces problems, such as stability. Therefore numerical-symbolic hybrid method would be a natural consideration in order to take the advan-tages of both these two methods. Hanzon and Jibetean proposed matrix method, whichtransforms the optimization of multivariate polynomial to a polynomial system of equa-tions through the first order condition. The method can easily generate the Gr(o|¨)bnerbasis by adding high order leading terms, so that any polynomial can be represented bythese basis. Here the representing coefficient matrix is called associated matrix. Thenone can get the critical points of the objective polynomial through computing eigenval-ues and eigenvectors of the associated matrix.Associated matrix plays an important role in Hanzon-Jibetean method. However,the scale of associated matrix is often large. In this dissertation we propose a newhybrid method, which is named as improved matrix method. We establish a matchingmodel between the added high order leading terms and polynomial equations arisingfrom the first order conditions. By optimizing this matching, we can get the minimalscale of the associated matrix, which would make the scale of the associated matrixsmaller and the algorithm more efficient.At the same time, we propose a new matrix contractive algorithm by adding a newvariable and a new equation to the original first order conditions. In this method, weget the critical points of the objective polynomial through computing the eigenvalue ofthe new added variable only once. By this improvement, we can make the polynomialoptimization much faster. As an application, we apply the improved matrix methods to constructing the startsystem for the homotopy method. Numerical results show that our new start systemsreduce the number of singular solutions in the homotopy continuation procedure.