The Semi-Algebraic Split Feasibility Problem and Its Semidefinite Relaxation

Abstract

This paper considers the semi-algebraic split feasibility problem (SASFP), i.e., the split feasibility problem defined by polynomials. It is more than a special case of the split feasibility problem (SFP) or the multiple-sets split feasibility problem (MSFP), since the solution set could be nonconvex or empty. We first establish the semi-definite relaxation for the SASFP, then discuss on the relationship of feasibility between the SASFP and its SDP relaxation, especially focus on infeasibility. Finally, some numerical experiments for different cases are implemented, and the corresponding results are reported.