Optimization Online


Computational performance of a projection and rescaling algorithm

Javier Pena (jfp***at***andrew.cmu.edu)
Negar Soheili (nazad***at***uic.edu)

Abstract: This paper documents a computational implementation of a {\em projection and rescaling algorithm} for finding most interior solutions to the pair of feasibility problems find $x\in L\cap\mathbb{R}^n_{+} $ and find $x\in L^\perp\cap\mathbb{R}^n_{+},$ where $L$ denotes a linear subspace in $\mathbb{R}^n$ and $L^\perp$ denotes its orthogonal complement. The projection and rescaling algorithm is a recently developed method that combines a {\em basic procedure} involving only low-cost operations with a periodic {\em rescaling step.} We give a full description of a MATLAB implementation of this algorithm and present multiple sets of numerical experiments on synthetic problem instances with varied levels of conditioning. Our computational experiments provide promising evidence of the effectiveness of the projection and rescaling algorithm. Our MATLAB code is publicly available. Furthermore, the simplicity of the algorithm makes a computational implementation in other environments completely straightforward.

Keywords: projection, rescaling, relative interior

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Technical report, Carnegie Mellon University, 2018.

Download: [PDF]

Entry Submitted: 03/19/2018
Entry Accepted: 03/19/2018
Entry Last Modified: 01/15/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