Sensitivity analysis in linear programming and semidefinite programming using interior-point methods

被引：32
|
作者：
Yildirim, EA [1 ]
Todd, MJ [1 ]
机构：
[1] Cornell Univ, Sch Operat Res & Ind Engn, Ithaca, NY 14853 USA
来源：
MATHEMATICAL PROGRAMMING | 2001年 / 90卷 / 02期
关键词：
sensitivity analysis; interior-point methods; linear programming; semidefinite programming;
D O I：
10.1007/PL00011423
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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 method:, 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 hounds 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.
引用
收藏
页码：229 / 261
页数：33
相关论文
共 50 条
  • [41] Interior-point algorithm for linear programming based on a new descent direction
    Billel, Zaoui
    Djamel, Benterki
    Aicha, Kraria
    Hadjer, Raouache
    RAIRO-OPERATIONS RESEARCH, 2023, 57 (05) : 2473 - 2491
  • [42] Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension
    Elizabeth John
    E. Alper Yıldırım
    Computational Optimization and Applications, 2008, 41 : 151 - 183
  • [43] Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension
    John, Elizabeth
    Yildirim, E. Alper
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2008, 41 (02) : 151 - 183
  • [44] IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming
    Zhang, Rui-Jin
    Liu, Xin-Wei
    Dai, Yu-Hong
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2024, 88 (01) : 1 - 36
  • [45] Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results
    Alizadeh, F
    Haeberly, JPA
    Overton, ML
    SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (03) : 746 - 768
  • [46] IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming
    Rui-Jin Zhang
    Xin-Wei Liu
    Yu-Hong Dai
    Computational Optimization and Applications, 2024, 88 : 1 - 36
  • [47] ON THE TURING MODEL COMPLEXITY OF INTERIOR POINT METHODS FOR SEMIDEFINITE PROGRAMMING
    de Klerk, Etienne
    Vallentin, Frank
    SIAM JOURNAL ON OPTIMIZATION, 2016, 26 (03) : 1944 - 1961
  • [48] A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming
    Gonzalez-Lima, Maria D.
    Oliveira, Aurelio R. L.
    Oliveira, Danilo E.
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2013, 56 (03) : 573 - 597
  • [49] Expected number of iterations of interior-point algorithms for linear programming
    Huang, SM
    JOURNAL OF COMPUTATIONAL MATHEMATICS, 2005, 23 (01) : 93 - 100
  • [50] A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming
    María D. Gonzalez-Lima
    Aurelio R. L. Oliveira
    Danilo E. Oliveira
    Computational Optimization and Applications, 2013, 56 : 573 - 597
12345