  


Solving Conic Systems via Projection and Rescaling
Javier Pena (jfpandrew.cmu.edu) Abstract: We propose a simple {\em projection and algorithm} to solve the feasibility problem \[ \text{ find } x \in L \cap \Omega, \] where $L$ and $\Omega$ are respectively a linear subspace and the interior of a symmetric cone in a finitedimensional vector space $V$. This projection and rescaling algorithm is inspired by previous work on rescaled versions of the perceptron algorithm and by Chubanov's projectionbased method for linear feasibility problems. As in these predecessors, each main iteration of our algorithm contains two steps: a {\em basic procedure} and a {\em rescaling} step. When $L \cap \Omega \ne \emptyset$, the projection and rescaling algorithm finds a point $x \in L \cap \Omega$ in at most $O(\log(1/\delta(L \cap \Omega)))$ iterations, where $\delta(L \cap \Omega) \in (0,1]$ is a measure of the most interior point in $L \cap \Omega$. The ideal value $\delta(L\cap \Omega) = 1$ is attained when $L \cap \Omega$ contains the center of the symmetric cone $\Omega$. We describe several possible implementations for the basic procedure including a perceptron scheme and a smooth perceptron scheme. The perceptron scheme requires $)(r^4)$ perceptron updates and the smooth perceptron scheme requires $O(r^2)$ smooth perceptron updates, where $r$ stands for the Jordan algebra rank of $V$. Keywords: Projection, Rescaling, Symmetric Cones Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF] Entry Submitted: 12/18/2015 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  