Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems

We propose a simple projection and rescaling algorithm that finds maximum support solutions to the pair of feasibility problems: $\mathit{\text{find}}\hspace{0.17em}x\in L\cap {\mathbb{R}}_{+}^n\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\mathit{\text{find}}\hspace{0.17em}\widehat{x}\in L^{\perp }\cap {\mathbb{R}}_{+}^n,$ where L is a linear subspace in ${\mathbb{R}}^n$ and $L^{\perp }$ is its orthogonal complement. The algorithm complements a basic procedure that involves only projections onto L and $L^{\perp }$ with a periodic rescaling step. The number of rescaling steps and, thus, overall computational work performed by the algorithm are bounded above in terms of a condition measure of the above pair of problems. Our algorithm is a natural but significant extension of a previous projection and rescaling algorithm that finds a solution to the full support problem: $\mathit{\text{find}}\hspace{0.17em}x\in L\cap {\mathbb{R}}_{++}^n$ when this problem is feasible. As a byproduct of our new developments, we obtain a sharper analysis of the projection and rescaling algorithm in the latter special case.