- Solving Conic Systems via Projection and Rescaling Javier Pena (jfpandrew.cmu.edu) Negar Soheili (nazaduic.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 finite-dimensional vector space $V$. This projection and rescaling algorithm is inspired by previous work on rescaled versions of the perceptron algorithm and by Chubanov's projection-based 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/2015Entry Accepted: 12/18/2015Entry Last Modified: 12/26/2016Modify/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 Optimization Online is supported by the Mathematical Optmization Society.