Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
复制标题
估计一类通过曲率积分求解线性规划的路径跟踪方法的复杂度
DOI：
10.1007/bf01182599
复制
发表时间：
1993
影响因子：
1.8
通讯作者：
J. Stoer
中科院分区：
文献类型：
--
作者：
G. Zhao;J. Stoer
在本文中，我们研究了一类特殊的原始-对偶路径跟踪方法，试图遵循内部可行解的轨迹在原始-对偶空间的原始和对偶问题的最优解。研究的方法是所谓的一阶方法：每次迭代包括一个“长”的步骤，沿着切线的轨迹，其次是明确的重定中心步骤，再次接近的轨迹。结果表明，这些方法的复杂性，这可以通过计算，以达到所需的增益精度的轨迹接近的点的数量来衡量，是有界的积分沿着的轨迹。被积函数是轨迹的二阶导数相对于一个特殊的路径参数的适当加权的测量，所以积分可以松散地称为曲率积分。
In this paper we study a particular class of primal-dual path-following methods which try to follow a trajectory of interior feasible solutions in primal-dual space toward an optimal solution to the primal and dual problem. The methods investigated are so-called first-order methods: each iteration consists of a “long” step along the tangent of the trajectory, followed by explicit recentering steps to get close to the trajectory again. It is shown that the complexity of these methods, which can be measured by the number of points close to the trajectory which have to be computed in order to achieve a desired gain in accuracy, is bounded by an integral along the trajectory. The integrand is a suitably weighted measure of the second derivative of the trajectory with respect to a distinguished path parameter, so the integral may be loosely called a curvature integral.