Sensitivity analysis in linear programming and semidefinite programming using interior-point methods
Sensitivity analysis in linear programming and semidefinite programming using interior-point methods
复制标题
使用内点法进行线性规划和半定规划的敏感性分析
DOI：
10.1007/pl00011423
复制
发表时间：
2001
影响因子：
2.7
通讯作者：
M. Todd
中科院分区：
文献类型：
--
作者：
E. Alper Yıldırım;M. Todd
本文分析了线性规划（LP）和半确定规划（SDP）中的右侧扰动和代价参数。我们得到了允许内点方法在单个内点迭代中恢复可行和近最优解的摄动的紧界。对于LP中唯一的非退化解，我们证明了用内点法得到的界与用最优基得到的界比较好。我们还使用Monteiro-Zhang家族的搜索方向给出了SDP的明确界限，并将它们专门用于who， H. K.。M和NT方向。
We analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming (SDP). We obtain tight bounds on the perturbations that allow interior-point methods to recover feasible and near-optimal solutions in a single interior-point iteration. For the unique, nondegenerate solution case in LP, we show that the bounds obtained using interior-point methods compare nicely with the bounds arising from using the optimal basis. We also present explicit bounds for SDP using the Monteiro-Zhang family of search directions and specialize them to the AHO, H..K..M, and NT directions.