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

Javier Peña () and Negar Soheili ()
Additional contact information
Javier Peña: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Negar Soheili: College of Business Administration, University of Illinois at Chicago, Chicago, Illinois 60607

Mathematics of Operations Research, 2022, vol. 47, issue 4, 3304-3316

Abstract: We propose a simple projection and rescaling algorithm that finds maximum support solutions to the pair of feasibility problems: find x ∈ L ∩ R + n and find x ^ ∈ L ⊥ ∩ R + n , where L is a linear subspace in R n and L ⊥ is its orthogonal complement. The algorithm complements a basic procedure that involves only projections onto L and L ⊥ 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: find x ∈ L ∩ 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.

Keywords: Primary: 90C05; secondary: 90C25; 90C60; projection; rescaling; support; condition measures; conic feasibility (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1235 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:4:p:3304-3316

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().