Motivated by Chubanov’s projection-based method for linear feasibility problems [Chubanov2015], a projection and rescaling algorithm for the conic feasibility problem \[ find \; x\in L\bigcap \Omega \] is proposed in [Pena2016], where $L$ and $\Omega$ are respectively a linear subspace and the interior of a symmetric cone in a finitely dimensional vector space $V$. When $V$ is the Euclidean space $R^n$, $L$ is the null space of some matrix $A\in R^{m\times n}$ and $\Omega$ is $R_{++}^n$, the problem reduces to the linear feasibility problem. In their method for the general case, the condition measure $\delta(L\bigcap\Omega)$ is adopted to analyze the iteration complexity. In this paper, we utilize another condition measure $\delta_{\infty}(L\bigcap\Omega)$, which is based on the $L_{\infty}$ norm. Besides, in the basic procedure, the stopping criterion is determined by the projection onto the space $L^{\bot}$ instead of $L$. Based on this, we can reduce the number of iterations for a von Neumann type basic procedure and a smoothed perceptron basic procedure by $O(r)$ and $O(r^{\frac12})$ respectively, where $r$ is the Jordan algebra rank of $V$. Furthermore, the prox-mirror method is also customized as a basic procedure, which can achieve the same iteration complexity of the smoothed perceptron method. Moreover, by carefully examining the fast and slow iterations, we can further reduce the total iteration complexity with the von Neumann type basic procedure. Similarly to the algorithm in [Lourenco2016], we can alternatively stop the algorithm when the possible solutions are near the boundary of the cone. The multi-block case is also considered.
Citation
Nat. Univ. Singapore/ TU Delft/ Shanghai Univ. July 2018