论文标题
线性编程的准牛顿原始偶发点算法的多项式最差案例迭代复杂性
Polynomial worst-case iteration complexity of quasi-Newton primal-dual interior point algorithms for linear programming
论文作者
论文摘要
准Newton方法是大规模数值优化的众所周知的技术。他们在优化问题或非线性方程系统中使用黑森的近似值。在内部点上下文中，准Newton算法计算与Newton Systems关联的矩阵的低级别更新，而不是在每次迭代时从头开始对其进行计算。在这项工作中，我们表明，线性编程的简化准牛顿原始二个内部点算法享有多项式最差案例迭代的复杂性。考虑了算法的可行和不可行的病例，并分析了中心路径的最常见社区。据我们所知，这是为这些方法提供多项式最差迭代复杂性界限的首次尝试。毫不奇怪，当使用牛顿方向时，使用准牛顿指示时获得的最坏情况复杂性结果比其对应物差。但是，准Newton的更新对于大规模优化问题非常有吸引力，在大规模优化问题中，分解矩阵的成本远高于求解线性系统的成本。
Quasi-Newton methods are well known techniques for large-scale numerical optimization. They use an approximation of the Hessian in optimization problems or the Jacobian in system of nonlinear equations. In the Interior Point context, quasi-Newton algorithms compute low-rank updates of the matrix associated with the Newton systems, instead of computing it from scratch at every iteration. In this work, we show that a simplified quasi-Newton primal-dual interior point algorithm for linear programming enjoys polynomial worst-case iteration complexity. Feasible and infeasible cases of the algorithm are considered and the most common neighborhoods of the central path are analyzed. To the best of our knowledge, this is the first attempt to deliver polynomial worst-case iteration complexity bounds for these methods. Unsurprisingly, the worst-case complexity results obtained when quasi-Newton directions are used are worse than their counterparts when Newton directions are employed. However, quasi-Newton updates are very attractive for large-scale optimization problems where the cost of factorizing the matrices is much higher than the cost of solving linear systems.
