Rescaling Algorithms for Linear Conic Feasibility
Rescaling Algorithms for Linear Conic Feasibility
复制标题
DOI：
10.1287/moor.2019.1011
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
D. Dadush;László A. Végh;G. Zambelli
中科院分区：
文献类型：
--
作者：
D. Dadush;László A. Végh;G. Zambelli
我们提出了两个线性圆锥可行性问题的简单多项式时间算法。对于矩阵$ a \ in \ mathbb {r}^{m \ times n} $，内核问题需要在$ a $的内核中一个正向量，并且图像问题需要$ a的图像中的正量向量^\ top $。两种算法都迭代简单的一阶步骤和重新缩放步骤。这些重新分类提高了自然的几何潜力。如果Goffin的条件度量$ \ rho_a $为负，则内核问题是可行的，并且内核算法的最差复杂性为$ o \ left（（（m^3n+mn^2）\ log {| \ rho_a | \ rho_a |^|^ {-1}}} \ right）$;如果$ \ rho_a> 0 $，则图像问题是可行的，并且图像算法在时间$ o \ left（m^2n^2 \ log {\ rho_a^{ - 1}}} \ right）$中运行。我们还将图像算法扩展到Oracle设置。我们通过扩展我们的算法以在$ a $的内核中找到最大支持的非负矢量来解决退化案例$ \ rho_a = 0 $，并以$ a^\ top $的图像为单位。在这种情况下，运行时间范围在比特大小的计算模型中表示：对于带有整数条目的输入矩阵$ a $和总编码长度$ l $，最大支持内核算法在时间$ o \ left中运行（（（（（（ m^3n+mn^2）l \ right）$，而最大支持图像算法在时间$ o \ left（m^2n^2l \ right）$中运行。标准线性编程可行性问题可以很容易地减少为最大支持问题，从而产生了线性编程的多项式时间算法。
We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix $A\in \mathbb{R}^{m\times n}$, the kernel problem requires a positive vector in the kernel of $A$, and the image problem requires a positive vector in the image of $A^\top$. Both algorithms iterate between simple first order steps and rescaling steps. These rescalings improve natural geometric potentials. If Goffin's condition measure $\rho_A$ is negative, then the kernel problem is feasible and the worst-case complexity of the kernel algorithm is $O\left((m^3n+mn^2)\log{|\rho_A|^{-1}}\right)$; if $\rho_A>0$, then the image problem is feasible and the image algorithm runs in time $O\left(m^2n^2\log{\rho_A^{-1}}\right)$. We also extend the image algorithm to the oracle setting. We address the degenerate case $\rho_A=0$ by extending our algorithms to find maximum support nonnegative vectors in the kernel of $A$ and in the image of $A^\top$. In this case the running time bounds are expressed in the bit-size model of computation: for an input matrix $A$ with integer entries and total encoding length $L$, the maximum support kernel algorithm runs in time $O\left((m^3n+mn^2)L\right)$, while the maximum support image algorithm runs in time $O\left(m^2n^2L\right)$. The standard linear programming feasibility problem can be easily reduced to either maximum support problems, yielding polynomial-time algorithms for Linear Programming.