CONVERGENCE ANALYSIS OF AN INEXACT FEASIBLE INTERIOR POINT METHOD FOR CONVEX QUADRATIC PROGRAMMING
CONVERGENCE ANALYSIS OF AN INEXACT FEASIBLE INTERIOR POINT METHOD FOR CONVEX QUADRATIC PROGRAMMING
复制标题
DOI：
10.1137/120886017
复制
发表时间：
2013-01-01
影响因子：
3.1
通讯作者：
Gondzio, Jacek
中科院分区：
文献类型：
--
作者：
Gondzio, Jacek
本文讨论了凸二次规划的不精确可行内点算法的两个变形。我们将考虑两个不同的邻域：一个是由使用欧几里德范数产生的短步长算法引起的小邻域，另一个是由使用无穷范数产生的（实用的）长步长算法引起的对称邻域。这两种算法都允许不精确地求解牛顿方程组。对于这两种算法，我们将提供牛顿方程中可接受的误差水平的条件，并建立最坏情况下的复杂性结果。
In this paper we will discuss two variants of an inexact feasible interior point algorithm for convex quadratic programming. We will consider two different neighborhoods: a small one induced by the use of the Euclidean norm which yields a short-step algorithm and a symmetric one induced by the use of the infinity norm which yields a (practical) long-step algorithm. Both algorithms allow for the Newton equation system to be solved inexactly. For both algorithms we will provide conditions for the level of error acceptable in the Newton equation and establish the worst-case complexity results.