Projection and rescaling algorithm for finding maximum support solutions to polyhedral conic systems

DOI10.1287/MOOR.2021.1235zbMATH Open1510.90178arXiv2003.08911MaRDI QIDQ6337052FDOQ6337052

Authors: Javier Peña, Negar Soheili 

Publication date: 19 March 2020

Abstract: We propose a simple projection and rescaling algorithm that finds maximum support solutions to the pair of feasibility problems [ ext{find} ; xin Lcapmathbb{R}^n_{+} ;;;; ext{ and } ; ;;;; ext{find} ; hat xin L^perpcapmathbb{R}^n_{+}, ] where $L$ is a linear subspace of $mathbb{R}^n$ and $L^{p}erp$ is its orthogonal complement. The algorithm complements a basic procedure that involves only projections onto $L$ and $L^{p}erp$ 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 problem [ ext{find} ; xin Lcapmathbb{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.

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

This page was built for publication: Projection and rescaling algorithm for finding maximum support solutions to polyhedral conic systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337052)