Optimization Online


An improved projection and rescaling algorithm for conic feasibility problems

Wei Zhang (lindelfeel***at***gmail.com)
Kees Roos (C.Roos***at***tudelft.nl )
Yanqin Bai (yqbai***at***i.shu.edu.cn)

Abstract: 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.

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
Entry Accepted: 07/23/2018
Entry Last Modified: 01/02/2019

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