Abstract
We propose analyzing interior-point methods using notions of problem-instance size which are direct generalizations of the condition number of a matrix. The notions pertain to linear programming quite generally; the underlying vector spaces are not required to be finite-dimensional and, more importantly, the cones defining nonnegativity are not required to be polyhedral. Thus, for example, the notions are appropriate in the context of semi-definite programming. We prove various theorems to demonstrate how the notions can be used in analyzing interior-point methods. These theorems assume little more than that the interiors of the cones (defining nonnegativity) are the domains of self-concordant barrier functions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
F. Alizadeh, “Interior point methods in semidefinite programming with applications to combinatorial optimization,”SIAM Journal on Optimization 5 (1) (1995) 13–51.
E.J. Andersen and P. Nash,Linear Programming in Infinite Dimensional Spaces: Theory and Applications (Wiley, Chichester, 1987).
L. Blum, M. Shub and S. Smale, “On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines,”AMS Bulletin (New Series) 21 (1989) 1–46.
J.M. Borwein and A.S. Lewis, “Partially finite convex programming, Part I: Quasi relative interiors and duality theory,”Mathematical Programming 57 (1) (1992) 15–48.
J. Demmel, “On condition numbers and the distance to the nearest ill-posed problem,”Numerische Mathematik 51 (1987) 251–289.
J. Demmel, “The probability that a numerical analysis problem is difficult,”Mathematics of Computation 50 (1988) 449–480.
D. den Hertog, “Interior point approach to linear, quadratic and convex programming,” Technische Universiteit, Delft (1992).
R.J. Duffin, “Infinite programs,” in: H.W. Kuhn and A.W. Tucker, eds.,Linear Inequalities and Related Systems (Princeton University Press, Princeton, NJ, 1956) pp. 157–170.
M.C. Ferris and A.B. Philpott, “An interior point algorithm for semi-infinite linear programming,”Mathematical Programming 43 (3) (1989) 257–276.
A.V. Fiacco and K.O. Kortanek, eds.,Semi-Infinite Programming and Applications, Lecture Notes in Economics and Mathematical Systems, Vol. 215 (Springer, New York, 1983).
S. Filipowski, “Towards a computational complexity theory that uses knowledge and approximate data,” Ph.D. Thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1993).
S. Filipowski, “On the complexity of solving feasible systems of linear inequalities specified with approximate data,”Mathematical Programming, to appear.
R. Freund, “An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution,”Annals of Operations Research, to appear.
D. Goldfarb and M.J. Todd, “Linear programming,” in: A. Rinnooy Kan and M.J. Todd, eds.,Handbooks in Operations Research and Management Science, Vol. I: Optimization (North-Holland, Amsterdam, 1989) Chapter 2.
C.C. Gonzaga, “An algorithm for solving linear programming in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior Point and Related Methods (Springer, New York, 1989) pp. 1–28.
C.C. Gonzaga, “Path following methods for linear programming,”SIAM Review 34 (1992) 167–227.
R.B. Holmes, “A Course on Optimization and Best Approximation,” Lecture Notes in Mathematics, Vol. 257 (Springer, Berlin, 1972).
C. Kallina and A.C. Williams, “Linear programming in reflexive spaces,”SIAM Review 13 (1971) 350–376.
N.K. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
L.G. Khachiyan, “A polynomial algorithm in linear programming,”Doklady Akademii Nauk SSSR 224 (1979) 1086–1093; translated in:Soviet Mathematics Doklady 20 (1979) 191–194.
D.G. Luenberger,Optimization by Vector Space Methods (Wiley, New York, 1969).
Yu.E. Nesterov and A.S. Nemirovskii,Interior Point Methods in Convex Optimization: Theory and Applications (SIAM, Philadelphia, PA, 1993).
J. Renegar, “On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials,”Mathematics of Operations Research 12 (1987) 121–148.
J. Renegar, “A polynomial-time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1) (1988) 59–93.
J. Renegar, “Lecture notes on the efficiency of Newton's method for convex optimization in Hilbert spaces,” preprint, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1993).
J. Renegar, “Some perturbation theory for linear programming,”Mathematical Programming 65 (1) (1994) 73–91.
J. Renegar, “Incorporating condition measures into the complexity theory of linear programming,”SIAM Journal on Optimization 5 (3) (1995) 506–524.
J. Renegar and M. Shub, “Unified complexity analysis for Newton LP methods,”Mathematical Programming 53 (1) (1992) 1–16.
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
W. Rudin,Functional Analysis (McGraw-Hill, New York, 1973).
M. Shub and S. Smale, “Complexity of Bezout's theorem, I: Geometric aspects,”Journal of the American Mathematical Society 6 (1993) 459–501.
M. Shub and S. Smale, “Complexity of Bezout's theorem, III: Condition number and packing,”Journal of Complexity 9 (1993) 4–14.
S. Smale, “The fundamental theorem of algebra and complexity theory,”AMS Bulletin (New Series) 4 (1981) 1–35.
S. Smale, “On the efficiency of algorithms of analysis,”AMS Bulletin (New Series) 13 (1985) 87–121.
S. Smale, “Algorithms for solving equations,” in:Proceedings of the International Congress of Mathematicians, Berkeley, CA, 1986 (American Mathematical Society, Providence, RI, 1987) pp. 172–195.
S. Smale, “Some remarks on the foundations of numerical analysis,”SIAM Review 32 (1990) 211–220.
M.J. Todd, “Interior-point algorithms for semi-infinite programming,” preprint, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1991).
L. Tuncel, “Asymptotic behavior of interior-point methods,” Ph.D. Thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1993).
S. Vavasis and Y. Ye, “Condition numbers for polyhedra with real number data,”Operations Research Letters 17 (5) (1995) 209–214.
S. Vavasis and Y. Ye, “A primal—dual interior-point method whose running time depends only on the constraint matrix,”Mathematical Programming, to appear.
J. Vera, “Ill-posedness in mathematical programming and problem solving with approximate data,” Ph.D. Thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1992).
J. Vera, “Ill-posedness and the complexity of deciding existence of solutions of linear programs,” Technical Report, Department of Industrial Engineering, University of Chile, Santiago (1992).
J. Vera, “Ill-posedness and the computation of solutions to linear programs with approximate data,”SIAM Journal on Optimization, to appear.
M.H. Wright, “Interior methods for constrained optimization,” in: A. Iserles, ed.,Acta Numerica 1992 (Cambridge University Press, Cambridge, 1992) pp. 341–407.
Author information
Authors and Affiliations
Additional information
Research supported by NSF Grant #CCR-9103285 and IBM. This paper was conceived in part while the author was sponsored by the visiting scientist program at the IBM T.J. Watson Research Center.
Rights and permissions
About this article
Cite this article
Renegar, J. Linear programming, complexity theory and elementary functional analysis. Mathematical Programming 70, 279–351 (1995). https://doi.org/10.1007/BF01585941
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585941