Abstract
This paper studies the robustness of interior point linear programming algorthims with respect to initial iterates that are too close to the boundary. Weighted least squares analysis is used in studying the near-boundary behavior of the affine scaling and Newton centering directions, which are often combined by interior point methods. This analysis leads to the develoment of a modified Newton centering direction exhibiting better near-boundary behavior than the two directions. Theoretical and computational results from the NETLIB test set are presented indicating that an approach which uses the modified newton direction is more robust than both the pure affine scaling approach and one which uses the Newton direction as the centering direction.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. Adler, N.K. Karmarkar, M.C.G. Reseande, and G. Veiga, “An implementation of Karmarkar's algrothm for linear programming,”Math. Programming 44 (1989) 297–335.
E.R. Barnes, “A variation on Karmarkar's algorithm for solving linear programming problems,”Math. Programming 36 (1986) 174–182.
I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Doklady Akadmiia Nauk SSSR 174 (1969) 747–748, (English translation:Soviet Math. Doklady 8 674–675.
A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, NY, 1968.
K.R. Frisch,The logarithmic potential method of convex programming, Memorandum, University Institute of Economic, Oslo, Norway, 1955.
D.M. Gay, “Electronic mail distribution of linear programming test problems,”Math. Programming Society COAL Newsletter,13 (1985) 10–12.
G. Golub and C. Van Loan, Matrix Computations, 2nd ed., The Johns Hopkins University Press, Baltimore, MD 567–568, 1989.
C.C. Gonzaga, “An algorithm for solving linear programming inO(n 3 L) operations,” N. Meggido, ed.,Progress in Math. Programming, Springer, Verlag, New York, NY, 1–28, 1989.
C.C. Gonzaga,Convergence of the large step prinal affine-scaling algorithm for prinal nondegenerate linear programs, Technical Report ES-230/90, Dept. of Systems Engineering and Computer Science, COPPE Federal University of Rio de Janeiro, Rio de Janeiro, Brazil, 1990.
C.C. Gonzaga, “Search directions for interior linear-programming methods,”Algorithmica,6 (1991), 153–161.
O. Güler, D. den Hertog, C. Roos, T. Terlaky, and T. Tsuchiya,Degeneracy in interior point methods for linear programming, Report 91-102, Faculty of technical Mathematics and Informatics, TU Delft, Delft, The Netherlands, 1991.
D. den Hertog and C. Roos, “A survey of search directions in interior point methods for linear programming,”Math. Programming,52 (1991) 481–510.
N.K. Karmarkar, “A new polynomial-time algorihm for linear programming,”Combinatorica,4 (1984) 373–395.
N.K. Karmakar and K.G. Ramakrishnan, “Computational results of an interior point algorithm for large scale linear programming,”Math. Programming,52 (1991) 555–586.
M. Kojima, S. Mizuno, and A. Yoshiye, “A primal-dual inteior point method for linear progamming,” in N. Meggido, ed.,Progress in Math. Programming, Springer-Verlag, New York, NY, 29–47, 1989.
C.L. Lawson and R.J. Hanson,Solving Least Squares Problems, Prentice-Hall Inc., Englewood Cliffs, NJ, 1974.
I.J. Lustig, R.E. Marsten, and D.F. Shanno, “Computational experience with aprimal-dual interior point method for linear programming,”Liear Algebra and its Applications,152 (1991) 191–222.
N. Meggido and M. Shub, “Boundary behaviour of interior point algorithms in linear programming,”Math. of Oper. Res. 14 (1989) 97–114.
C.L. Monma and A.J. Morton, “Computational experience with the dual affine variant of Karmarkar's method for linear programming,”Oper. Res. Letters,6 (1987), 261–267.
R.D.C. Monteiro, T. Tsuchiya, and Y. Wang,A simplified global convergence proof of the affine scaling algorithm, Manusript, Dept. of Systems and Industrial Engineering, University of Arizona, Tucson, AZ, 1992.
D. Shanno,Tutorial: Interior point methods for linear programming, Presented at the ORSA/TIMS 34th Joint National Meeting, San Francisco, CA. November, 1992.
G. Sonnevend,An analytical centre for polyhedrons and new classes of global algorthms for linear (smoth, convex) programming, Lecture Notes in Control and Information Sciences 84, Springer-Verlag, Berlin, 1986, 866–876.
G. Sonnevend, “New algorithms in convex programming based on the notin of “centre” (for a system of analytic inequalities) and on rational extrapolation,” in K.H. Hoffmann et al., eds.,Trends in Math. Optimization, Birkhauser Verlag, Basel, Switzerland, 1988, 311–327.
M.J. Todd,A low complexity interior point algorithm for linear programming, Technical Report 903, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1990.
M.J. Todd, “Playing with interior points,”Math. Programming Society COAL Newsletter,19 (1991) 17–25.
T. Tsuchiya and M. Muramatsu,Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems,” Research Memorandum 423. The Institute of Statistical Mathematics, Tokyo, Japan, 1992.
R.J. Vanderbei, M.S. Meketon, and B.A. Freedman, “A modification of Karmarkar's linear programming algorithm,”Algorithmica 1 (1986) 395–407.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hipolito, A.L. A weighted least squaes study of robustness in interior point linear programming. Comput Optim Applic 2, 29–46 (1993). https://doi.org/10.1007/BF01299141
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01299141