Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-23T22:19:37.997Z Has data issue: false hasContentIssue false
  • English
  • Français

Final iterations in interior point methods – preconditioned conjugate gradients and modified search directions

Published online by Cambridge University Press:  17 February 2009

Weichung Wang
Weichung Wang
Affiliation:
Department of Mathematics and Science Education, National Tainan Teachers College, Tainan 700, Taiwan
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this article we consider modified search directions in the endgame of interior point methods for linear programming. In this stage, the normal equations determining the search directions become ill-conditioned. The modified search directions are computed by solving perturbed systems in which the systems may be solved efficiently by the preconditioned conjugate gradient solver. A variation of Cholesky factorization is presented for computing a better preconditioner when the normal equations are ill-conditioned. These ideas have been implemented successfully and the numerical results show that the algorithms enhance the performance of the preconditioned conjugate gradients-based interior point methods.

Type
Research Article
Information
The ANZIAM Journal , Volume 41 , Issue 3 , January 2000 , pp. 312 - 328
Copyright
Copyright © Australian Mathematical Society 2000

References

[1]Carolan, W., Hill, J., Kennington, J., Niemi, S. and Wichmann, S., “An empirical evaluation of the KORBX algorithms for military airlift applications”, Operations Research 38 (2) (1990) 240–248.Google Scholar
[2]Czyzyk, J., Mehrotra, S. and Wright, S. J., “PCx user guide”, Technical Report OTC 96/01, Optimization Technology Center, Argonne National Laboratory and Northwestern University, 1996.CrossRefGoogle Scholar
[3]Forsgren, A., Gill, P. E. and Shinnerl, J. R., “Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization”, SIAM J. Matrix Anal. Appl. 17 (1996) 187–211.CrossRefGoogle Scholar
[4]Freund, R. W. and Jarre, F., “A QMR-based interior-point algorithm for solving linear programs”, Technical Report, AT&T Bell Laboratories and Institut für Angewandte Mathematik und Statistik, 1995.Google Scholar
[5]Gay, D. M., “Electronic mail distribution of linear programming test problems”, Mathematical Programming Soc. COAL Newsletter (1985).Google Scholar
[6]Gill, P. E. and Murray, W., “Newton-type methods for unconstrained and linearly constrained optimization”, Mathematical Programming 7 (1974) 311–350.Google Scholar
[7]Gonzaga, C. C., “Path-following methods for linear programming”, SIAM Review 34 (2) (06 1992) 167–224.CrossRefGoogle Scholar
[8]Hough, P. D. and Vavasis, S. A., “Complete orthogonal decomposition for weighted least squares”, Center of Applied Mathematics and Department of Computer Science, Cornell University, May 1996.Google Scholar
[9]Karmarkar, N. K., “A new polynomial-time algorithm for linear programming”, Combinatorica 4 (1984) 373–395.Google Scholar
[10]Lustig, I. J., Marsten, R. E. and Shanno, D. F., “Computational experience with a primal-dual interior point method for linear programming”, Linear algebra and its application 152 (1991) 191–222.Google Scholar
[11]Mehrotra, S. and Wang, J.-Sh., “Conjugate gradient based implementation of interior point methods for network flow problems”, Technical Report 95–70.1, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208–3119, U.S.A., October 1995.Google Scholar
[12]Mizuno, Sh. and Jarre, F., “Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation”, Technical Report Research Memorandum 605, The Institute of Statistical Mathematics, Tokyo, Japan, April 1996.Google Scholar
[13]Portugal, L. F., Resende, M. G. C., Veiga, G. and Júdice, J. J., “A truncated primal-infeasible dualfeasible network interior point method”, November 1994.Google Scholar
[14]Vanderbei, R. J., “LOQO: An interior point code for quadratic programming”, Program in Statistics and Operations Research, Princeton University. [email protected], 1995.Google Scholar
[15]Wang, W., “Final iterations in interior point methods — preconditioned conjugate gradients and modified search directions”, Technical Report CS-TR-3674, Computer Science Department Report, University of Maryland, August 1996.Google Scholar
[16]Wang, W., “Iterative methods in interior point algorithms for linear programming”, Ph.D. dissertation, Applied Mathematics Program, University of Maryland, 08 1996.Google Scholar
[17]Wang, W. and O'Leary, D. P., “Adaptive use of iterative methods in interior point methods for linear programming”, Technical Report CS-TR-3560, Computer Science Department Report, University of Maryland, November 1995.Google Scholar
[18]Wright, M. H., “Interior methods for constrained optimization”, in Acta Numerica 1992 (ed. Iserles, A.), (Cambridge University Press, New York, USA, 1992) 341–407.Google Scholar
[19]Zhang, Y., “Solving large-scale linear programs by interior-point methods under the MATLAB environment”, Technical Report TR 96–01, Department of Mathematics and Statistics, University of Maryland Baltimore County, February 1996.Google Scholar