Abstract
This paper presents an algorithm for solving a linear program LP (to a given tolerance) from a given prespecified starting point. As such, the algorithm does not depend on any “bigM” initialization assumption. The complexity of the algorithm is sensitive to and is dependent on the quality of the starting point, as assessed by suitable measures of the extent of infeasibility and the extent of nonoptimality of the starting point. Two new measures of the extent of infeasibility and of nonoptimality of a starting point are developed. We then present an algorithm for solving LP whose complexity depends explicitly and only on how close the starting point is to the set of LP feasible and optimal solutions (using these and other standard measures), and also onn (the number of inequalities). The complexity results using these measures of infeasibility and nonoptimality appear to be consistent with the observed practical sensitivity of interior-point algorithms to certain types of starting points. The starting point can be any pair of primal and dual vectors that may or may not be primal and/or dual feasible, and that satisfies a simple condition that typically arises in practice or is easy to coerce.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
K.M. Anstreicher, A combined phase I—phase II projective algorithm for linear programming, Mathematical Programming 43 (1989) 209–223.
K.M. Anstreicher, A combined phase I—phase II scaled potential algorithm for linear programming, Mathematical Programming 52 (1991) 429–439.
K.M. Anstreicher, On interior algorithms for linear programming with no regularity assumptions, Operations Research Letters 11 (1992) 209–212.
R.M. Freund, Theoretical efficiency of a shifted barrier function algorithm for linear programming, Linear Algebra and its Applications 152 (1991) 19–41.
R.M. Freund, A potential-function reduction algorithm for solving a linear program directly from an infeasible “warm start”, Mathematical Programming 52 (1991) 441–466.
R.M. Freund, A potential reduction algorithm with user-specified phase I—phase II balance, for solving a linear program from an infeasible warm start, to appear in SIAM Journal on Optimization.
R.M. Freund, Following a “balanced” trajectory from an infeasible point to an optimal linear programming solution with a polynomial-time algorithm, to appear in Mathematics of Operations Research.
G. de Ghellinck and J.-P. Vial, A polynomial Newton method for linear programming, Algorithmica 1 (1986) 425–453.
P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, Shifted barrier methods for linear programming, Technical Report SOL 88-9, Department of Operations Research, Stanford University (1988).
N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica 4 (1984) 373–395.
M. Kojima, N. Megiddo and S. Mizuno, A primal-dual infeasible-interior-point algorithm for linear programming, Research Report RJ 8500, IBM Almaden Research Center, San Jose, CA (1991), Mathematical Programming 61 (1993) 261–280.
I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a primal-dual interior point method for linear programming, Linear Algebra and its Applications 152 (1991) 191–222.
I.J. Lustig and D.F. Shanno, private communication (April, 1993).
R. Marsten, R. Subramanian, M. Saltzman, I.J. Lustig and D. Shanno, Interior point methods for linear programming: Just call Newton, Lagrange, and Fiacco and McCormick!, Interfaces 20 (1990) 105–116.
J. Mitchell, An interior point column generation method for linear programming using shifted barriers, SIAM Journal on Optimization 4 (1994) 423–440.
S. Mizuno, Polynomiality of infeasible interior point algorithms for linear programming, Mathematical Programming 67 (1994) 109–119.
S. Mizuno, M. Kojima and M.J. Todd, Infeasible-interior-point primal-dual potential-reduction algorithms for linear programming, to appear in SIAM Journal on Optimization.
S. Mizuno, M. J. Todd and Y. Ye, A surface of analytic centers and infeasible-interior-point algorithms for linear programming, Mathematics of Operations Research 20 (1995) 135–162.
C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization (Prentice-Hall, NJ, 1982).
R.A. Polyak, Modified barrier functions (theory and methods), Mathematical Programming 54 (1992) 177–222.
F.A. Potra, A quadratically convergent infeasible interior-point algorithm for linear programming, Report No. 28, Dept. of Mathematics, The University of Iowa, Iowa City, IA (1992).
F.A. Potra, An infeasible interior-point predictor-corrector algorithm for linear programming, to appear in SIAM Journal on Optimization.
F.A. Potra, A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points, Mathematical Programming 67 (1994) 383–406.
C. Roos and J.P. Vial, A polynomial method of approximate centers for linear programming, Mathematical Programming 54 (1992) 295–305.
M.J. Todd, On Anstreicher's combined phase I—phase II projective algorithm for linear programming, Mathematical Programming 55 (1992) 1–15.
M.J. Todd, Combining phase I and phase II in a potential reduction algorithm for linear programming, Mathematical Programming 59 (1993) 133–150.
M.J. Todd and Y. Wang, On combined phase 1-phase 2 projective methods for linear programming, Algorithmica 9 (1993) 64–83.
P. Tseng, A simple complexity proof for a polynomial-time linear programming algorithm, Operations Research Letters 8 (1989) 155–159.
J.P. Vial, A projective algorithm for linear programming with no regularity condition, Operations Research Letters 12 (1992) 1–2.
Y. Ye, M.J. Todd and S. Mizuno, An\(O(\sqrt {nL} )\)-iteration homogeneous and self-dual linear programming algorithm, Mathematics of Operations Research 19 (1994) 53–67.
Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM Journal on Optimization 4 (1994) 208–227.
Y. Zhang, Superlinear convergence of infeasible interior-point methods for linear programming, Mathematical Programming 66 (1994) 361–377.
Author information
Authors and Affiliations
Additional information
Research supported in part by the MIT-NTU Collaboration Agreement.
Rights and permissions
About this article
Cite this article
Freund, R.M. An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution. Ann Oper Res 62, 29–57 (1996). https://doi.org/10.1007/BF02206810
Issue Date:
DOI: https://doi.org/10.1007/BF02206810