  


An improved projection and rescaling algorithm for conic feasibility problems
Wei Zhang (lindelfeelgmail.com) Abstract: Motivated by Chubanov's projectionbased 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 proxmirror 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 multiblock case is also considered. Keywords: Projection and Rescaling, Symmetric cones, Condition measure, Conic systems Category 1: Linear, Cone and Semidefinite Programming Citation: Nat. Univ. Singapore/ TU Delft/ Shanghai Univ. July 2018 Download: [PDF] Entry Submitted: 07/22/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  