In this work, in the context of Linear and Quadratic Programming, we interpret Primal Dual Regularized Interior Point Methods (PDR-IPMs) in the framework of the Proximal Point Method. The resulting Proximal Stabilized IPM (PS-IPM) is strongly supported by theoretical results concerning convergence and the rate of convergence, and can handle degenerate problems. Moreover, in the second part of this work, we analyse the interactions between the regularization parameters and the computational foot-print of the linear algebra routines used to solve the Newton linear systems. In particular, when these systems are solved using an iterative Krylov method, we propose general purpose preconditioners which, exploiting the regularization and a new rearrangement of the Schur complement, remain attractive for a series of subsequent IPM iterations. Therefore they need to be recomputed only in a fraction of the total IPM iterations. The resulting regularized second order methods, for which low-frequency-updates of the preconditioners are allowed, pave the path for an alternative third way in-between first and second order methods.
翻译:在这项工作中,我们结合线性与二次曲线编程,在“准点法”的框架内解释两极固定式内地方法(PDR-IPM),由此形成的极准稳定性IPM(PS-IPM)得到关于趋同率和趋同率的理论结果的有力支持,并能够处理退化的问题。此外,在这项工作的第二部分,我们分析用于解决牛顿线性系统的线性代数例行程序(PDR-IPM)的正规化参数和计算脚印之间的相互作用。特别是,当这些系统使用迭代Krylov方法解决时,我们提出了通用目的先决条件,利用Schur补充的正规化和新的重新排列,仍然对随后的一系列IPP的迭代法具有吸引力。因此,它们只需要在IPM总迭代数的一小部分中进行重新整理。由此产生的正规化的第二顺序方法,允许使用低频率前置装置,为第一种和第二顺序方法之间的第三种选择铺路。