多项式分裂可行问题

本文研究多项式分裂可行问题,即由多项式不等式定义的分裂可行问题,包括凸与非凸、可行与不可行的问题;给出多项式分裂可行问题解集的半定松弛表示;研究其半定松弛化问题的性质;并基于这些性质建立求解多项式分裂可行问题的半定松弛算法.本文在较为一般的条件下证明了,如果分裂可行问题有解,则可通过本文建立的算法求得一个解点;如果问题无解,则该算法能够判别问题不可行.最后通过数值实验对算法进行验证.

The split feasibility problem with polynomials

This paper discusses the split feasibility problem with polynomials. The sets are semi-algebraic,defined by polynomial inequalities. They can be either convex or nonconvex, either feasible or infeasible. We give semidefinite relaxations for representing the intersection of the sets. Properties of the semidefinite relaxations are studied. Based on the representation, a semidefinite relaxation algorithm is given for solving the split feasibility problem. Under a general condition, we prove that if the split feasibility problem is feasible, we can get a feasible point;if it is infeasible, we can obtain a certificate for the infeasibility. Some numerical examples are given.