Optimization Online


Solving Conic Systems via Projection and Rescaling

Javier Pena (jfp***at***andrew.cmu.edu)
Negar Soheili (nazad***at***uic.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 )


Download: [PDF]

Entry Submitted: 12/18/2015
Entry Accepted: 12/18/2015
Entry Last Modified: 12/26/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society