Limiting behavior of the affine scaling continuous trajectories for linear programming problems
Limiting behavior of the affine scaling continuous trajectories for linear programming problems
复制标题
线性规划问题的仿射缩放连续轨迹的限制行为
DOI：
10.1007/bf01594923
复制
发表时间：
1991
影响因子：
2.7
通讯作者：
R. Monteiro
中科院分区：
文献类型：
--
作者：
I. Adler;R. Monteiro
对于标准形式的线性规划问题，我们考虑了由原始仿射尺度算法产生的矢量场的连续轨迹。通过将这些轨迹刻画为某些参数化对数障碍族问题的解，我们证明了这些轨迹趋向于最优解，该最优解一般依赖于起点。通过考虑上述对数障碍族问题的拉格朗日乘子所产生的轨迹，我们证明了与仿射标度轨迹相关的对偶估计的轨迹收敛于对偶问题的所谓“中心”最优解。我们还给出了与仿射标度轨迹的渐近方向有关的结果。我们将简要讨论如何将我们的结果应用于以不同于标准形式的格式表示的线性规划。最后，我们将结果推广到原始-对偶仿射尺度算法。
We consider the continuous trajectories of the vector field induced by the primal affine scaling algorithm as applied to linear programming problems in standard form. By characterizing these trajectories as solutions of certain parametrized logarithmic barrier families of problems, we show that these trajectories tend to an optimal solution which in general depends on the starting point. By considering the trajectories that arise from the Lagrangian multipliers of the above mentioned logarithmic barrier families of problems, we show that the trajectories of the dual estimates associated with the affine scaling trajectories converge to the so called ‘centered’ optimal solution of the dual problem. We also present results related to asymptotic direction of the affine scaling trajectories. We briefly discuss how to apply our results to linear programs formulated in formats different from the standard form. Finally, we extend the results to the primal-dual affine scaling algorithm.