Stabilization of interior-point methods for linear programming

被引：13

作者：

Kovacevic-Vujcic, VV ^{[1
]}

Asic, MD

机构：

[1] Univ Belgrade, Fac Org Sci, Belgrade, Yugoslavia

[2] Ohio State Univ, Dept Math, Newark, OH USA

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 1999年 / 14卷 / 03期

关键词：

interior-point methods; ill-conditioning; degeneracy; stabilization;

D O I：

10.1023/A:1026452506999

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The paper studies numerical stability problems arising in the application of interior-point methods to primal degenerate linear programs. A stabilization procedure based on Gaussian elimination is proposed and it is shown that it stabilizes all path following methods, original and modified Dikin's method, Karmarkar's method, etc.

引用

页码：331 / 346

页数：16

共 50 条

[1] Stabilization of Interior-Point Methods for Linear Programming
Vera V. Kovacevic-Vujcic
Miroslav D. Asic
Computational Optimization and Applications, 1999, 14 : 331 - 346
[2] Sensitivity analysis in linear programming and semidefinite programming using interior-point methods
Yildirim, EA
Todd, MJ
MATHEMATICAL PROGRAMMING, 2001, 90 (02) : 229 - 261
[3] Warm-start strategies in interior-point methods for linear programming
Yildirim, EA
Wright, SJ
SIAM JOURNAL ON OPTIMIZATION, 2002, 12 (03) : 782 - 810
[4] Validated Infeasible Interior-Point Predictor–Corrector Methods for Linear Programming
Ismail I. Idriss
Wolfgang V. Walter
Numerical Algorithms, 2004, 37 : 177 - 185
[5] PCx: An interior-point code for linear programming
Czyzyk, J
Mehrotra, S
Wagner, M
Wright, SJ
OPTIMIZATION METHODS & SOFTWARE, 1999, 11-2 (1-4) : 397 - 430
[6] Validated infeasible interior-point predictor-corrector methods for linear programming
Idriss, II
Walter, WV
NUMERICAL ALGORITHMS, 2004, 37 (1-4) : 177 - 185
[7] Solving linear systems in interior-point methods
Seol, T
Park, S
COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (04) : 317 - 326
[8] A LOW COMPLEXITY INTERIOR-POINT ALGORITHM FOR LINEAR PROGRAMMING
Todd, Michael J.
SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (02) : 198 - 209
[9] Sparsity preserving preconditioners for linear systems in interior-point methods
Drazic, Milan D.
Lazovic, Rade P.
Kovacevic-Vujcic, Vera V.
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2015, 61 (03) : 557 - 570
[10] A Primal-Dual Slack Approach to Warmstarting Interior-Point Methods for Linear Programming
Engau, Alexander
Anjos, Miguel F.
Vannelli, Anthony
OPERATIONS RESEARCH AND CYBER-INFRASTRUCTURE, 2009, : 195 - +

← 1 2 3 4 5 →