论文标题
一种结构化修改的牛顿方法，用于求解在二次编程的内点方法中产生的非线性方程的系统
A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming
论文作者
论文摘要
这项工作的重点是用于不平等约束二次程序的内点方法，尤其是在屏障参数的每个值的非线性方程系统上。牛顿迭代提供了高质量的解决方案，但是我们对经过修改的牛顿系统感兴趣，这些系统在计算上便宜，而牺牲了质量较低的解决方案。我们提出了一种结构化修改的牛顿方法，其中每个修改后的雅各布由以前的雅各布组成，再加上每个接下来的迭代的低级别更新矩阵。对于给定的等级，每个更新矩阵都是为了使以2纳米和Frobenius Norm在当前迭代的距离最小化与Jacobian的距离。该方法是从某种意义上保留了雅各布式的非零模式的结构。在理想的理论环境中，结果支持更新矩阵的选择。我们还通过基本的内点实现产生数值结果，以研究理论框架内外的实际绩效。为了提高超出理论框架的性能，我们还激励并构建了两个启发式方法，以添加到该方法中。
The focus in this work is on interior-point methods for inequality-constrained quadratic programs, and particularly on the system of nonlinear equations to be solved for each value of the barrier parameter. Newton iterations give high quality solutions, but we are interested in modified Newton systems that are computationally less expensive at the expense of lower quality solutions. We propose a structured modified Newton approach where each modified Jacobian is composed of a previous Jacobian, plus one low-rank update matrix per succeeding iteration. Each update matrix is, for a given rank, chosen such that the distance to the Jacobian at the current iterate is minimized, in both 2-norm and Frobenius norm. The approach is structured in the sense that it preserves the nonzero pattern of the Jacobian. The choice of update matrix is supported by results in an ideal theoretical setting. We also produce numerical results with a basic interior-point implementation to investigate the practical performance within and beyond the theoretical framework. In order to improve performance beyond the theoretical framework, we also motivate and construct two heuristics to be added to the method.
