On the limiting properties of the affine-scaling directions

Key Findings & Data:The worst-case angle between the affine-scaling directions and the objective function vector provides an interesting measure that has been very helpful in convergence analyses and in understanding the behaviour of various interior-point algorithms.

💡

Conclusion & Impact:We also provide a new characterization of the smallest large variable complexity measure of Ye.

🔬Design:Research Article

📍Scope:Comprehensive Sample

⚙️Variables:Domain Parameters

Abstract

We study the limiting properties of the affine-scaling directions for linear programming problems. The worst-case angle between the affine-scaling directions and the objective function vector provides an interesting measure that has been very helpful in convergence analyses and in understanding the behaviour of various interior-point algorithms. We establish new relations between this measure and some other complexity measures which are used in the complexity analyses of algorithms for linear programming. We also provide a new characterization of the smallest large variable complexity measure of Ye.

🔖

Cite This Article

LARA, H. J., GONZAGA, C. C., TUNÇEL, L. (2004). On the limiting properties of the affine-scaling directions. Yöneylem Araştırması Dergisi, Cilt: 16 - Sayı: 1, 47–69. https://ajindex.com/articles/332322

References (16)

I. Adler and R. D. C. Monteiro, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Maih. Prog. A 50 (1991) 29-51
E. R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Math. Prog. A 36 (1986) 174-182
A. Ben-Tal and M. Teboulle, A geometric property of the least squares solution of linear equations, Linear Algebra and Its Applications 139 (1990) 165-170
I. I. Dikin. On the speed of an iterative process, Upravlyaemye Sistemi 12 (1974) 54-60
I. I. Dikin, Iterative solution of problems of linear and quadratic programming, (Russian) Dokl. Akad. Nauk SSSR 174 (1967) 747-748
M. Epelman and R. M. Freund, A new condition measure, pre-conditioners, and relations between different measures of conditioning for conic linear systems, SIAM J. Optim. 12 (2002) 627-655
C. C. Gonzaga and R. A. Tapia. On the convergence of the Mizuno-Todd-Ye algorithm to the analytic center of the solution set, SIAM J. Optim. 7 (1997) 47-65
C. C. Gonzaga and H. Lara. A note on properties of condition numbers, Linear Algebra and Its Applications 261 (1997) 269-273
L. A. Hall and R. J. Vanderbei, Two-thirds is sharp for affine scaling, Oper. Res. Lett. 13 (1993) 197-201
J. C. K. Ho and L. Tunçel, Reconciliation of various complexity and condition measures for linear programming problems and a generalization of Tardos' theorem, In: Foundations of Computational Mathematics, Proceedings of the Smalefest 2000, F. Cucker and-J. M. Rojas (eds.) World Scientific, 2002, pp. 93-147
N. Karmarkar, A new polynomial-time algorithm for linear programming, Combina-torica 4 (1984) 373-395
H. J. Lara and C. C. Gonzaga. A characterization of the smallest large variable condition number. Investigacion Operativa Volume 9, N 1,2 and 3, (2000)
H.J. Lara and L. Tunçel, Condition and complexity measures for infeasibility certificates of systems of linear inequalities and their sensitivity analysis, Research Report 2002-10, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, May 2002 (revised: July 2002)
H. J. Lara and L. Tunçel, On the computational complexity of solving systems of linear inequalities, in preparation
N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming, Math. Oper. Res. 14 (1989) 97-146
R. D. C. Monteiro and T. Tsuchiya, A simp