A new extension of Chubanov’s method to symmetric cones
提出Chubanov方法的新变体，用于求解对称锥上的可行性问题，通过扩展Roos的方法，在计算复杂度上优于现有方法，数值实验显示在病态实例上更高效。
Abstract We propose a new variant of Chubanov’s method for solving the feasibility problem over the symmetric cone by extending Roos’s method (Optim Methods Softw 33(1):26–44, 2018) of solving the feasibility problem over the nonnegative orthant. The proposed method considers a feasibility problem associated with a norm induced by the maximum eigenvalue of an element and uses a rescaling focusing on the upper bound for the sum of eigenvalues of any feasible solution to the problem. Its computational bound is (1) equivalent to that of Roos’s original method (2018) and superior to that of Lourenço et al.’s method (Math Program 173(1–2):117–149, 2019) when the symmetric cone is the nonnegative orthant, (2) superior to that of Lourenço et al.’s method (2019) when the symmetric cone is a Cartesian product of second-order cones, (3) equivalent to that of Lourenço et al.’s method (2019) when the symmetric cone is the simple positive semidefinite cone, and (4) superior to that of Pena and Soheili’s method (Math Program 166(1–2):87–111, 2017) for any simple symmetric cones under the feasibility assumption of the problem imposed in Pena and Soheili’s method (2017). We also conduct numerical experiments that compare the performance of our method with existing methods by generating strongly (but ill-conditioned) feasible instances. For any of these instances, the proposed method is rather more efficient than the existing methods in terms of accuracy and execution time.