论文标题
最小值问题的更新和稳定框架
An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem
论文作者
论文摘要
我们考虑了Polyhedra上的最小值点（MNP）问题，这是一个涵盖线性编程的良好问题。我们提出了一个一般的算法框架，该框架结合了解决此问题的两种基本方法：主动设置方法和一阶方法。我们的算法执行了一阶更新步骤，然后迭代旨在“稳定”当前迭代的其他预测，即找到本地最佳的解决方案，同时保持当前的紧密不平等。此类步骤先前已用于非负平方（NNL）问题的活动集方法中。 我们以多个迭代的数量在多个迭代中绑定在维度和相关的电路不平衡度量中。特别是，对于网络流量实例，该算法强烈多项式。古典NNLS算法（例如Lawson-Hanson算法）是我们框架的特殊实例。结果，我们获得了这些算法的收敛范围。我们的初步计算实验显示出有希望的实践表现。
We consider the minimum-norm-point (MNP) problem over polyhedra, a well-studied problem that encompasses linear programming. We present a general algorithmic framework that combines two fundamental approaches for this problem: active set methods and first order methods. Our algorithm performs first order update steps, followed by iterations that aim to `stabilize' the current iterate with additional projections, i.e., find a locally optimal solution whilst keeping the current tight inequalities. Such steps have been previously used in active set methods for the nonnegative least squares (NNLS) problem. We bound on the number of iterations polynomially in the dimension and in the associated circuit imbalance measure. In particular, the algorithm is strongly polynomial for network flow instances. Classical NNLS algorithms such as the Lawson-Hanson algorithm are special instantiations of our framework; as a consequence, we obtain convergence bounds for these algorithms. Our preliminary computational experiments show promising practical performance.
