A truncated Newton interior-point algorithm for the solution of a multicommodity spatial equilibrium model

L. Portugal, J. Judice, and L. Fernandez

In this paper we introduce a Truncated Newton (TN) interior-point algorithm for solving monotone linear complementarity problems. Contrary to the usual Newton interior-point methods that use exact Newton directions, this algorithm computes at each iteration an approximate Newton direction by employing appropriate preconditioned iterative linear system solvers. The stopping criterion used in these iterative procedures is defined in terms of the norm of the residual vector associated to the linear constraints and guarantes global convergence for the TN interior-point algorithm. We describe an efficient implementation of this algorithm for solving the Linear Complementarity Problem (LCP) associated to the symmetric and nonsymmetric multicommodity spatial equilibrium problems. The Preconditioned Conjugate Gradient (PCG) or the Preconditioned Quasi Minimal Residual (PQMR) algorithms are incorporated in the implementation depending on the matrix of the LCP to be symmetric or nonsymmetric. We also describe an incomplete QR factorization preconditioning technique which greatly improves the convergence properties of the PCG and PQMR algorithms. Finally, the stopping criterion of the TN algorithm exploits the stucture of the network model and leads to an exact solution for the LCP. We report extensive computational experience that shows the great efficiency of the approach discussed in this paper.

[POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]