zbMATH — the first resource for mathematics

Condition numbers for polyhedra with real number data. (English) Zbl 0858.90097
Summary: We consider the complexity of finding a feasible point inside a polyhedron specified by homogeneous linear constraints. A primal-dual interior point method is used. The running time of the interior point method can be bounded in terms of a condition number of the coefficient matrix \(A\) that has been proposed by Ye. We demonstrate that Ye’s condition number is bounded in terms of another condition number for weighted least squares discovered by Stewart and Todd. Thus, the Stewart-Todd condition number, which is defined for real-number data, also bounds the complexity of finding a feasible point in a polyhedron.

90C05 Linear programming
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
Full Text: DOI
[1] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[2] Luo, Z.Q.; Tseng, P., Error bounds and convergence analysis of matrix splitting algorithms for the affine variational inequality problem, SIAM J. on optim., 2, 43-54, (1992) · Zbl 0777.49010
[3] Mangasarian, O.L., Simple computable bounds for solutions of linear complementarity problems and linear programs, Math. programming study, 25, 1-12, (1985) · Zbl 0582.90098
[4] O’Leary, D.P., On bounds for scaled projections and pseudoinverses, Linear algebra appl., 132, 115-117, (1990) · Zbl 0701.15003
[5] Polyak, R., Modified barrier functions (theory and methods), Math. programming, 54, 177-222, (1992) · Zbl 0756.90085
[6] Stewart, G.W., On scaled projections and pseudoinverses, Linear algebra appl., 112, 189-193, (1989) · Zbl 0658.15003
[7] Todd, M.J., A Dantzig-Wolfe-like variant of Karmarkar’s interior-point linear programming algorithm, Oper. res., 38, 1006-1018, (1990) · Zbl 0724.90037
[8] Tuncel, L., A pseudo-polynomial complexity analysis for interior-point algorithms, ()
[9] Vavasis, S.A., Stable numerical algorithms for equilibrium systems, SIAM J. matrix anal. appl., 15, 1108-1131, (1994) · Zbl 0806.65020
[10] Vavasis, S.A.; Ye, Y., An accelerated interior point method whose running time depends only on A, () · Zbl 1345.90059
[11] Ye, Y., Toward probabilistic analysis of interior-point algorithms for linear programming, Math. oper. res., 19, 38-52, (1994) · Zbl 0799.90086
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.