论文标题
投影和恢复算法，以找到对多面体圆锥系统的最大支持解决方案
Projection and rescaling algorithm for finding maximum support solutions to polyhedral conic systems
论文作者
论文摘要
我们提出了一种简单的投影和重新算法，该算法可为一对可行性问题找到最大支持解决方案\ [\ text {find} \; x \ in l \ cap \ mathbb {r}^n _ {+} \; \; \; \; \ text {and} \; \; \; \; \; \ text {find} \; \ hat x \ in l^\ perp \ cap \ mathbb {r}^n _ {+}，\]，其中$ l $是$ \ mathbb {r}^n $和$ l^\ perp $的线性子空间是其正交补充。该算法补充了一个基本程序，该程序仅涉及$ l $和$ l^\ perp $的预测，并定期重新缩放步骤。在上述问题的条件度量方面，算法进行的重新缩放步骤数量和总体计算工作的数量是有限的。 我们的算法是先前投影和恢复算法的自然而显着的扩展，该算法可以找到解决问题的解决方案\ [\ text {find} \; x \ in L \ cap \ mathbb {r}^n _ {++} \]当此问题可行时。作为我们新发展的副产品，我们在后一种特殊情况下对投影和重新算法进行了更清晰的分析。
We propose a simple projection and rescaling algorithm that finds maximum support solutions to the pair of feasibility problems \[ \text{find} \; x\in L\cap\mathbb{R}^n_{+} \;\;\;\; \text{ and } \; \;\;\;\; \text{find} \; \hat x\in L^\perp\cap\mathbb{R}^n_{+}, \] where $L$ is a linear subspace of $\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 problem \[ \text{find} \; 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.
