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

• 成果类型: Article; Early Access
• 署名作者: Pena, Javier; Soheili, Negar
• 署名单位: Carnegie Mellon University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1235
• 发表日期: 2022
• 关键词: condition number; relaxation

摘要

We propose a simple projection and rescaling algorithm that finds maximum support solutions to the pair of feasibility problems: find x is an element of L boolean AND R-+(n) and find (x) over cap is an element of L-perpendicular to boolean AND R-+(n) , where L is a linear subspace in R-n and L(perpendicular to)is its orthogonal complement. The algorithm complements a basic procedure that involves only projections onto L and L-perpendicular to 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 is an element of L boolean AND 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 race.