Nonconvex Quadratically-Constrained Feasibility Problems: An Inside-Ellipsoids Outside-Sphere Model
提出一种新方法将非凸二次约束可行性问题等价转化为内椭球外球优化问题，该问题可行域凸、仅多一个变量，并通过迭代求解凸优化子问题来获得原问题的可行解或局部解，数值实验验证了其有效性。
Abstract This paper proposes a new approach for solving Quadratically Constrained Feasibility Problems (QCFPs). We introduce an isomorphic mapping (one-to-one and onto correspondence), which equivalently converts the QCFP to an optimization problem called the Inside-Ellipsoids Outside-Sphere Problem (IEOSP). This mapping preserves the convexity of convex constraints, but it converts all non-convex constraints to convex ones. The QCFP is a feasibility problem with non-convex constraints, while the IEOSP is an optimization problem with a convex feasible region and a non-convex objective function. It is shown that the global optimal solution of IEOSP is a feasible solution of the QCFP. Comparing the structures of QCFP and the proposed IEOSP, the second model only has one extra variable compared to the original QCFP because it employs one slack variable for the mapping. Thus, the problem dimension approximately remains unchanged. Due to the convexity of all constraints in IEOSP, it has a well-defined feasible region. Therefore, it can be solved much easier than the original QCFP. This paper proposes a solution algorithm for IEOSP that iteratively solves a convex optimization problem. The algorithm is mathematically shown to reach either a feasible solution of the QCFP or a local solution of the IEOSP. To illustrate our theoretical developments, a comprehensive numerical experiment is performed, and 500 different QCFPs are studied. All these numerical experiments confirm the promising performance and applicability of our theoretical developments in the current paper.